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

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:

  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. Cancelled
  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, branch-and-bound method, 0-1 knapsack problem revisited
  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. Cancelled

Exercise classes:

  1. Exercise sheet 1
    answers
  2. Exercise sheet 2
    answers
  3. Exercise sheet 3
    answers
  4. Exercise sheet 4
    answers
  5. Exercise sheet 5
    answers
  6. Exercise sheet 6
    answers
  7. Exercise sheet 7
    answers
  8. Cancelled
  9. First exam
  10. Exercise sheet 8
    answers
  11. Exercise sheet 9
    answers
  12. Exercise sheet 10
  13. Exercise sheet 11
  14. Exercise sheet 12
  15. Second exam (instead of Exercise sheet 13)
  16. Cancelled

Old exams: