COP-4534: Algorithm Techniques (Spring 2018)

Location: GL 166
Time: Tuesday and Thursday 19:50 -- 21:05
Instructor: Ning Xie (office ECS 380)
    Office Hours: Tuesday and Thursday 18:45 -- 19:45, or by appointments
TA: Yekun Xu (username: yxu040). Office Hours: Tuesday 13:45 PM -- 15:45 PM at ECS 232B

(Disclaimer: All information on this page about the course is tentative and subject to further changes.)

Syllabus

Topics:

• Mathematics Background, Algorithm Analysis
• Lists, Stacks and Queues
• Trees and Heaps
• Hashing and Disjoint Sets
• Divide and Conquer
• Sorting Algorithms
• Graphs & Graph Algorithms
• Dynamic Programming

Textbook: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Third Edition (MIT Press, 2009).

Grading: Grading will be based on homework assignments, a midterm, and a final exam. The midterm and final exam will be in-class, and all students must attend the on campus exam. Any exceptions must be discussed with the instructor, and approved in advance. The timing will be determined in a manner that avoids conflicts with other classes. The tentative scheme for grading is:

• Homework 40%
• Midterm Exam 20%
• Final Exam 40%.

Homework Policy:

• You are allowed to form a group with no more than 3 students to work on homework together. You are allowed to consult other books in solving homework problems, or to discuss the problems with other students in your group, but you should cite any such sources that you use. Most importantly, you must write up your solutions on your own --- merely copying answers from other books or other students is definitely NOT acceptable and will be treated as plagiarism.
• Late homework will generally NOT be accepted. If there are extenuating circumstances, you should make prior arrangements with the instructor.
• Homework submissions must be uploaded to SCIS Moodle.

Assignments:

• Homework 1: due Sunday January 28, 2018.
• Homework 2: due Sunday February 18, 2018.
• Homework 3: due Sunday March 4, 2018.
• Homework 4: due Sunday April 8, 2018.
• Homework 5: due SATURDAY April 21, 2018.

Announcements:

• January 21: Homework 1 is out, due Sunday January 28.
• February 11: Homework 2 is out, due Sunday February 18.
• February 22: The in-class midterm exam is scheduled on Tuesday March 6.
• February 25: Homework 3 is out, due Sunday March 4.
• April 1: Homework 4 is out, due Sunday April 8.
• April 14: Homework 5 is out, due SATURDAY April 21.
• April 17: The final exam is scheduled on Tuesday April 24, 19:15 -- 21:15 at GL 166 (normal classroom).

Schedule:

• Lecture 1 (Jan. 9): Introduction, Model and Asymptotics (Textbook chapter 1, chapter 3)
• Lecture 2 (Jan. 11): Math background, Ball-testing problem (Textbook Appendix A)
• Lecture 3 (Jan. 16): Recursion, Recurrence (Textbook section 4.3--4.5)
• Lecture 4 (Jan. 18): More Recurrence, Divide and Conquer (Textbook section 4.3--4.5)
• Lecture 5 (Jan. 23): More Divide and Conquer (Reference section 4.3-4.5)
• Lecture 6 (Jan. 25): Backtracking, Linked Lists
• Lecture 7 (Jan. 30): Stacks, Queues and Trees
• Lecture 8 (Feb. 1): Binary Search Trees (Textbook section 12.1 -- 12.3)
• Lecture 9 (Feb. 6): AVL Trees
• Lecture 10 (Feb. 8): Heaps (Textbook section 6.1--6.3)
• Lecture 11 (Feb. 13): Heaps and Priority Queues (Textbook section 6.4)
• Lecture 12 (Feb. 15): Binomial Heaps (Textbook 2nd edition, chapter 19)
• Lecture 13 (Feb. 20): Quick Sort I (Textbook chapter 7)
• Lecture 14 (Feb. 22): Quick Sort II
• Lecture 15 (Feb. 27): Randomized Algorithms (Textbook section 5.1--5.3)
• Lecture 16 (Mar. 1): Sorting Lower Bound (Textbook section 8.1)
• Lecture 17 (Mar. 6): Midterm Exam
• Lecture 18 (Mar. 8): Review of Midterm Exam
• Lecture 19 (Mar. 20): Counting Sort , Stable Sorting, Radix Sort, Bucket Sort (Textbook section 8.3, 8.4)
• Lecture 20 (Mar. 22): Hashing I (Textbook section 11.1--11.3)
• Lecture 21 (Mar. 27): Hashing II (Textbook section 11.1--11.3)
• Lecture 22 (Mar. 29): Rolling Hash (Textbook section 32.2)
• Lecture 23 (Apr. 3): Dynamic Programming I (Textbook section 15.1)
• Lecture 24 (Apr. 5): Dynamic Programming II (Textbook section 15.2, 15.3)
• Lecture 25 (Apr. 10): Dynamic Programming III (Textbook section 15.4)
• Lecture 26 (Apr. 12): Dynamic Programming IV (Textbook section 15.4)
• Lecture 27 (Apr. 17): Dynamic Programming V, NP-completeness (Textbook section 34.1--34.3)
• Lecture 28 (Apr. 19): NP-completeness, student project presentation