Algorithms

What this covers

• Asymptotic analysis: proving O, Ω, and Θ bounds from the definitions, and analyzing nested loops and recursive calls rather than pattern-matching from memory
• Solving recurrences with recursion trees, substitution, and the Master Theorem — including recognizing which cases the Master Theorem does not cover
• Correctness proofs: loop invariants for iterative algorithms, induction for recursive ones, and exchange arguments for greedy choices
• Dynamic programming from scratch: defining the subproblem, writing the recurrence, identifying the ordering, and reconstructing the solution (LCS, knapsack, edit distance, interval scheduling)
• Graph algorithms and why they work: BFS/DFS structure, topological order, Dijkstra's greedy invariant, Bellman-Ford with negative edges, MST via Kruskal and Prim
• Reductions and a first pass at P, NP, and NP-completeness — what a polynomial-time reduction actually shows about relative hardness

Where learners get stuck

Treating big-O as "the running time" instead of an upper bound, so Θ, Ω, and worst-versus-average case get blurred together

Intro courses use big-O casually in conversation, so students absorb it as a synonym for runtime. Then an exam asks for a tight bound or a lower bound on the best case and the informal habit produces confident wrong answers.

Writing a recursive solution with memoization and assuming the analysis is done, without counting distinct subproblems times work per subproblem

The code works, which feels like success. But DP runtime comes from the size of the subproblem space, and students who never draw that space cannot explain why knapsack is pseudo-polynomial or why adding a dimension changes the bound.

Believing a greedy algorithm is correct because it passed the examples in lecture, and not being able to construct a counterexample when it is wrong

Greedy proofs (exchange arguments, staying-ahead) are the least algorithmic part of the course — there is no template. Students skip them, then cannot tell whether Dijkstra fails on negative edges or why interval scheduling by earliest finish time is optimal but earliest start time is not.

What a session looks like

A typical session starts with you explaining a problem or a graded question in your own words while I listen for the gap. From there we usually pick one algorithm and take it apart: state the invariant, argue the induction step, then count the work. For dynamic programming problems I will make you say the subproblem definition before any code exists, because that is where most attempts break. Expect to be asked "what input would break this?" often. Diagrams, recursion trees, and pseudocode can be shared on screen; the reasoning happens out loud.

Helpful to know first

• Programming fluency in one language (Python, Java, or C++) — writing and tracing recursive functions without reference
• Familiarity with arrays, linked lists, stacks, queues, hash tables, trees, and heaps, including their operation costs
• Basic discrete math: induction, summations, logarithm and exponent rules, set and graph notation
• Comfort reading pseudocode, since most algorithms texts and lectures present algorithms this way

Questions

What is the difference between an algorithms course and the data structures course I already took?

Data structures focuses on how to build and use containers and what their operations cost. Algorithms focuses on design paradigms and proof: given a problem, which technique applies, why is the resulting method correct, and what is its asymptotic complexity. You will use the structures you already know as tools rather than studying their implementations.

I can code the solution but I lose points on the proof and analysis. Can that be fixed?

Yes, and it is the most common reason students come to this topic. Proof writing here follows a small number of recurring shapes — loop invariant, induction on input size, exchange argument, cut-and-paste for optimal substructure. Sessions drill those shapes on problems you are already working on until the structure becomes automatic.

Do I need to be good at math for this?

You need induction, summations, and logarithm manipulation more than calculus. If recurrence solving or asymptotic algebra is the sticking point, we can work through those directly rather than assuming them.

Can we work on my actual homework problems?

We can work through problems you bring, focusing on method and reasoning so you can produce the write-up yourself. If your course has a collaboration policy on graded work, follow it — the sessions are most useful on past problem sets, practice exams, and textbook exercises.