CS381 Introduction to the Analysis of Algorithms

Tu/Th 10:30 am - 11:45 am Wetherill Lab of Chemistry 172

Course staff

Instructor:

Elena Grigorescu, elena-g@purdue.edu

Office Hours: Tue 1-2pm LWSN 1209.


Graduate TAs:

  • Tatiana Kuznetsova (head TA)
    tkuznets@purdue.edu,
    Office Hours: Wed 10:30-12, HAAS G50;
  • Anudeep Reddy Dwaram,
    adwaram@purdue.edu,
    Office Hours: Thr 3-4:30, HAAS G50;
  • Young-San Lin,
    lin532@purdue.edu,
    Office Hours: Mon 4-5:30; HAAS G50
  • Runzhi Yang,
    yang1492@purdue.edu,
    Office Hours: Wed 4:30-6; HAAS G50.

Undergraduate TAs:

  • Ryan Davis,
    davis791@purdue.edu,
    Office Hours: Mon 1:30-3:30, HAAS G50
  • Shubhang Kulkarni,
    kulkar17@purdue.edu,
    Office Hours: Fri 10:30-12:30, HAAS G50.

(Check exceptions on piazza)

Announcements

Welcome to CS 381!

Texts
  • Algorithm design

    J. Kleinberg, E. Tardos. Pearson Education.

  • Intro to algorithms

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

LaTeX resources
  • Check here for pointers on LaTeX.
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; flows and cuts; lower bound techniques; graph algorithms; NP-completeness; randomized algorithms; approximation algorithms.

Prerequisites: CS 251, CS 172.

Grading
  • 20% homeworks
  • 10% quizzes (possibly unannounced, lowest score will be dropped)
  • 20% for each midterm
  • 30% final.
Schedule (tentative)
(two lectures will be cancelled to make-up for the evening exams)

  • Jan. 9 Lecture 1. Course intro. Review insertion sort, induction. Notes on induction/proofs
  • Jan. 11Lecture 2. Asymptotic notation. Divide and conquer. Merge sort. HW1 out
  • Jan. 16 Lecture 3. Solving Recurrences.
  • Jan 18 Lecture 4. Master theorem
  • Jan. 23 Lecture 5. Counting inversions. Max subarray problem.
  • Jan. 25 Lecture 6. Quicksort.
  • Jan 30 Lecture 7. Median and order statistics.
  • Feb 1 Lecture 8. Closest pair in 2D
  • Feb. 6 Lecture 9 Matrix multiplication and EVENING MIDTERM 8:00p - 9:00p PHYS 112
  • Feb 8 Lecture 10. Intro to dynamic programming
  • Feb. 13 Lecture 11. DP: Interval partitioning
  • Feb 15 CANCELLED.
  • Feb 20 Lecture 12 DP: Longest Common Subsequence
  • Feb. 22 Lecture 13. DP: Alignment problems
  • Mar. 1 Lecture 15.
  • Mar. 6 Lecture 16.
  • Mar. 8 Lecture 17. Quiz
  • Mar. 13 Lecture 18. Spring Break
  • Mar. 15 Lecture 19. Spring Break.
  • Mar. 20 Lecture 20.
  • Mar 22 Lecture 21
  • Mar 27 Lecture 21.5 at usual time and evening MIDTERM 8:00p - 9:00p PHYS 112
  • Mar. 29 Lecture 22
  • Apr. 3 Lecture 23
  • Apr 5 Lecture 24
  • Apr. 10 CANCELLED
  • Apr 12 Lecture 26
  • Apr. 17 Lecture 27
  • Apr 19 Lecture 28
  • Apr 24 Lecture 29
  • Apr 26 Lecture 30
  • Fri May 4 8am-10, WALC 1055 FINAL EXAM