Department of Computer Science and Technology

Algorithms 1

Course pages 2023–24

# Algorithms 1 & 2

Moodle

### Schedule

This is the planned lecture schedule. It will be updated as and when actual lectures deviate from schedule. Slides will be uploaded the night before a lecture.

 2. Sorting Lecture 01 [slides] 2.1 Insertsort Lecture 02 [slides] 2.3 Big-O notation 2.4 The cost of sorting 2.6–2.7 Binary insertsort, selectsort Lecture 03 [slides] 2.11 Quicksort 2.9 Mergesort 2.10 Heapsort Lecture 04 [slides] 2.14 Faster sorting: couting sort, bucket sort, radix sort 2.13 Stability Sorting algorithms compared 2.8 Bubblesort 2.12 Median and order statistics using quicksort Example sheet 1 [pdf] Compulsory tick: mergesort, due 5 Feb Optional: sortbound. Why doesn't the Ω(n log n) bound apply to countingsort? 3. Algorithm design Lecture 05 [slides] 3.1 Dynamic programming Lecture 06 [slides] Dynamic programming examples Lecture 07 [slides] 3.2 Greedy algorithms First half of example sheet 2 [pdf] Optional tick: huffman Compulsory tick: resalloc, due 19 Feb 4. Data structures (intro) Lecture 08 [slides] 4.1 Memory and pointers 4.1–4.2 List, tree, stack, queue, dictionary 4.7 Hash tables 4.9 Priority queues Rest of example sheet 2 [pdf] 5. Graphs and path finding Lecture 09 [slides] 5, 5.1 Graphs (14:27) 5.2 Depth-first search (11:37) 5.3 Breadth-first search (6:43) Lecture 10 [slides] 5.4 Dikstra's algorithm (15:25) plus proof (24:01) Lecture 11 [slides] 5.6 Bellman-Ford (12:13) Lecture 12 [slides] 5.7 Dynamic programming (13:06) 5.8 Johnson's algorithm (13:43) Example sheet 4 [pdf] Optional tick: bfs-all from ex4.q6 Optional challenge: chatgpt-bfs Optional assignment: grade-chatgpt Optional tick: bf-cycle from ex4.q19 6. Graphs and subgraphs Lecture 13 [slides] 6.1 Flow networks (9:31) 6.2 Ford-Fulkerson algorithm (21:55) Lecture 14 [slides] 6.3 Max-flow min-cut theorem (19:38) Lecture 15 [slides] 6.4 Matchings (11:01) 6.7 Topological sort (14:16) Lecture 16 [slides] Example sheet 5 [pdf] Compulsory tick: max-flow, due 11 March 7. Advanced data structures Lecture 16 (ctd) [slides] 7.1 Aggregate analysis (8:56) Lecture 17 [slides] 7.3 Amortization: definition (10:59) 7.4 Potential functions (14:17) Lecture 18 [slides] 4.7 Hash tables revisited 4.8 Binomial heap 7.5 Three priority queues (18:26) Lecture 19 [slides] 7.6 Fibonacci heap (18:13) Lecture 20 [slides] 7.8 (continued) 7.7 Implementing the Fibonacci heap 7.9 Disjoint sets (18:07) Lecture 21 [slides] Review of amortized analysis Example sheet 6 [pdf] Optional tick: dis-set from ex6.q12 Optional tick: fib-heap 4. Data structures (ctd) Lecture 21 ctd. [slides] 4.3 Binary search trees Lecture 22 [slides] 4.4 2-3-4 trees 4.6 B-trees Lecture 23 [slides] 4.5 Red-black trees Example sheet 3 [pdf] Epilog Lecture 24 [slides] What's examinable Proof by induction / bfs-all challenge