COT5407: Introduction to Algorithms (Spring 2013)

Instructor: Ning Xie (office ECS 380)
Location: GL 139
Time: Monday and Wednesday 17:00 -- 18:15
Office Hours: Wed. 14:30 -- 17:00 or by appointment.
TA: Kianoush Gholami, Office Hours: Wed. 18:20 -- 19:20 (right after class) at ECS 232.



(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 and Order Statistics
• Basic Data Structures: Trees, Hash Tables, Priority Queues, Union/Find, etc
• Graphs & Graph Algorithms
• Dynamic Programming
• String Algorithms
• NP-Completeness

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: Homeworks 25%, Midterm Exam 35% and Final Exam 40%.

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.
• Homework submissions must be typeset. Handwritten submissions will NOT be accepted. These must be uploaded to SCIS moodle in PDF format only.

Assignments:

• Homework 1: due Tuesday January 22, 2013.
• Homework 2: due Tuesday February 5, 2013.
• Homework 3: due Tuesday February 19, 2013.
• Homework 4: due Tuesday April 2, 2013.
• Homework 5: due SUNDAY April 14, 2013.

Announcements:

• January 15: Homework 1 is out, due Tuesday January 22.
• January 29: Homework 2 is out, due Tuesday February 5.
• February 12: Homework 3 is out, due Tuesday February 19.
• February 20: The in-class midterm exam is scheduled on Wed. February 27.
• March 26: Homework 4 is out, due Tuesday April 2.
• April 8: Homework 5 is out, due SUNDAY April 14.
• April 8: The in-class final exam is scheduled on Monday April 22.

Schedule:

• Lecture 1 (Jan. 7): Introduction (Chapter 1)
• Lecture 2 (Jan. 9): Asymptotics (Section 3.1)
• Lecture 3 (Jan. 14): Insertion Sort, Running Time Analysis (Chapter 2)
• Lecture 4 (Jan. 16): Divide and Conquer: Peak Finding
• Lecture 5 (Jan. 23): Heaps, Heap Sort, Priority Queue (Chapter 6)
• Lecture 6 (Jan. 28): Quick Sort, Randomized Algorithms (Chapter 7)
• Lecture 7 (Jan. 30): Sorting Lower Bound, Counting Sort, Stable Sorting (Section 8.1, 8.2)
• Lecture 8 (Feb. 4): Bucket Sort and Radix Sort (Section 8.3, 8.4)
• Lecture 9 (Feb. 6): Binary Search Tree (BST) (Section 12.1, 12.2, 12.3)
• Lecture 10 (Feb. 11): Balanced BST: Red-Black Trees (Section 13.1, 13.2, 13.3)
• Lecture 11 (Feb. 13): Hashing I (Section 11.1, 11.2)
• Lecture 12 (Feb. 18): Hashing II (Section 11.3)
• Lecture 13 (Feb. 20): Hashing III (Section 17.1, 32.2)
• Lecture 14 (Feb. 25): Review
• Lecture 15 (Feb. 27): Midterm Exam
• Lecture 16 (March 4): Review of Midterm Exam
• Lecture 17 (March 6): Graphs, Graphs Algorithms, BFS (Appendix B.4, Section 22.1)
• Lecture 18 (March 18): BFS (Section 22.2)
• Lecture 19 (March 20): DFS (Section 22.3)
• Lecture 20 (March 25): Topological Sort (Section 22.4)
• Lecture 21 (March 27): Minimum Spanning Trees (Section 23.1, 23.2)
• Lecture 22 (April 1): Shortest Paths I (Section 24.0)
• Lecture 23 (April 3): Shortest Paths II: Bellman-Ford (Section 24.1)
• Lecture 24 (April 8): Shortest Paths III: Dijkstra's Algorithm (Section 24.2, 24.3)
• Lecture 25 (April 10): Dynamic Programming I (Section 15.1)
• Lecture 26 (April 15): Dynamic Programming II (Section 15.2, 15.3)
• Lecture 27 (April 17): NP Completeness (Chapter 34)