Back to Exams Dashboard
Module Information
Module
- 10 CATS
- Required core
- Module Link
Exam
- Summer Exam
- 80%
Topics
- Big-O Notation
- Worst-Case asymptotic running time
- Bubble Sort
- Merge Sort
- Master Theorem
- Generating Function for Recurrence Relations
- Quick Sort
- Probability Space
- Conditional Probability, Independence
- Random Variable (coupon collector’s problem)
- Expectation and Variance (infinite monkey problem)
- Conditional Expectation (coupon collector’s problem)
- Markov’s Inequality
- Chebyshev’s inequality
- Analysis of randomized quick sort
- Pigeonhole Principle
- Hall’s theorem
- Graph Theory
- Eulerian Graphs
- Trees
- Bipartite Graphs
- Maximum Matchings and Minimum Vertex Covers
- König-Egerváry Theorem and Hall’s theorem
- The Probabilistic Method and Cuts in Graphs
- Ramsey Theory