Datastructures and Algorithms (at Amsterdam University College) 2017-2018

Lectures

regular lectures: Wan Fokkink (w.j.fokkink@vu.nl)

exercise classes: Petar Vukmirovic (petar.vukmirovic2@gmail.com)

Recommended reading material

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:

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. Lecture-free week
  9. First exam
  10. Turing machines, Church-Turing thesis, recursive languages
    p219-238 (Chapter 9, up to Universal Algorithms) of Harel
  11. Undecidability, halting problem, Post correspondence problem
    p191-218 (Chapter 8) of Harel
  12. Complexity classes P and NP, NP-completeness, bounded tiling problem
    p159-186 (Chapter 7) of Harel
  13. Satisfiability problem, complexity classes co-NP, PSpace and EXP
  14. Quantum computing
    Sections 10.1, 10.2, 10.3.1-10.3.3 of Arora and Barak
  15. Simon's algorithm
    Sections 10.3.4, 10.5 of Arora and Barak
  16. Second exam

Exercise classes:

  1. Exercise sheet 1
    answers
  2. Exercise sheet 2
    answers
  3. Exercise sheet 3
  4. Exercise sheet 4
  5. Exercise sheet 5
  6. Exercise sheet 6
  7. Exercise sheet 7
  8. Cancelled
  9. Cancelled
  10. Exercise sheet 8
  11. Exercise sheet 9
  12. Exercise sheet 10
  13. Exercise sheet 11
  14. Exercise sheet 12
  15. Exercise sheet 13
  16. Cancelled

Old exams: