Midterm · 2 Nov

Design & Analysis
of Algorithms

CS332 notes rebuilt for beginners: plain-word explanations, hand traces, hidden answers and timed mock exams. Pick a mode, learn it, then prove it without hints.

Start with Topic 0 Take a mock exam

Pick how you learn today

Every topic page has these four tabs. The one you choose stays selected on every page.

Visual
Trace tables, diagrams and step-by-step pictures.
Worked example
One problem solved slowly, then the rule.
Guided questions
Work it out yourself, with hidden hints.
Explanation & drill
A straight explanation, then practice.

Nine topics. One midterm.

0Oct 12–17
Math toolkit: logs, exponents, sums
Logs, exponents, floors and the sums you will meet in every analysis.
1Oct 12–17
What an algorithm is & counting its steps
What makes something an algorithm, and how to count the steps it takes.
2Oct 12–17
Proof techniques
Direct proof, contradiction, contrapositive and induction, with fill-in skeletons.
3Oct 12–17
Correctness: loop invariants, pre/postconditions
Loop invariants: initialization, maintenance, termination.
4Oct 18–24
Insertion sort
Trace it, prove it correct, and count its best and worst cases.
5Oct 18–24
Loop-analysis rules & space complexity
Quick rules for nested and halving loops, plus how much memory an algorithm uses.
6Oct 18–24
Asymptotic notation: O, Ω, Θ
Big-O, Omega and Theta: choosing c and n0 and writing the proof.
7Oct 25–29
Divide & conquer + merge sort
Split, solve, combine: merge sort traced and analysed.
8Oct 25–29
Recurrences: recursion trees & guess-and-verify
Solve T(n) by expansion, recursion trees and substitution.

The toolbox

Cheatsheet
Every formula on one page
Which technique?
Read a question, pick the method
My mistakes
Never repeat an error
Flashcards
70 cards: flip them here or import into Anki

Notes are written in our own words with original examples, citing the lecture slides and CLRS 4e. The original slides and book are not in this site.