COP-4534: Algorithm Techniques (Fall 2015)

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