COMP90077 Advanced Algorithms and Data Structures
Does any resource help with this course?
- Algorithm Design by Kleinberg and Tardos
- Algorithms by Jeff Erickson
- Linear Programming
- Design of Approximation Algorithms
What is this course about?
This course is an introduction to advanced algorithms and data structures for engineering students. The first part of the course covers advanced data structures, including treap, amortised analysis, quake heap, splay tree, hashing, range tree, and min cut/max flow. The second part of the course covers advanced algorithms, including linear programming, vertex cover, set cover, factor-x approximation, and duality.
The course covers the following topics:
- Treap
- tree + heap
- Amortised Analysis
- always have balance
- prepaid
- potential
- Quake Heap
- x tournament trees
- Splay Tree
- splay after every operation
- practical somehow
- Hashing
- usually static/fixed size
- perfect hashing: two-level hashing ensuring no collision
- cuckoo hashing: x hash functions, allowing insertion
- Range Tree
- multidimensional sort
- Min Cut/Max Flow
- adjacency list
- union find
- matching
- bipartite graph
- Linear Programming
- given a set of linear inequalities, find the maximum/minimum value of a linear function
- vertex cover
- set cover
- factor-x approximation
- duality