COP-4534: Algorithm Techniques (Spring 2016)

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)