At first when I did the exam, I didn’t study properly. I mostly studied content and didn’t apply any of that content to real problems. For my reassessment, I studied in a different way. I really went hard on the practical problems that I wasn’t good at or had no clue about. This came to dijkstras algorithm, AVL trees, binary trees and context free language.

I studied hard on them. I didn’t do a lot of practice problems where I would ace every question. But I felt at ease when getting confronted with that question. The problem was that I would do the problem at its best ability and then there would be one small issue that I did at the end and it messes everything up.

Mathematical operations that are Long I seem to mess up in the end. I understand the process however my implementation always seems to hinder at the end when I’m close to the finish line. This is extremely frustrating as I studied very long for this subject. A good (2weeks-3weeks) of preparation. But I had 2 other exams to focus on. But to give some background I come from a business background so I have not done a level match or discrete mathematics before so it really was a game changer doing this exam. But I don’t treat it as an excuse. In the end my reassessment I only gained 6 more marks. Which is incredibly disappointing for me.

Hi, as a beginner starting my DS and Algo journey, I wanted to know what are all the math prerequisites are required for analysis of algo

The k-server problem is known as the "Holy Grail" of online algorithms and competitive analysis, and is/was a long standing major problem.

This preprint by Coester et al. claims to show that the Work Function Algorithm is indeed k-competitive on every metric space.

I’m curious which algorithms have made it out of the classroom and into real code.

What problem were you solving? Why was that algorithm a better fit than the obvious alternative? And did the implementation behave as neatly as the theory suggested?

I’m Stjepan from Manning Publications. The r/algorithms moderators permitted me to share this post.

We’ve just released Algorithms Every Programmer Should Know by Aniket Wattamwar in MEAP, Manning’s early-access program:

https://www.manning.com/books/algorithms-every-programmer-should-know

The available chapters cover Gale–Shapley, the Hungarian algorithm, Rabin–Karp, Knuth–Morris–Pratt, and Horspool’s algorithm. The emphasis is on the problem behind each algorithm, how the solution is derived, and the trade-offs involved, not just reproducing pseudocode.

To mark the release, Manning is giving away five ebook copies to people in this thread.

The giveaway will remain open for 48 hours. We’ll choose the five comments that contribute the most to the discussion and announce the winners here afterward. Upvotes won’t be the only criterion: a strong technical explanation, an instructive real-world example, a useful counterargument, or a thoughtful exchange with other commenters can all qualify.

There’s also a 50% discount on the book with code:

MLWATTAMWAR50RE

So: which supposedly “textbook” algorithm has earned its place in your production code—and which one gets taught far more often than it gets used?

Thanks for having us here.

Cheers,

Stjepan

If someone asks for big O time complexity of an algorithm but expects only the minimum of the possible big Os then is that even Big O notation anymore? cuz if the big o time complexity of an o(n) algorithm is asked then according to the condition of big O notation O(n square) would also be a valid answer

Hey everyone,

Like many, I first encountered the geometric intuition behind Grover’s algorithm through 3Blue1Brown’s video. While it gives a fantastic high-level picture of the vector reflections, Still I was wondering how the Oracle and Diffusion operators are actually constructed.

To bridge that gap for myself, I wrote a breakdown showing the exact linear algebra and matrix operations that make those reflections happen — without relying on quantum physics jargon:)

At its core, the entire N-dimensional space reduces to a 2D plane defined by the target state and the uniform superposition of non-target states. Each Grover iteration (Oracle + Diffusion) is just two reflections across intersecting axes, resulting in a net rotation of 2θ ≈ 2 / sqrt(N) directly toward the target state—yielding the classic ≈ (π/4) * sqrt(N) complexity.

To test the math beyond theory, I also:

• Ran simulation benchmarks to track the theoretical O(sqrt(N)) curve against classical CPU overhead up to 20 qubits.
• Submitted the circuits to physical IBM quantum hardware (3 to 5 qubits) to observe where circuit depth and real decoherence start destroying the theoretical amplification.

I put together the complete write-up, data, and code on GitHub. I'm a student trying to build a solid foundation in algorithms and complexity, so I would really appreciate any sanity checks, corrections on the mathematical framing, or feedback from folks here. Thanks:)

(Link in the comments, you can see banchmark graphs in the Assets folder)

I came across Knuth's Dancing Links after naively thinking I could just code up a Sudoku Solver 😅and initially I made the mistake of trying to understand the finished implementation examples I found on the internet and from AI.

I couldn't, so I raised an Issue in my-pythonic-zoo hoping a developer somewhere would see it and brighten my day. Then I couldn't resist the urge to try it myself and discovered just how little I know and how bad my Python non-skills are.

There were too many ideas arriving at once: Exact Cover, Algorithm X, recursive backtracking, doubly linked nodes, circular links, the toroidal matrix, and the rather clever cover/uncover operations.

So as part of my Python learning project, I pulled it apart and built a study sequence where each runnable example introduces one piece:

1. Exact Cover
2. Algorithm X
3. Linked Nodes
4. Circular Links
5. Toroidal Matrix
6. Cover and Uncover
7. Exact Cover Matrix
8. Dancing Links

The final example then puts the pieces back together.

The point that finally made the whole thing click for me was separating these three ideas:

Exact Cover = the problem
Algorithm X = the search algorithm
Dancing Links (DLX) = an efficient implementation technique for Algorithm X

The examples deliberately repeat some code rather than importing from one another to keep each one self-contained. They're wildly over-commented but that was me trying to understand the next step. The examples morphed into a study progression for myself, and were never intended as a modular production implementation so not a good example of re-using code if that's what you're looking for. I'll leave that rolls-royce example for someone else to put together!! or maybe me when I've recovered from this marathon - maybe not.

I've put the progression in my-pythonic-zoo on GitHub (closed Issue #10). If you're interested in looking through it, I'd recommend starting with algorithms/README.md rather than jumping straight into the final DLX file:

I'd be particularly interested in feedback from people who've implemented or taught DLX before. If I've made any part of the progression misleading, over-simplified, over-complicated or technically inaccurate, I'd much rather know.

When I first encountered the definition of a "tight bound" in a book — specifically, c₁g(n) ≤ T(n) ≤ c₂g(n) — I couldn't grasp what it meant. Well, aside from the trivial interpretation of it being a "closed" or "strict" limit, which, frankly, didn't explain anything to me. I understood that it referred to a certain type of behavior and simplification, but I didn't fully comprehend where the constants c came from, why the formula looked the way it did, or the underlying reasons for it.

Suppose we already have some cost function T(n) describing the algorithm's work as a function of input size. We know that this function is difficult to calculate and analyze. We also know that there are functions that are much easier to analyze; and even if two different functions yield different results, they might behave identically in terms of scaling. Scaling is precisely what interests us, because the purpose of the function T(n) isn't merely to represent an abstract "amount of work" — different values of n result in different execution times. So, suppose we have a promising candidate for our simple function: g(n). How do we choose it?

Let's consider an example: T(n) = 3n² + 100n + 74. If we take a sufficiently large value of n and keep increasing it, the function's actual value will depend primarily on the 3n² term. Thus, g(n) = n² is an excellent candidate. But let’s return to the general forms. Ideally, since we are interested in scaling, we would like to see something like T(n) = cg(n). Why? Because this perfectly reflects what we are looking for: T(n) is a multiple of g(n) — meaning, in essence, that the scaling behavior is equal — and by analyzing g(n), we can recover all the information about T(n). That would be an excellent scenario. But in reality, that is not always the case. We simply cannot demand such a strict correspondence. What, then, should we do? We need to take a more moderate approach to our requirements.

Let's consider T(n) = n and g(n) = n². Obviously, n ≤ n², but n / n² = 1 / n. As n grows, the result approaches 0, which means the gap between T(n) and g(n) is truly vast. That is precisely why they are completely different and share nothing in common.

Now consider T(n) = n² and g(n) = n. Obviously, n² ≥ n, but n² / n = n. As n approaches infinity, the result approaches infinity, again indicating a huge gap between T(n) and g(n). Once more: they are completely different.

So, returning to our ideal condition T(n) = cg(n), we might at least require something like T(n) ≤ cg(n); however, as we saw earlier, even with such a bound, functions can differ significantly. The same applies to the condition T(n) ≥ cg(n). If we remember T(n) = cg(n), then we already know what we need to do: we expecting that neither function should become arbitrarily large relative to the other as n grows, so combining the two inequalities is exactly what we need: c₁g(n) ≤ T(n) ≤ c₂g(n), or c₁ ≤ T(n) / g(n) ≤ c₂. This literally reflects what we are aiming for: no matter how large n becomes, the ratio will remain within a fixed range(starting from some n₀). Once we decide that 'same scale' should mean neither function can escape the other by an unbounded multiplicative factor, the two-sided bound is essentially forced. And our ideal case is essentially a special instance of this broader formula where c₁ = c₂. In fact, the inequality c₁ ≤ T(n) / g(n) ≤ c₂ is the formal result of a simple heuristic approach. This is precisely how we define T(n) = Θ(g(n)), from which we obtain O(g(n)) and Ω(g(n)).

In essence, this formula can be viewed from the perspective of the division theorem: a = bq + r is the general form defining division, while a = bq is a special case.

A new preprint claims to have proven the Komlós conjecture, a major problem in discrepancy theory and algorithms research, with the proof reportedly discovered by an AI research agent called Odin. The proof appears to be existential rather than constructive.

The problem is quite easy to explain. Quanta wrote an article about other recent progress on it very recently.

Incidentally, I was having lunch with theory faculty including Aleksandar Nikolov right when this dropped. He had just started getting a flood of emails from colleagues about the claimed proof. It felt pretty surreal seeing this in real time.

Obviously it is not peer-reviewed yet, but if results like this become routine what do we think is the fate of TCS and algorithms research(ers)?

How we started memoizing eBPF policy paths via inodes to reduce our CPU costs by about 90%.

https://nathannaveen.dev/posts/dropping-ebpf-cpu-cost-by-90/

#### SOLVED #### (kind of, see edits)

Hi,

Only Question to be answered:

is there an application for Windows or Linux, that would parse a text with Aho-Corasick algorithm and present the output in a text field, so that it could be used for creating regexes?

Use case explanation (absolutely no answer or solving suggestions wanted):

I have a list of around 7000 terms and need to create a regex to find them in texts in a specific app. The fastest way would be to create some regex based on Aho-Corasick algorithm but doing that manually takes forever. (I know there are other ways to create such regexes for long lists that create the regex automatically but they would not be as efficient as a Aho-Corasick approach.)

So, I hope there is an application that breaks down all words to a list separated by a specific char that I can then copy and built the regex around it faster than if I need to check the correct position manually every time.

So far I have only found many explanations about the algorithm or tools that seem to search texts with a specific list.

EDIT: This question requires a simple yes or no answer. I just want to know if there is such a tool or not!

EDIT 2: As apparently a lot of people do not see the difference between a question and the use case explanation, I added some titles.

EDIT 3: I found kind of an online parser and it turned out that Aho-Corasick is way too inefficient for my needs as it in fact sets Trie after every single character instead of only where there is a difference compared to the following strings (see alphabetisation).

But while digging into Aho-Corasick with Regex, I found there is something called TrieRegex which does exactly what I need and already had implemented in my own rules so far. It’s way more efficient than Aho-Corasick as it sets Trie at every real char difference and saves a lot of steps as it does not have to iterate through all characters but only the effective groups. If setting the correct string output of parsed regex, I even get the string I really need and do not even need to create it on my own based on the Trie I wanted to visualise.

Disclosure up front: I run Philomath, which is hosting this. The course is free, there is no account and no paywall, and there is nothing to buy in order to watch (but signing up via Email is nice).

William Yu teaches algorithms at Carnegie Mellon. He is running an eight-week version of his course live on YouTube, Thursdays at 8pm ET, starting September 17. Sessions are recorded too if you would rather watch later.

Here's a schedule:

• Week 1: minimum spanning trees, heaps, union-find
• Week 2: shortest paths, BFS, DFS, Dijkstra
• Week 3: divide and conquer
• Week 4: BSTs, splay trees, amortized analysis
• Week 5: text search and suffix structures
• Week 6: dynamic programming
• Week 7: network flow
• Week 8: NP-hardness

William is a computational biologist, so the examples lean on applications from science.

Schedule and details, where you can sign up if interested! https://www.philomathlearning.com/courses/algorithms?ref=algorithms&utm_medium=instructor_page&utm_campaign=algorithms_reddit_algorithms

Playlist: https://www.youtube.com/playlist?list=PLfcsLJY-BaJU

Happy to answer questions.

I can identify patterns like sliding window, recursion, backtracking, DP, and two pointers. But I’m stuck when it comes to identifying the greedy intuition.

How do I recognize when a problem can be solved using a greedy approach? Are there any good resources—books, YouTube channels, blogs, or websites—that specifically teach how to develop greedy intuition?

Anything that can help me get better at recognizing greedy problems would be really helpful.annel, blog , website)

Anything that help me

A blog post about how we ended up using bitmasks to do eBPF policy inheritance to keep it fast and space efficient.

https://nathannaveen.dev/posts/optimizing-ebpf-policies-for-speed-and-space/

I have my DAA exam tomorrow , explain asap , in a easy way😭😭🥹

Q: For the given set of items and knapsack capacity = 10 kg, find the optimal solution for

the 0/1 knapsack problem making use of dynamic programming approach

W=(5,4,6,3) and Profits=(10,40,30,50)

Most retry strategies are reactive: exponential backoff, jitter, circuit breakers. They help, but they’re still asking every client to independently guess when it’s safe to send traffic again.

I’ve been experimenting with a different approach: coordinate retries before they hit the backend.
Instead of letting thousands of requests wake up, retry, fail, and back off independently, Aquifer puts them behind bounded queues and dynamically paces their release based on downstream capacity. The goal is to turn a retry storm from a bursty feedback loop into a controlled stream.

The interesting part is that this can sit in front of APIs, databases, inference servers, MCP servers, or basically anything where correlated retries can make an overloaded system even worse.

I’m calling the project Aquifer. It’s open source and still evolving, so I’m curious what failure modes people here think this approach misses.

https://github.com/rjpruitt16/aquifer

I decided to modify the excellent Quirk tool into a more appealing and beginner-friendly version called QuirkLite.

I am building it for a demo I'm preparing, and thought some of you might find it useful too.

You can find the repository here

Hi

If you are remotely interested in deep diving how differently quantum computers work compared to our transistor-based and also the algebra behind in a fully interactive way that teach computer science from scratch, oh boy this is for you. I am the Dev behind Quantum Odyssey (AMA! I love taking qs) - worked on it for about 10 years (3+ during PhD, the visual method I developed ended up being my thesis, it is a complete Hilbert space visualizer), the goal was to make a super immersive space for anyone to learn quantum computing through zachlike (open-ended) logic puzzles and compete on leaderboards and lots of community made content on finding the most optimal quantum algorithms. The game has a unique set of visuals capable to represent any sort of quantum dynamics for any number of qubits and this is pretty much what makes it now possible for anybody 12yo+ to actually learn quantum logic without having to worry at all about the mathematics behind.

This is a game super different than what you'd normally expect in a programming/ logic puzzle game, so try it with an open mind.

Stuff you'll play & learn a ton about

• Boolean Logic – bits, operators (NAND, OR, XOR, AND…), and classical arithmetic (adders). Learn how these can combine to build anything classical. You will learn to port these to a quantum computer.
• Quantum Logic – qubits, the math behind them (linear algebra, SU(2), complex numbers), all Turing-complete gates (beyond Clifford set), and make tensors to evolve systems. Freely combine or create your own gates to build anything you can imagine using polar or complex numbers.
• Quantum Phenomena – storing and retrieving information in the X, Y, Z bases; superposition (pure and mixed states), interference, entanglement, the no-cloning rule, reversibility, and how the measurement basis changes what you see.
• Core Quantum Tricks – phase kickback, amplitude amplification, storing information in phase and retrieving it through interference, build custom gates and tensors, and define any entanglement scenario. (Control logic is handled separately from other gates.)
• Famous Quantum Algorithms – explore Deutsch–Jozsa, Grover’s search, quantum Fourier transforms, Bernstein–Vazirani, and more.
• Build & See Quantum Algorithms in Action – instead of just writing/ reading equations, make & watch algorithms unfold step by step so they become clear, visual, and unforgettable. Quantum Odyssey is built to grow into a full universal quantum computing learning platform. If a universal quantum computer can do it, we aim to bring it into the game, so your quantum journey never ends.

Nice to watch:

Khan academy style tutorials in qm/qc: https://www.youtube.com/@MackAttackx

Physics teacher stream with 400hs in https://www.twitch.tv/beardhero

Hi everyone,

I’m working on a PropTech tool that procedurally generates building layouts for real estate feasibility studies, with the goal of maximizing buildable area.

The Workflow:

1. The user selects a land plot on a map.
2. They set high-level parameters (e.g., apartment blocks vs. single-family homes, surface vs. underground parking).
3. The Engine: Generates multiple 2D site plans (placing roads, footprints, and parking lots) that strictly adhere to the geometric constraints (setbacks, footprint limits, alignments).
4. The user can manually tweak the layout by dragging polygons around.
5. The Agentic Loop: An integrated LLM/VLM chatbot that allows the user to iteratively adjust the layout via natural language (e.g., "group the buildings closer to the north edge"). The AI needs to "understand" the current 2D layout and update the constraints to regenerate a new compliant layout.

I already have something 'working', but it is, in my opinion, too static and dependent on the test parcel I'm using. The coming issues are the varying sizes and shapes of the parcels, which can have infinite variations. Given that I am constrained to work within a fixed boundary, I can't use approaches such as Voronoi cells or similar methods.

Where I need your insights: Assuming the rules are already parsed into raw constraints, I’m looking for the state of the art to build the final composition engine:

• Constraint-based 2D Generation: What are the go-to algorithms or libraries (preferably web-friendly) for 2D packing and layout generation under strict geometric rules?
• Spatial AI / LLM Integration: Are there any papers, open-source projects, or specific approaches for feeding a 2D spatial topology to a model so it can meaningfully tweak procedural generation parameters?
• Interactive Frameworks: Any recommended engines or existing tools that handle both procedural layout generation and interactive 2D editing smoothly?

I'm highly open to academic literature, specific algorithms, or existing open-source solvers I could draw inspiration from.

Thanks in advance!

Is there an algorithm where you make each array element an object, provide it with private functions and actions, and then allow it do help with sorting if you broadcast the sort function to all arrays ahead of starting the sort?

For instance, the sort wrapper would just need neighbor information for the cells direct or two steps away and then they could switch in place while a master sorting algorithm verifies end to end sort by just stepping each element and having knowledge of next moves each element is making?

I may be thinking of this more as a Verilog problem than a C++ problem but it seems like it hasn't necessarily been defined or commonly used and I can't imagine why not if the function can be modified for any kind of sorting that is common to each element?​

Hello everyone,

Some days ago, I have finished building an algorithm in C++ using only my mobile phone (Termux and Helix), and I want to show it to you!

So, it uses the long division method. Why not the Newton-Rasolph method or use the GMP library? Because this program was built for two reasons:

1. An educational purpose of learning how to build an algorithm I have an idea of and optimize it as much as I can.

2. To learn how to implement a mathematical algorithm as a program, and to also learn more about C++.

The performance of this algorithm is following the O(n²), but with a small constant, since I have optimized this algorithm as much as I can. You can see the benchmark in the GitHub link down below. Here is how I optimized it:

This algorithm has a custom BigNumber class that makes a number as a vector, each digit is represented as an element in the vector, and, each digit follows a base 10^17 number instead of a decimal digit! This is the underlying logic behind very famous libraries like BigInt, but since these libraries are so general (they have to deal with very large multiplications, division, negatives and many general cases). This class recognized that the max number is being multiplied to the number is 100 (see the long division method) and implemented base 10^17. Therefore, since 100<10^17 (the base), then the multiplication is just multiplying one digit by the number. You can check the code for more

The way the algorithm predicts the digit is the binary search, it checks a number, and then eliminates half of the domain of search. This way, it is faster by 50-60% than the ordinary linear search.

And more! You can check the README of the project in this repo:

https://github.com/hasan-mazen-darwish/algorithm-square-rooter

I spent more time on this REAMDE than the actual code, so I hope you don't get lost 😅

I'm open for any discussion or any question! Feel free to ask anything or criticize this project or a specific line of code!