Marcin Sydow - Algorithms and Data Structures - Course Web Page

• "Introduction to Algorithms" (CLRS), T.Cormen et al., 3rd edition, MIT Press, 2009
• "Algorytmy i struktury danych" (BDR), (in Polish) L.Banachowski, K.Diks, W.Rytter, WNT 2001
• "Algorithms and Datastructures. The Basic Toolbox" (MS), K.Mehlhorn P.Sanders, Springer 2008
• "Algorithm Desing" (KT), J.Kleinberg E.Tardos, Pearson 2006

1. "Correctness of Algorithms" - Introduction, Algorithm Specification and Verification.
2. "Complexity of Algorithms" - Time and space complexity. Asymptotic notation (O,o,Omega,omega,Theta)
3. "Searching" Searching in unsorted and sorted sequences. K-skip algorithm. "Divide and Conquer". Binary Search Algorithm. Positional Statisitcs. "Tournament" Algorithm. Hoare's Algorithm (idea).
4. "Sorting 1" The role of sorting. Selection Sort, Insertion Sort, Merge Sort.
5. "Sorting 2" Quick Sort. Lower Bound for comparison-based sorting. Count Sort. Radix Sort
6. "Recursion" Recursive algorithms. Solving recursive equations. Quick Sort average complexity proof (BDR). Master Theorem (CLRS)
7. Colloquium 1 (searching + sorting)
8. "Basic Data Structures" Representation of sequences: linked lists, arrays, dynamic arrays, etc. Abstract Data Structures. Examples: Stack, Queue, Deque. Amortised complexity analysis: "Potential" method, etc. (lecture based on chapter 3 of (MS))
9. "Priority Queues" Priority Queue. Binary Heap. Heapsort and Other Applications. Exensions: Addressable and Mergeable Priority Queues. Binomial Heap.
10. "Dictionaries" Dictionary. Hashing. Ordered Dictionary. BST, AVL, self-organising BST.
11. "Basic Graph Algorithms" Reminder of basic graphs/trees definitions. Graph Representations. Recursive traversals of rooted trees. General graph traversals: BFS and DFS with applications.
12. Colloquium 2
13. "Shortest Paths" Properties of Shortest Paths. Relaxation and its properties. Single Source Shortest Paths (case 1: DAG, case 2: non-negative weights (Dijkstra's alg.), case 3: arbitrary weights (Bellman-Ford's alg.)), All-Pairs Shortest Paths
14. "Minimum Spanning Tree" Definition. Cut and Cycle property. Prim's and Kruskal's algorithms. Union-Find abstract data structure
15. (optional) Retake of Colloquium 1 or 2