CS381 Introduction to the Analysis of Algorithms

Tu/Th 12:00-1:15 pm, Beering Hall of Lib Arts & Ed 2280

Course staff

Instructor:

Elena Grigorescu, elena-g purdue.edu

Office Hours: Mon 11am-12 LWSN 1209.

TA: Nabeel Butt, butt purdue.edu.

Office Hours: Tue 1:30-2:30pm LWSN 1168,
Thr 10-11am LWSN 3162

TA: Akash Kumar, akumar purdue.edu .

Office Hours: Wed 3-4pm LWSN 1168
Fri 10:30-11:30pm in LWSN 3162

(Check exceptions on piazza)

Announcements

HW 2 posted on Blackboard

Elena's and Nabeel's office hours have been slightly modified.

HW 1 posted on Blackboard.

Welcome to CS 381!

Texts
  • Intro to algorithms

    T. Cormen, C.Leiserson, R. Rivest, C. Stein. 3rd edition. MIT

  • Recommended: Algorithm design

    J. Kleinberg, E. Tardos. Pearson Education.

Class websites

Blackboard for assigned homework and grades.

Piazza for class discussions.

Course description
The course gives a broad introduction to the design and analysis of algorithms. A tentative list of topics includes: sorting and order statistics; common algorithm design techniques including divide-and-conquer, dynamic programming, and greedy; design and use of data structures; lower bound techniques, graph algorithms, NP-completeness, randomized algorithms, approximation algorithms.

Prerequisites: CS 251, CS 172.

Grading
  • 15% homeworks (biweekly Psets)
  • 15% quizzes (possibly unannounced, expect biweekly)
  • 35% midterm
  • 35% final.
Schedule
  • Aug. 26 Lecture 1. Course intro. Review insertion sort, induction. Book Appendix A, B. Chaps 1-2.2 Notes on induction/proofs
  • Aug. 28Lecture 2. Asymptotic notation. Divide and conquer. Merge sort. Book 2.3, 3, 4.3, 4.4. HW1 out
  • Sep. 2 Lecture 3. Recurrences. Induction, substitution methods. Book 4.3.
  • Sep 4 Lecture 4. Quiz 1. Counting inversions slides, demo. Max subsequence Book 4.1.
  • Sep. 9 Lecture 5. Max subarray problem. Master theorem. Book 4.1, 4.5, 4.6
  • Sep. 11 Lecture 6. Quick sort. Randomized quicksort. Book Chap 7. Appendix C
  • Sep. 16 Lecture 7. Median and order statistics.Chap 9. HW2 out. Optional reading: new result.
  • Sep. 18 Lecture 8. Hashing Book 11.1-11.4
  • Sep. 23 Lecture 9. Search trees Chap 12-13
  • Sep. 25 Lecture 10. Augmenting data structures Chap 14. Quiz 2. Practice exam out.
  • Sep. 30 Lecture 11. Amortized analysis. Chap 17. HW 3 out.
  • Oct 2 Lecture 12. Review for the midterm
  • Oct 6 Monday! MIDTERM 8-10pm SMTH 108
  • Oct. 7 Lecture 13. Dynamic programming. Fibonacci Notes Jeff Erickson. Weighted interval scheduling Kleinberg-Tardos chapter
  • Oct. 9 Lecture 14. Dynamic programming. Longest common subsequence. Edit distance. Chap 15.
  • Oct. 14 Lecture 15. October break
  • Oct. 16 Lecture 16. Dynamic programming. Subset-sum. Knapsack. HW 4 out.
  • Oct. 21 Lecture 17. Greedy. Scheduling problems Chap 16
  • Oct. 23 Lecture 18. Greedy. Graph algorithms. Shortest path.Chap 22, 24, Quiz 3.
  • Oct. 35 Lecture 19. DP. Shortest path. Chap 24
  • Oct. 30 Lecture 20. Minimum spanning trees Chap 23, HW 5 out
  • Nov 4 Lecture 21 Topological sort Chap 22
  • Nov 6 Lecture 21 Data compression. Chap 16.3. Quiz 4
  • Nov. 11 Lecture 22 Max flow-min cut Chap 26
  • Nov. 13 Lecture 23 Max flow. Capacity scaling
  • Nov. 18 Lecture 24 Max flow. Applications HW 5 out
  • Nov. 20 Lecture 25 NP completeness. Intro.
  • Nov. 25 Lecture 26 Cancelled- Makeup for the evening midterm
  • Nov. 27 Lecture 27 Thanksgiving. No Class
  • Dec 2 Lecture 28 NP completeness. Reductions HW 7 out
  • Dec. 4 Lecture 29 NP completness Quiz 5
  • Dec. 9 Lecture 30 NP completeness. Approximation/Randomized algorithms
  • Dec. 11 Lecture 31 Review
  • Dec. 16 Lecture 32 FINAL EXAM 7:00p - 9:00p MTHW 210