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

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

**Syllabus**:

- 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).

**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 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 Wednesday January 27, 2016.
- Homework 2: due Wednesday February 17, 2016.
- Homework 3: due Sunday March 6, 2016.
- Homework 4: due Sunday April 10, 2016.
- Homework 5: due Wednesday April 27, 2016.

** Announcements: **

- January 20: Homework 1 is out, due Wednesday January 27.
- January 25: Homework 1 due day is extended to Thursday January 28.
- February 10: Homework 2 is out, due Wednesday February 17.
- February 18: The in-class midterm exam is scheduled on Tuesday March 8.
- February 28: Homework 3 is out, due Sunday March 6.
- April 3: Homework 4 is out, due Sunday April 10.
- April 14: The final exam is scheduled on Tuesday May 3, 7:15 PM -- 9:15 PM, in ECS 145.
- April 20: Homework 5 is out, due Wednesday April 27.

** Schedule: **

- Lecture 1 (Jan. 12): Introduction
- Lecture 2 (Jan. 14): Asymptotics, Ball-testing problem
- Lecture 3 (Jan. 19): Recursion, Recurrence
- Lecture 4 (Jan. 21): More Recurrence, Backtracking
- Lecture 5 (Jan. 26): Divide and Conquer
- Lecture 6 (Jan. 28): Divide and Conquer, Linked Lists
- Lecture 7 (Feb. 2): Review of Homework 1
- Lecture 8 (Feb. 4): Stacks, Queues and Trees
- Lecture 9 (Feb. 9): Binary Search Trees
- Lecture 10 (Feb. 11): AVL Trees
- Lecture 11 (Feb. 16): Heaps
- Lecture 12 (Feb. 18): Heaps and Priority Queues
- Lecture 13 (Feb. 23): Binomial Heaps
- Lecture 14 (Feb. 25): Binomial Heaps, Quick Sort
- Lecture 15 (Mar. 1): Quick Sort, Randomized Algorithms
- Lecture 16 (Mar. 3): Sorting Lower Bound, Counting Sort
- Lecture 17 (Mar. 8): Midterm Exam
- Lecture 18 (Mar. 10): Stable Sorting, Radix Sort, Bucket Sort
- Lecture 19 (Mar. 22): Review of Midterm Exam
- Lecture 20 (Mar. 24): Hashing
- Lecture 21 (Mar. 29): Cancelled
- Lecture 22 (Mar. 31): Rolling Hash, Graphs and Graph Algorithms
- Lecture 23 (Apr. 5): BFS, Testing Bipartiteness
- Lecture 24 (Apr. 7): DFS, Topological Sort
- Lecture 25 (Apr. 12): Topological Sort, Minimum Spanning Trees
- Lecture 26 (Apr. 14): Greedy Algorithms, Prim's Algorithm
- Lecture 27 (Apr. 19): Kruskal's Algorithms, Union-Find
- Lecture 28 (Apr. 21): Shortest Path, Dijkstra Algorithm
- Lecture 29 (Apr. 26): Dynamic Programming (I)
- Lecture 30 (Apr. 28): Dynamic Programming (II)