StudiousStart free

16 units · 63 lessons

Design and Analysis of Algorithms

Design and Analysis of Algorithms from the first idea to exam level: every lesson builds on the one before, with a worked example, a step-through diagram where it helps, a quick check and practice that adapts to what you know. Follows Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th ed. (with Levitin's Design & Analysis of Algorithms).

Design and Analysis of Algorithms at a glance

What does Design and Analysis of Algorithms cover?

Algorithm Analysis, Asymptotic Notation, Recurrences, Divide & Conquer, Sorting & Lower Bounds, Greedy Algorithms, Dynamic Programming, Graph Traversal, Minimum Spanning Trees, Shortest Paths, Backtracking & Branch and Bound, String Matching and NP-Completeness. It follows Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th ed. (with Levitin's Design & Analysis of Algorithms).

How many lessons does the Design and Analysis of Algorithms course on Studious have?

16 units and 63 lessons, from "Algorithms and correctness with loop invariants" to "Approximation algorithms". Each lesson has a worked example, a quick check and practice that adapts to what you know, and many have step-by-step diagrams.

Course outline

  1. Unit 1 · Week 1

    Algorithms and Their Analysis

    1. Algorithms and correctness with loop invariants
    2. The RAM model and counting steps
    3. Best, worst and average case of insertion sort
    4. Analysing loops: nested, halving and doubling
  2. Unit 2 · Week 2

    Asymptotic Notation

    1. Big-O: upper bounds
    2. Big-Ω and Big-Θ
    3. Little-o, little-ω and the limit test
    4. Ordering growth rates
  3. Unit 3 · Week 3

    Recurrences

    1. Recurrences from recursive code
    2. The substitution method
    3. The recursion-tree method
    4. The master theorem
  4. Unit 4 · Week 4

    Divide and Conquer

    1. The divide-and-conquer pattern and binary search
    2. Merge sort
    3. Maximum subarray
    4. Karatsuba and Strassen multiplication
  5. Unit 5 · Week 5

    Quicksort and Selection

    1. Partitioning: Lomuto and Hoare
    2. Quicksort's best, worst and average case
    3. Randomized quicksort
    4. Quickselect and order statistics
  6. Unit 6 · Week 6

    Heaps and Heapsort

    1. Binary heaps and max-heapify
    2. Building a heap in linear time
    3. Heapsort
    4. Priority queues
  7. Unit 7 · Week 7

    Sorting in Linear Time

    1. The Ω(n log n) lower bound for comparison sorts
    2. Counting sort
    3. Radix sort
    4. Bucket sort
  8. Unit 8 · Week 8

    Greedy Algorithms

    1. The greedy choice and optimal substructure
    2. Activity selection
    3. Fractional knapsack
    4. Huffman coding
    5. Coin change and where greedy fails
  9. Unit 9 · Week 9

    Dynamic Programming I

    1. Memoization and tabulation
    2. Rod cutting
    3. 0/1 knapsack
    4. Coin change with dynamic programming
  10. Unit 10 · Week 10

    Dynamic Programming II

    1. Longest common subsequence
    2. Edit distance
    3. Matrix-chain multiplication
    4. Longest increasing subsequence
  11. Unit 11 · Week 11

    Graphs and Traversal

    1. Representing graphs
    2. Breadth-first search
    3. Depth-first search and edge types
    4. Topological sort
    5. Strongly connected components
  12. Unit 12 · Week 12

    Minimum Spanning Trees

    1. Spanning trees and the cut property
    2. Kruskal's algorithm and union–find
    3. Prim's algorithm
  13. Unit 13 · Week 13

    Shortest Paths

    1. Single-source shortest paths and relaxation
    2. Dijkstra's algorithm
    3. Bellman–Ford and negative cycles
    4. Floyd–Warshall for all pairs
  14. Unit 14 · Week 14

    Backtracking and Branch and Bound

    1. Backtracking and the N-Queens problem
    2. Subset sum and graph colouring
    3. Branch and bound for 0/1 knapsack
  15. Unit 15 · Week 15

    String Matching

    1. Naive string matching
    2. Rabin–Karp
    3. Knuth–Morris–Pratt
  16. Unit 16 · Week 16

    NP-Completeness

    1. P, NP and decision problems
    2. Polynomial-time reductions
    3. NP-complete problems: SAT to vertex cover
    4. Approximation algorithms

Study every lesson with diagrams, practice and Buddy, your AI tutor.

Start studying free