ECE345 — Algorithms and Data Structures

Course focuses on the design and analysis of algorithms and data structures. Traditionally a pre-requisite to do anything in software engineering. Follows ECE244 — Programming Fundamentals and ECE297 — Software Design and Communication.

We used the Introduction to Algorithms textbook by Cormen, Leiserson, Rivest, and Stein (CLRS).

Concepts covered

• Discrete mathematics
  • Logarithms and exponents
  • Fibonacci numbers
  • Summation
    • Sequence and series (arithmetic, geometric, infinite geometric)
  • Combinatorics
    • Rule of sums, rule of products
    • Combinations, permutations
    • Binomial theorem
    • Combinatorial argument
  • Proofs (correctness, termination)
    • Direct proof
    • Contradiction
    • Induction (weak, strong, structural)
    • Axiom
    • Theorem
  • Recurrence relation
    • Master theorem
    • Recursion tree method
    • Substitution method
  • Probability
    • Conditional probability (Bayes’ theorem)
• Algorithmic analysis
  • Asymptotic notation (big-O, big-Ω, big-Θ)
    • Time complexity
    • Space complexity
    • Limit method
    • L’Hôpital’s rule
  • Algorithmic analysis (best case, worst case, average/expected case)
  • Deterministic, probabilistic algorithms
• Data structures
  • Array, dynamic array, linked list
  • Binary tree
    • Binary search tree
    • Red-black tree
    • AVL tree
  • Heap
  • Hash table
    • Hash function
    • Hash collision (chaining, open addressing)
• Abstract data types (ADT)
  • Stack, queue
  • Priority queue
  • Dictionary
• Sorting algorithm
  • Comparison-based sorting algorithms
    • Mergesort
    • Quicksort
    • Heapsort
    • Lower bound running time theorem
  • Counting sort
    • Prefix sum
  • Radix sort
• Dynamic programming
  • Optimal substructure
  • Longest common sub-sequence
  • Knapsack problem (take/leave variant)
• Greedy algorithm
  • Optimal substructure
  • Knapsack problem (fractional variant)
  • Huffman compression
• Amortised analysis
  • Aggregate method
  • Accounting method
  • Splay tree
  • Skewed heap
• Graph theory
  • Trees
    • Binary tree
    • Decision tree
    • Threaded tree
    • Splay tree
  • Traversal algorithms
    • Breadth-first search
    • Depth-first search
  • Topological sort
  • Minimum spanning tree
    • Prim’s algorithm
  • Shortest path
    • Dijkstra’s algorithm
    • Bellman-Ford algorithm
  • Maximum flow
    • Ford-Fulkerson algorithm
    • Edmonds-Karp algorithm
    • Maximum bipartite matching
• Integer programming
  • Difference constraints
• Theory of computation
  • Finite state automata (DFAs)
  • Formal language
  • Turing machine
    • Church-Turing thesis
    • Decidability
    • Halting (accept, reject states)
  • Gödel’s completeness theorem
  • Computational complexity theory
    • $P$, $NP$
• NP-completeness
  • Intractability
  • Cook-Levin theorem
  • NP-completeness proof

Extra notes

• Algpseudocodex LaTeX package
• CLRS homework solutions
• Blockchain
  • Surveillance capitalism
  • Cryptography
• Approximation algorithm