Location: ECS 145

Time: Tuesday and Thursday 19:50 -- 21:05

Instructor: Ning Xie (office ECS 380)

Office Hours: Tuesday and Thursday 18:45 -- 19:45, or by appointments

TA: Shuai Xu (username: sxu010). Office Hours: Thursday 12:00 -- 14:00 at ECS 257.

**
(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**:
Mark A. Weiss, *Data Structures and Algorithm Analysis in Java, Third Edition*
(Pearson, 2012).

** Reference**:
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 January 29, 2017.
- Homework 2: due Sunday February 19, 2017.
- Homework 3: due Sunday March 5, 2017.
- Homework 4: due Sunday April 16, 2017.

** Announcements: **

- January 20: Homework 1 is out, due Sunday January 29.
- February 11: Homework 2 is out, due Sunday February 19.
- February 26: Homework 3 is out, due Sunday March 5.
- March 2: The in-class midterm exam is scheduled on Thursday March 9.
- April 9: Homework 4 is out, due Sunday April 16.
- April 11: The final exam is scheduled on Tuesday April 25, 19:15 -- 21:15 at ECS 145 (normal classroom).

** Schedule: **

- Lecture 1 (Jan. 10): Introduction, Model and Asymptotics (Textbook chapter 2)
- Lecture 2 (Jan. 12): Math background, Ball-testing problem (Textbook section 1.2, 2.1, Reference Appendix A)
- Lecture 3 (Jan. 17): Recursion, Recurrence (Textbook section 1.3, Reference section 4.3--4.5)
- Lecture 4 (Jan. 19): More Recurrence, Divide and Conquer (Reference section 4.3--4.5)
- Lecture 5 (Jan. 24): More Divide and Conquer (Reference section 4.3-4.5)
- Lecture 6 (Jan. 26): Backtracking, Linked Lists (Textbook section 3.2)
- Lecture 7 (Jan. 31): Review of Homework 1
- Lecture 8 (Feb. 2): Stacks, Queues and Trees (Textbook section 3.6,3.7,4.1--4.3)
- Lecture 9 (Feb. 7): Binary Search Trees (Textbook section 4.3)
- Lecture 10 (Feb. 9): AVL Trees (Textbook section 4.4)
- Lecture 11 (Feb. 14): Heaps (Textbook section 6.1--6.3)
- Lecture 12 (Feb. 16): Heaps and Priority Queues (Textbook section 6.4)
- Lecture 13 (Feb. 21): Binomial Heaps (Textbook section 6.8)
- Lecture 14 (Feb. 23): Quick Sort (Textbook section 7.7)
- Lecture 15 (Feb. 28): Randomized Algorithms (Textbook section 10.4)
- Lecture 16 (Mar. 2): Sorting Lower Bound, Counting Sort (Textbook section 7.8)
- Lecture 17 (Mar. 7): Stable Sorting, Radix Sort, Bucket Sort (Textbook section 7.11)
- Lecture 18 (Mar. 9): Midterm Exam
- Lecture 19 (Mar. 21): Review of Midterm Exam
- Lecture 20 (Mar. 23): Hashing (Textbook section 5.1--5.4)
- Lecture 21 (Mar. 28): Rolling Hash (Reference section 32.2)
- Lecture 22 (Mar. 30): Graphs and Graph Algorithms (Reference section 22.1, 22.2)
- Lecture 23 (Apr. 4): BFS, Testing Bipartiteness (Reference section 22.2)
- Lecture 24 (Apr. 6): DFS, Topological Sort (Reference section 22.3, 22.4)
- Lecture 25 (Apr. 11): MST, Greedy Algorithms, Prim's Algorithm (Reference section 23.1, 23.2)
- Lecture 26 (Apr. 13): Shortest Path, Dijkstra Algorithm (Textbook section 9.3) (Reference section 23.2)
- Lecture 27 (Apr. 18): Dynamic Programming I (Textbook section 10.3)
- Lecture 28 (Apr. 20): Dynamic Programming II (Textbook section 10.3)