COT5407: Introduction to Algorithms (Spring 2015)

Instructor: Ning Xie (office ECS 380)
Location: GL 139
Time: Monday and Wednesday 17:00 -- 18:15
Office Hours: Monday, Wednesday 16:00 -- 17:00 or by appointment.
TA: Kianoush Gholami. Office Hours: Wednesday 18:15 -- 20:15 at ECS 231



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

Syllabus:

• Recurrence Relations and Analysis of Algorithms
• Divide-and-Conquer
• Sorting
• Basic Data Structures: Trees, Hash Tables, Priority Queues, etc
• Randomized 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 scheme for grading is: Homework assignments 30%, Midterm Exam 25% and Final Exam 45%.

Homework Policy:

• Late homework will generally NOT be accepted. If there are extenuating circumstances, you should make prior arrangements with the instructor.
• You can collaborate on homework problems with other students in the class. However, you must write up each problem solution by yourself without assistance and write on top of your assignment the names of all your collaborators for the homework.
• Homework submissions must be typeset. Handwritten submissions will NOT be accepted. These must be uploaded to SCIS moodle in PDF format only.

Homework Assignments:

• Homework 1: due Friday January 30, 2015.
• Homework 2: due Monday February 16, 2015.
• Homework 3: due Friday February 27, 2015.
• Homework 4: due Sunday April 12, 2015.
• Homework 5: due Thursday April 23, 2015.

Announcements:

• January 20: Homework 1 is out, due Friday January 30, 2015.
• February 9: Homework 2 is out, due Monday February 16, 2015.
• February 16: The in-class midterm exam is scheduled on Monday March 2, 2015.
• February 19: Homework 3 is out, due Friday February 27, 2015.
• February 19: Homework 3 is out, due Friday February 27, 2015.
• April 4: Homework 4 is out, due Sunday April 12, 2015.
• April 7: The final exam is schedule on Monday April 27 5:00 -- 7:00 PM at GL 139.
• April 16: Homework 5 is out, due Thursday April 23, 2015.
• April 20: Homework 5 is now due Friday April 24, 2015.

Schedule:

• Lecture 1 (Jan. 12): Introduction (Chapter 1)
• Lecture 2 (Jan. 14): Asymptotics, Insertion Sort, Running Time Analysis (Chapter 2, Section 3.1)
• Lecture 3 (Jan. 21): Merge Sort, Recurrence, Master Theorem (Section 4.4, 4.5)
• Lecture 4 (Jan. 26): Divide-and-Conquer: Multiplication, Peak Finding
• Lecture 5 (Jan. 28): 2D Peak Finding, Heaps (Chapter 6)
• Lecture 6 (Feb. 2): Heap Sort, Priority Queue, Quick Sort (Chapter 6, 7)
• Lecture 7 (Feb. 4): Quick Sort, Randomized Algorithms (Chapter 7)
• Lecture 8 (Feb. 9): Sorting Lower Bound, Counting Sort, Stable Sorting (Section 8.1-8.3)
• Lecture 9 (Feb. 11): Radix Sort, Bucket Sort(Section 8.3)
• Lecture 10 (Feb. 16): Bucket Sort, Binary Search Trees(Section 12.1-12.3)
• Lecture 11 (Feb. 18): Binary Search Tree, Red-Black Trees (Section 13.1-13.3)
• Lecture 12 (Feb. 23): Red-Black Trees, Hashing I (Section 11.1)
• Lecture 13 (Feb. 25): Hashing II (Section 11.2, 11.3)
• Midterm Exam (Mar. 2)
• Lecture 14 (Mar. 4): Midterm review, Hashing III
• Lecture 15 (Mar. 16): Hashing IV, Graphs (Section 17.1, 32.2, Appendix B.4)
• Lecture 16 (Mar. 18): BFS (Section 22.2)
• Lecture 17 (Mar. 23): DFS (Section 22.3)
• Lecture 18 (Mar. 25): Topological Sort (Section 22.4)
• Lecture 19 (Mar. 30): Minimum Spanning Trees I(Section 23.1, 23.2)
• Lecture 20 (Apr. 1): Minimum Spanning Trees II(Section 23.3)
• Lecture 21 (Apr. 6): Minimum Spanning Trees III(Section 21.1-21.3)
• Lecture 22 (Apr. 8): Shortest Paths I: Bellman-Ford (Section 24.0, 24.1)
• Lecture 23 (Apr. 13): Shortest Paths II: Dijkstra (Section 24.2, 24.3)
• Lecture 24 (Apr. 15): Shortest Paths III, All-Pairs Shortest Paths I (Section 25.1)
• Lecture 25 (Apr. 20): All-Pairs Shortest Paths II (Section 25.2, 25.3)
• Lecture 26 (Apr. 22): DP, NP-completeness