Basic Algorithms

Spring 2016 — CSCI-UA.0310-003

Lectures: Mon/Wed 2:00-3:15pm, room 101 WWH

Recitation: Mon 12:30-1:45pm, room 109 WWH

Midterm exam: Wed, March 23

Mailing List

Instructor: Victor Shoup

Recitation Leader: Abhinav Tamaskar <avt237@nyu.edu>

Grading: There will be a problem set roughly once every two weeks. There will be a midterm exam and a final exam. Final grades will be weighted as follows:

Text:

Topics:

Slides and notes:

  1. merge sort
  2. Code: sorting.c
  3. divide and conquer
  4. polynomials and the FFT
  5. division
  6. 2-3 trees
  7. priority queues
  8. dynamic programming
  9. greedy algorithms
  10. amortized analysis
  11. graphs
  12. graphs (SCCs)
  13. graphs (shortest paths)
  14. Demo: Bellman-Ford
  15. Demo: Acyclic
  16. Demo: Dijkstra
  17. graphs (all pairs shortest paths)
  18. graphs (MST)
  19. Demo: Prim
  20. Notes: Probability Primer
  21. probability
  22. selection
  23. Quick Sort
  24. Hashing (1)
  25. Hashing (2)
  26. Hashing (3)
  27. Hashing (4): cuckoo hashing
  28. NP completeness (1)
  29. NP completeness (2)
  30. NP completeness (3)
  31. NP completeness (4)

Problem Sets:

  1. Problem Set 1 (due Feb. 8)
  2. Problem Set 2 (due Feb. 17)
  3. Problem Set 3 (due Feb. 29)
  4. Problem Set 4 (due Mar. 9)
  5. Problem Set 5 (due Mar. 30)
  6. Problem Set 6 (due April 6)
  7. Problem Set 7 (due April 20)
  8. Problem Set 8 (due May 2)
  9. Problem Set 9 (due May 9)