General Information
Goals
- Understanding the relationship between algorithm design, correctness proof and complexity analysis.
- Learning algorithmic techniques of general applicability.
- Knowing some major algorithms in a few common domains.
- Practical experience in applying generic algorithms to specific problems
Syllabus
Note: this is still a draft overview version of the syllabus
- Program Correctness
- Concept of loop Invariants
- Using invariants do prove and to design algorithms
- Asymptotic Analysis
- Fundamentals
- Notation
- Cycles and summations
- Divide-and-Conquer Design Pattern
- Solving recurrences (unrolling, substitution, recursion tree, master formula))
- Amortized Analysis
- Examples of usage
- Aggregation, accounting and potential methods
- Probabilistic Analysis
- Average-case analysis
- Randomized algorithms
- Revisiting sorting and selection
- Sorting/order concepts
- Bucket sort and radix sort
- Quickselect
- Dynamic Programming
- Optimal substructure and overlapping subproblems
- Top-down (memoization) and bottom-up strategies
- Some easy, medium and more advanced examples
- String Algorithms
- String Matching (Knut-Morris-Pratt, Rabin-Karp, ...)
- Tries and Suffix Trees/Arrays
- Some more possible selected topics
- Universal and perfect hashing
- Balanced search trees
- Introduction to the theory of NP-completeness
)