Instructor: Ning Xie (office ECS 380)

Location: ECS 136

Time: Tuesday and Thursday 12:30 -- 13:45

Office Hours: Tuesday and Thursday 14:00 -- 15:00 or by appointment

TA: Kianoush Gholami. Office Hours: Wednesday 14:00 -- 16:00 at ECS 231.

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

**Syllabus**:

- Asymptotics, Recurrence
- Divide-and-Conquer (Strassen, FFT)
- Basic Data Structures: Trees, Hash Tables, Priority Queues, etc
- Graphs & Graph Algorithms
- Dynamic Programming
- Greedy Algorithms
- NP-Completeness
- Network Flow
- String Matching

**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 30%
- Midterm Exam 30%
- 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 September 16, 2014.
- Homework 2: due Friday October 3, 2014.
- Homework 3: due Thursday October 16, 2014.
- Homework 4: due Sunday November 16, 2014.
- Homework 5: due Sunday November 30, 2014.

** Announcements: **

- September 9: Homework 1 is out, due Tuesday September 16, 2014.
- September 26: Homework 2 is out, due Friday October 3, 2014.
- October 9: Homework 3 is out, due Thursday October 16, 2014.
- October 9: The in-class midterm exam is scheduled on Tuesday October 21, 2014.
- November 4: The final exam is scheduled on Tuesday December 9, 2014, 12:00 -- 2:00 PM in ECS 136.
- November 8: Homework 4 is out, due Sunday November 16, 2014.
- November 23: Homework 5 is out, due Sunday November 30, 2014.

** Schedule: **

- Lecture 1 (Aug. 26): Pre-semester Test. Introduction
- Lecture 2 (Aug. 28): Asymptotics, Running Time Analysis, Merge Sort (Chapter 1, 2, Section 3.1, 4.4)
- Lecture 3 (Sept. 2): Master Theorem, Strassen's Algorithm (Section 4.2, 4.5)
- Lecture 4 (Sept. 4): Polynomial Representations (Section 30.1)
- Lecture 5 (Sept. 9): Fast Fourier Transform (FFT) (Section 30.2)
- Lecture 6 (Sept. 11): Heaps, Heap Sort and Priority Queues (Chapter 6)
- Lecture 7 (Sept. 16): Probabilistic Analysis and Randomized Algorithms (Chapter 5)
- Lecture 8 (Sept. 18): Medians and Order Statistics (Section 9.1, 9.2)
- Lecture 9 (Sept. 23): Quicksort (Chapter 7)
- Lecture 10 (Sept. 25): Hash Tables (Section 11.1, 11.2)
- Lecture 11 (Sept. 30): Applications of Hash Tables (Section 11.3, 17.1)
- Lecture 12 (Oct. 2): String Matching, Karp-Rabin (Section 32.1, 32.2)
- Lecture 13 (Oct. 7): Graphs Representations and BFS (Appendix B.4, Section 22.1, 22.2)
- Lecture 14 (Oct. 9): Bipartite Graphs, DFS (Section 22.3)
- Lecture 15 (Oct. 14): Topological Sort, Strongly Connected Components (Section 22.4, 22.5)
- Lecture 16 (Oct. 16): Shortest Paths, Bellman-Ford (Section 24.0, 24.1)
- Lecture 17 (Oct. 21): In-class Midterm Exam
- Lecture 18 (Oct. 23): Dijkstra's Algorithm (Section 24.3)
- Lecture 19 (Oct. 28): Greedy Algorithms, Activity-selection (Section 16.0, 16.1)
- Lecture 20 (Oct. 30): Huffman Codes (Section 16.2, 16.3)
- Lecture 21 (Nov. 4): Dynamic Programming I (Section 15.1, 15.2, 15.3)
- Lecture 22 (Nov. 6): Dynamic Programming II (Section 15.4)
- Lecture 23 (Nov. 11): No Class (Veteran's day)
- Lecture 24 (Nov. 13): Dynamic Programming III (Space-efficient DP, Longest Increasing Subsequence)
- Lecture 25 (Nov. 18): NP Completeness I (Section 34.0, 34.1, 34.2)
- Lecture 26 (Nov. 20): NP Completeness II (Section 34.3, 34.4)
- Lecture 27 (Nov. 25): NP Completeness III (Section 34.5)
- Lecture 28 (Dec. 2): Maximum Flow I (Section 26.1)
- Lecture 29 (Dec. 4): Maximum Flow II (Section 26.2, 26.3)