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:
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
- Asymptotic Notation; Recurrences; Substitution, Master Method
- Divide-and-Conquer: Merge Sort, Strassen, Quick Sort
- Sorting and Order Statistics
- Heapsort, Linear-time Sorting, Quick Selection
- H.W. 6-1, 6-3, 7-1, 8-3, 8-4, 9-1
- Hashing, Hash Functions
- Binary Search Trees; Red-Black Trees;
- Dynamic Programming
- 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
- Final Exam (Reviews