COT5407: Introduction to Algorithms (Spring 2014)
Instructor: Ning Xie (office ECS 380)
Location: GL 139
Time: Monday and Wednesday 17:00 -- 18:15
Office Hours: Wed. 15:00 -- 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
- 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 30% 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 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.
Assignments:
Announcements:
- January 14: Homework 1 is out, due Tuesday January 21, 2014.
- January 30: Homework 2 is out, due Friday February 7, 2014.
- February 12: The in-class midterm exam is scheduled on Monday March 3, 2014.
- February 19: Homework 3 is out, due Wednesday February 26, 2014.
- March 31: Homework 4 is out, due Monday April 7, 2014.
- April 7: The final exam is scheduled on Monday April 21 , 2014.(Time: 5:00--7:00 PM, Place: GL 139)
- April 9: Homework 5 is out, due Wednesday April 16, 2014.
Schedule:
- Lecture 1 (Jan. 6): Introduction, Asymptotics (Chapter 1, 2)
- Lecture 2 (Jan. 8): Bubble Sort, Running Time Analysis (Section 3.1)
- Lecture 3 (Jan. 13): Insertion Sort, Merge Sort, Recurrence, Master Theorem (Section 4.4, 4.5)
- Lecture 4 (Jan. 15): Divide-and-Conquer: Multiplication, Peak Finding
- Lecture 5 (Jan. 22): Heaps (Chapter 6)
- Lecture 6 (Jan. 27): Heap Sort, Priority Queue, Quick Sort (Chapter 6, 7)
- Lecture 7 (Jan. 29): Quick Sort, Randomized Algorithms (Chapter 7)
- Lecture 8 (Feb. 3): Counting Sort, Stable Sorting, Bucket Sort (Section 8.1-8.3)
- Lecture 9 (Feb. 5): Bucket Sort, Binary Search Trees (BST) (Section 8.3, 12.1, 12.2)
- Lecture 10 (Feb. 10): Binary Search Trees, Red-Black Trees (Section 12.3, 13.1)
- Lecture 11 (Feb. 12): Red-Black Trees, Hashing I (Section 13.2, 13.3, 11.1, 11.2)
- Lecture 12 (Feb. 17): Hashing II (Section 11.2, 11.3)
- Lecture 13 (Feb. 19): Hashing III (Section 17.1, 32.2)
- Lecture 14 (Feb. 24): Hashing IV (Section 32.2, 11.4)
- Lecture 15 (Feb. 26): Graphs and Graphs Algorithms (Appendix B.4, Section 22.1)
- Lecture 16 (Mar. 3): Midterm Exam
- Lecture 17 (Mar. 5): Midterm Exam Review
- Lecture 18 (Mar. 17): BFS (Section 22.2)
- Lecture 19 (Mar. 19): DFS (Section 22.3)
- Lecture 20 (Mar. 24): Topological Sort (Section 22.4)
- Lecture 21 (Mar. 26): Minimum Spanning Trees (Section 23.1, 23.2)
- Lecture 22 (Mar. 31): Shortest Paths I: Generic Algorithm (Section 24.0)
- Lecture 23 (Apr. 2): Shortest Paths II: Bellman-Ford (Section 24.1)
- Lecture 24 (Apr. 7): Shortest Paths III: Dijkstra (Section 24.2, 24.3)
- Lecture 25 (Apr. 9): Dynamic Programming I (Section 15.1)
- Lecture 26 (Apr. 14): Dynamic Programming II (Section 15.2, 15.3)
- Lecture 27 (Apr. 16): Dynamic Programming III (Section 15.4)