Datastructures and Algorithms (at Amsterdam University College) 20172018
Lectures
regular lectures: Wan Fokkink (w.j.fokkink@vu.nl)
exercise classes: Petar Vukmirovic (petar.vukmirovic2@gmail.com)
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, AddisonWesley, 2004 (3rd ed)

Thomas Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science, AddisonWesley, 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
Slides
Copies of the slides
Written exams
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 and the second exam on December 19.
Programming assignments
There are two programming assignments, each making up 15% of the final mark.
The first programming assignment will be made available here on Monday September 25. The deadline for handing it in is Friday October 20 at 5pm.
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 p132133 (OrderofMagnitude Improvements) of Harel; Chapter 1.1 (Algorithms), 1.2 (Analyzing algorithms), 2 (Growth of Functions) of CormenLeisersonRivest
 Queues; Lists; Insertion sort; Selection sort
p1921 (Control Structures) and 2439 (from Diagrams for Algorithms up to Queues and Stacks) and 7075 (ObjectOriented Programming) of Harel; Chapter 11.1 (Stacks and queues), 11.2 (Linked lists) of CormenLeisersonRivest
 Bubble sort; Mergesort; Dynamic programming; 01 knapsack problem; Quicksort
p2124 (Bubblesort: An Example; The "Goto" Statement) and 8587 (DivideandConquer) of Harel; Chapter 1.3 (Designing algorithms), 8.1 (Description of quicksort), 8.2 (Performance of quicksort) of CormenLeisersonRivest
 Binary trees; Heaps; Heapsort; Counting sort; Radix sort
p3940 (Trees, or Hierarchies) and 9192 (Heaps and Getting Work Done on Time) and 143146 (AverageCase 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 CormenLeisersonRivest
 Binary search trees; AVL trees
p4043 and 133136 (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 CormenLeisersonRivest; Tutorial on AVL trees
 Hashing; Breadth and depthfirst search; Kosaraju's strongly connected components algorithm
Chapter 12 (Hash Tables), 23.2 (Breadthfirst search), 23.3 (Depthfirst search), 23.5 (Strongly connected components) of CormenLeisersonRivest
 Dijkstra's shortest path algorithm; BellmanFord shortest path algorithm; Prim's and Kruskal's minimum spanning tree algorithms; Greedy approach to 01 knapsack problem
p8791 (Greedy Algorithms and Railroad Contractors; Dynamic Programming and Weary Travelers) of Harel; Chapter 25.2 (Dijkstra's algorithm), 25.3 (The BellmanFord algorithm), 24 (Minimum Spanning Trees), 17.2 (Elements of the greedy strategy) of CormenLeisersonRivest
 Lecturefree week
 First exam
 Turing machines, ChurchTuring thesis, recursive languages
p219238 (Chapter 9, up to Universal Algorithms) of Harel
 Undecidability, halting problem, Post correspondence problem
p191218 (Chapter 8) of Harel
 Complexity classes P and NP, NPcompleteness, bounded tiling problem
p159186 (Chapter 7) of Harel
 Satisfiability problem, complexity classes coNP, PSpace and EXP
 Quantum computing
Sections 10.1, 10.2, 10.3.110.3.3 of Arora and Barak
 Simon's algorithm
Sections 10.3.4, 10.5 of Arora and Barak
 Second exam
Exercise classes:
 Exercise sheet 1
answers
 Exercise sheet 2
answers
 Exercise sheet 3
 Exercise sheet 4
 Exercise sheet 5
 Exercise sheet 6
 Exercise sheet 7
 Cancelled
 Cancelled
 Exercise sheet 8
 Exercise sheet 9
 Exercise sheet 10
 Exercise sheet 11
 Exercise sheet 12
 Exercise sheet 13
 Cancelled
Old exams: