Location: ECS 138

Time: Tuesday and Thursday 11:00 -- 12:15

Instructor: Ning Xie (office ECS 380)

Office Hours: Tuesday and Thursday 13:00 -- 14:00, or by appointments

TA: Yekun Xu (username: yxu040). Office Hours: Wednesday 1:30 PM -- 3:30 PM at ECS 232B

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

**Syllabus**

**Topics**:

- Mathematics Background, Algorithm Analysis
- Lists, Stacks and Queues
- Trees and Heaps
- Hashing and Disjoint Sets
- Divide and Conquer
- Sorting 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 tentative scheme for grading is:

- Homework 40%
- Midterm Exam 20%
- Final Exam 40%.

**Homework Policy**:

- You are allowed to form a group with no more than 3 students to work on homework together. However, you must write up each problem solution by yourself without assistance.
- Late homework will generally NOT be accepted. If there are extenuating circumstances, you should make prior arrangements with the instructor.
- Homework submissions must be uploaded to SCIS Moodle.

**Assignments**:

- Homework 1: due Sunday September 10, 2017.
- Homework 2: due Sunday October 8, 2017.
- Homework 3: due Sunday October 22, 2017.
- Homework 4: due Sunday November 19, 2017.
- Homework 5: due WEDNESDAY December 6, 2017.

** Announcements: **

- August 31: Homework 1 is out, due Sunday September 10.
- October 1: Homework 2 is out, due Sunday October 8.
- October 12: The in-class midterm exam is scheduled on Thursday October 26.
- October 15: Homework 3 is out, due Sunday October 22.
- November 12: Homework 4 is out, due Sunday November 19.
- November 27: The final exam is scheduled on Thursday December 14, 9:45 -- 11:45 at ECS 138 (normal classroom).
- November 29: Homework 5 is out, due WEDNESDAY December 6.

** Schedule: **

- Lecture 1 (Aug. 22): Introduction, Model and Asymptotics (Textbook chapter 1, chapter 3)
- Lecture 2 (Aug. 24): Math background, Ball-testing problem (Textbook Appendix A)
- Lecture 3 (Aug. 29): Recursion, Recurrence (Textbook section 4.3--4.5)
- Lecture 4 (Aug. 31): More Recurrence, Divide and Conquer (Textbook section 4.3--4.5)
- Lecture 5 (Sept. 5): More Divide and Conquer (Reference section 4.3-4.5)
- Lecture 6 (Sept. 7): Cancelled due to Hurricane Irma
- Lecture 7 (Sept. 19): Backtracking, Linked Lists
- Lecture 8 (Sept. 21): Stacks, Queues and Trees
- Lecture 9 (Sept. 26): Binary Search Trees (Textbook section 12.1 -- 12.3)
- Lecture 10 (Sept. 28): AVL Trees
- Lecture 11 (Oct. 3): Heaps (Textbook section 6.1--6.3)
- Lecture 12 (Oct. 5): Heaps and Priority Queues (Textbook section 6.4)
- Lecture 13 (Oct. 10): Binomial Heaps (Textbook 2nd edition, chapter 19)
- Lecture 14 (Oct. 12): Quick Sort I (Textbook chapter 7)
- Lecture 15 (Oct. 17): Quick Sort II
- Lecture 16 (Oct. 19): Randomized Algorithms (Textbook section 5.1--5.3)
- Lecture 17 (Oct. 24): Sorting Lower Bound(Textbook section 8.1)
- Lecture 18 (Oct. 26): Midterm Exam
- Lecture 19 (Oct. 31): Review of Midterm Exam
- Lecture 20 (Nov. 2): Counting Sort , Stable Sorting, Radix Sort, Bucket Sort (Textbook section 8.3, 8.4)
- Lecture 21 (Nov. 7): Hashing (Textbook section 11.1--11.3)
- Lecture 22 (Nov. 9): Rolling Hash (Textbook section 32.2)
- Lecture 23 (Nov. 14): Dynamic Programming I (Textbook section 15.1)
- Lecture 24 (Nov. 16): Dynamic Programming II (Textbook section 15.2, 15.3)
- Lecture 25 (Nov. 21): Dynamic Programming III (Textbook section 15.4)
- Lecture 26 (Nov. 28): Dynamic Programming IV (Textbook section 15.4)
- Lecture 27 (Nov. 30): Graphs and Graph Algorithms (Textbook section 22.1, 22.2)
- Lecture 28 (Dec. 5): Testing Bipartiteness, Dijkstra's Algorithm (Textbook section 22.2, 23.2)
- Lecture 29 (Dec. 7): MST, Greedy Algorithms, Prim's Algorithm (Textbook section 23.1, 23.2)