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)