Datastructures and Algorithms (at Amsterdam University College) 2017-2018
regular lectures: Wan Fokkink (email@example.com)
exercise classes: Petar Vukmirovic (firstname.lastname@example.org)
Recommended reading material
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, MIT Press, 1990
David Harel, Algorithmics: The Spirit of Computing, Addison-Wesley, 2004 (3rd ed)
Thomas Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science, Addison-Wesley, 2006 (3rd ed)
in particular Chapters 8 (Turing machines), 12 (undecidability) and 15 (P, NP and Cook's Theorem)
H 10.1, 10.2, 10.3, 10.5, 10.7 (quantum computing) from Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, draft version from 2007
Revised copies of the slides
There are two written exams, each making up 35% of the final mark. At these exams, you are allowed to use copies of the slides (hard copies or on a laptop).
The first exam will be on October 31 / November 3 and the second exam on December 19.
There are two programming assignments, each making up 15% of the final mark.
First programming assignment, deadline Friday October 20, 5 PM.
Two test cases: The first test case should produce B, whereas the second test case should produce A.
NEW Second programming assignment, deadline Friday December 15, 5 PM.
NEW Five test cases: A zipped directory with five test cases and their outputs.
Passing the course
To pass the course, an overall passing mark suffices. That is, it is not a requirement that all four individual parts have a passing mark.
Schedule per lecture:
- Introduction; Big O; Pseudocode; Stacks
Chapter 1 and p132-133 (Order-of-Magnitude Improvements) of Harel; Chapter 1.1 (Algorithms), 1.2 (Analyzing algorithms), 2 (Growth of Functions) of Cormen-Leiserson-Rivest
- Queues; Lists; Insertion sort; Selection sort
p19-21 (Control Structures) and 24-39 (from Diagrams for Algorithms up to Queues and Stacks) and 70-75 (Object-Oriented Programming) of Harel; Chapter 11.1 (Stacks and queues), 11.2 (Linked lists) of Cormen-Leiserson-Rivest
- Bubble sort; Mergesort; Dynamic programming; 0-1 knapsack problem; Quicksort
p21-24 (Bubblesort: An Example; The "Goto" Statement) and 85-87 (Divide-and-Conquer) of Harel; Chapter 1.3 (Designing algorithms), 8.1 (Description of quicksort), 8.2 (Performance of quicksort) of Cormen-Leiserson-Rivest
- Binary trees; Heaps; Heapsort; Counting sort; Radix sort
p39-40 (Trees, or Hierarchies) and 91-92 (Heaps and Getting Work Done on Time) and 143-146 (Average-Case Complexity; Upper and Lower Bounds) of Harel; 5.5 (Trees), 7.1 (Heaps), 7.2 (Maintaining the heap property), 7.3 (Building a heap), 7.4 (The heapsort algorithm), Chapter 9.2 (Counting sort), 9.3 (Radix sort) of Cormen-Leiserson-Rivest
- Binary search trees; AVL trees
p40-43 and 133-136 (Treesort: An Example) of Harel; Chapter 13.1 (What is a binary search tree?), 13.2 (Querying a binary search tree), 13.3 (Insertion and deletion) of Cormen-Leiserson-Rivest; Tutorial on AVL trees
- Hashing; Breadth- and depth-first search; Kosaraju's strongly connected components algorithm
Chapter 12 (Hash Tables), 23.2 (Breadth-first search), 23.3 (Depth-first search), 23.5 (Strongly connected components) of Cormen-Leiserson-Rivest
- Dijkstra's shortest path algorithm; Bellman-Ford shortest path algorithm; Prim's and Kruskal's minimum spanning tree algorithms; Greedy approach to 0-1 knapsack problem
p87-91 (Greedy Algorithms and Railroad Contractors; Dynamic Programming and Weary Travelers) of Harel; Chapter 25.2 (Dijkstra's algorithm), 25.3 (The Bellman-Ford algorithm), 24 (Minimum Spanning Trees), 17.2 (Elements of the greedy strategy) of Cormen-Leiserson-Rivest
- Lecture-free week
- Turing machines, Church-Turing thesis, recursive languages
p219-238 (Chapter 9, up to Universal Algorithms) of Harel
- Undecidability, halting problem, Post correspondence problem
p191-218 (Chapter 8) of Harel
- Complexity classes P and NP, NP-completeness, bounded tiling problem
p159-186 (Chapter 7) of Harel
- Satisfiability problem, branch-and-bound method, 0-1 knapsack problem revisited
- Quantum computing
Sections 10.1, 10.2, 10.3.1-10.3.3 of Arora and Barak
- Simon's algorithm
Sections 10.3.4, 10.5 of Arora and Barak
- Exercise sheet 1
- Exercise sheet 2
- Exercise sheet 3
- Exercise sheet 4
- Exercise sheet 5
- Exercise sheet 6
- Exercise sheet 7
- First exam
- Exercise sheet 8
- Exercise sheet 9
- Exercise sheet 10
- Exercise sheet 11
- Exercise sheet 12
- Second exam (instead of Exercise sheet 13)