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
Revised 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 / November 3 and the second exam on December 19.
Programming assignments
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 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
 Cancelled
 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, branchandbound method, 01 knapsack problem revisited
 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
 Cancelled
Exercise classes:
 Exercise sheet 1
answers
 Exercise sheet 2
answers
 Exercise sheet 3
answers
 Exercise sheet 4
answers
 Exercise sheet 5
answers
 Exercise sheet 6
answers
 Exercise sheet 7
answers
 Cancelled
 First exam
 Exercise sheet 8
answers
 Exercise sheet 9
answers
 Exercise sheet 10
 Exercise sheet 11
 Exercise sheet 12
 Second exam (instead of Exercise sheet 13)
 Cancelled
Old exams: