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)
- Telescoping
- Combinatorics
- Rule of sums, rule of products
- Combinations, permutations
- Binomial theorem
- Combinatorial argument
- Proofs (correctness, termination)
- Direct proof
- Proof by contradiction
- Proof by induction (weak, strong)
- Recurrence relation
- Probability
- 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
- Asymptotic notation (big-O, big-Ω, big-Θ)
- Data structures
- Array, dynamic array, linked list
- Binary tree
- Heap
- Hash table
- Hash function
- Hash collision (chaining, open addressing)
- Abstract data types (ADT)
- Graph theory
- Trees
- Traversal algorithms
- Sorting algorithm
- Comparison-based sorting algorithms
- Counting sort
- 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
- NP-completeness