Location: ECS 145

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

Instructor: Ning Xie (office ECS 380)

Office Hours: Tuesday 17:00 -- 18:00 and Thursday 16:00 -- 17:00, or by appointments

TA: Shokoufeh Mokhtari (office ECS 251)

Office Hours: Thursday 12:30 -- 1:30 and Friday 12:00 -- 1:00

**
(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**:

- 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 Thursday September 10, 2015.
- Homework 2: due Monday September 28, 2015.
- Homework 3: due Friday October 16, 2015.
- Homework 4: due Wednesday November 4, 2015.
- Homework 5: due Saturday November 21, 2015.
- Homework 6: due Wednesday December 2, 2015.

** Announcements: **

- September 3: Homework 1 is out, due Thursday September 10, 2015.
- September 21: Homework 2 is out, due Monday September 28, 2015.
- October 9: Homework 3 is out, due Friday October 16, 2015.
- October 13: The in-class midterm exam is scheduled on Tuesday October 20.
- October 27: Homework 4 is out, due Wednesday November 4, 2015.
- November 13: Homework 5 is out, due Saturday November 21, 2015.
- November 24: Homework 6 is out, due Wednesday December 2, 2015.
- December 1: The final exam is scheduled on Thursday December 10, 9:45AM -- 11:45AM, in ECS 145.

** Schedule: **

- Lecture 1 (Aug. 25): Introduction, Asymptotics
- Lecture 2 (Aug. 27): Recursion, Recurrence
- Lecture 3 (Sept. 1): Backtracking, Linked Lists
- Lecture 4 (Sept. 3): Review of Java and Programming Issues
- Lecture 5 (Sept. 8): Stacks and Queues
- Lecture 6 (Sept. 10): Queues and Trees
- Lecture 7 (Sept. 15): Binary Search Trees
- Lecture 8 (Sept. 17): AVL Trees
- Lecture 9 (Sept. 22): Heaps
- Lecture 10 (Sept. 24): Heaps and Priority Queues
- Lecture 11 (Sept. 29): Binomial Heaps
- Lecture 12 (Oct. 1): Binomial Heaps, Quick Sort
- Lecture 13 (Oct. 6): Quick Sort, Randomized Algorithms
- Lecture 14 (Oct. 8): Sorting Lower Bound, Counting Sort, Bucket Sort
- Lecture 15 (Oct. 13): Stable Sorting, Radix Sort, Bucket Sort
- Lecture 16 (Oct. 18): Bucket Sort, Hashing
- Lecture 17 (Oct. 20): Midterm Exam
- Lecture 18 (Oct. 22): Midterm Review
- Lecture 19 (Oct. 27): Hashing, Graphs
- Lecture 20 (Oct. 29): BFS, Testing Bipartiteness
- Lecture 21 (Nov. 3): DFS, Topological Sort
- Lecture 22 (Nov. 5): Minimum Spanning Tree, Prim's Algorithm
- Lecture 23 (Nov. 10): Kruskal's Algorithms, Union-Find
- Lecture 24 (Nov. 12): Shortest Path, Dijkstra Algorithm
- Lecture 25 (Nov. 17): Union-Find (continued)
- Lecture 26 (Nov. 19): Dynamic Programming (I)
- Lecture 27 (Nov. 24): Dynamic Programming (II)
- Lecture 28 (Dec. 1): Dynamic Programming (III)
- Lecture 29 (Dec. 3): Divide and Conquer