CISC 3220 Analysis of Algorithms

Basic Information and Requirements

Instructor: Prof. Neng-Fa Zhou
Class hours: Monday 06:30-09:10PM 3413 Ingersoll
Office hours: 5:00-6:00 Monday (room Ingersoll 1161)
Textbook:
- Introduction to Algorithms, Third Edition, By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press, 2009.

Topics

Algorithms, data structures, and their analysis. Applications for and solution to recurrence problems. Upper and lower bounds on complexities of various problems. Classification by design structures. Sorting methods, graph and selection algorithms. Pattern matching. Efficient computation of transitive closure and equivalences. NP-completeness. Prerequisite: CISC 3120 and 3130.

Homework assignments

There will be one homework assignment every week. Unless notified otherwise, the homework is due in one week after it is assigned. Please email your homework to cisc3220 (AT) picat-lang.org. Please write your name, student ID, and the number of the assignment in the subject, and attach your answers to the email as a PDF file. Sample answers to the questions will be given and selected questions will be reviewed in class. There will be a one-point deduction for each missing homework or late submitted homework. The total deduction will not exceed 10 points.

Exams and Grading

There will one midterm exam and one accumulative final exam, both closed-book. The midterm accounts for 30%, the final accounts for 50%, and the remaining 20% of the grade will be based on homework.

Course Outline

Introduction
- H.W. 2-1, 2-2, 2-3
Asymptotic Notation; Recurrences; Substitution, Master Method
- H.W. 3-1, 3-2, 3-3
Divide-and-Conquer: Merge Sort, Strassen, Quick Sort
Sorting and Order Statistics
- Exercises
Heapsort, Linear-time Sorting, Quick Selection
- H.W. 6-1, 6-3, 7-1, 8-3, 8-4, 9-1
Hashing, Hash Functions
- The Rabin-Karp algorithm
Binary Search Trees; Red-Black Trees;
- H.W. 12-1, 12-2
Dynamic Programming
- H.W. 15-1, 15-2, 15-5
Greedy Algorithms
- Huffman codes
- Minimum Spanning Trees
- Dijkstra's algorithm
Graph Algorithms: Breadth-first search; Depth-first search; ; Shortest Paths; Maximum Flow
- H.W. 22.2-1, 22.2-2, 22.2-3, 22.2-4, 22.3-1, 22.3-2, 22.3-4, 22.3-7, 22.4-3
NP-Completeness (Solving NP-Complete Problems with Picat)
Final Exam 5/22/2017 6:00 PM - 8:00 PM 3413 N (Reviews