Links
Course overview
Design and analysis of classic algorithms.
Main topics
- asymptotic notation, loop invariants, correctness, recurrence
- sorting & selection: insertion, merge, quick, heap, k-order statistics
- data structures: stacks, queues, linked lists, dictionaries, hash tables, binary search trees, red-black trees
- graph algorithms: representation of graphs, BFS, DFS, topological sort, stronlgy connected components, minimum spanning tree (Kruskal, Prim), shortest path (Dijkstra, Bellmann-Ford)
- divide-and-conquer, greedy algorithms, dynamic-programming
- complexity theory: decision problems, complexity classes, reductions, NP-hardness, NP-completeness