Lectures: WF 1130 - 12:45, 001 Stanger.
Text: Algorithms by Cormen, Rivest, and Leiserson
Goals: To understand the fundamental significance of designing and analyzing algorithms in computer science. We study the design of algorithms according to methodology and application. Methodologies include: divide and conquer, dynamic programming, and greedy strategies. Applications involve: sorting, ordering and searching, graph algorithms, geometric algorithms, mathematical (number theory, algebra and linear algebra) algorithms, and string matching algorithms. Analysis of algorithms is studied - worst case, average case, and amortized - with an emphasis on the close connection between the time complexity of an algorithm and the underlying data structures. NP-Completeness theory is examined along with methods of coping with intractability, such as approximation and probabilistic algorithms.
Exams: There will be one midterm (25%) and one final examination (35%).
Assignments: Homeworks are worth 40% of your
grade. You may do homeworks with a partner (max 2 people per
group) , as long as you stick with that same partner the whole semester.
Grading: You can guarantee an A with 90% a B with 80% etc. I may curve these numbers in your favor, if I feel it is needed.
Special Dates: Due to the Jewish High Holiday season, I will not be in class on Wednesdays, October 1, 15, and 22. There will be alternate instructions in place of lecture. Further details TBA.
| assignment 1 | assignment 2 | assignment_3 | assignment 4 |
Week |
Topic |
Reading |
| 1-2 | Introduction: Polynomial Time Algorithms versus NP-Complete Problems. Worst, Average, and Amortized Analysis. Simple Algorithms: Max, Min, GCD. Recursion. | Chapters 1, 17, 31 |
| 3-4 | Data Structure Review: Stacks, Queues, Priority Queues, Height Balanced Search Trees, Heaps. Searching and Sorting: Heapsort, Quicksort, Bucket Sort, Radix Sort. | Chapters 6-9. |
| 5-6 | Graph Algorithms: Topological Sorting, Minimum Spanning Tree and the Union-Find Data Structure | Chapters 21, 23. |
| 7 | Graph Algorithms: Depth First Search and Applications, Breadth First Search, Shortest Path. | Chapters 22, 24. |
| 8 | Geometric Algorithms: Line Intersection, Convex Hull. | Chapter 33. |
| 9 | Midterm - Date TBA | |
| 10-11 | Dynamic Programming: Fibonacci Numbers, Binomial Coefficients, All Pairs Shortest Path, Knapsack, Matrix-chain Multiplication, Optimal Triangulation, Fixed Size Graph Bandwidth. Connection to Queues. | Chapters 15, 25. |
| 12 | Greedy Methods: Huffman Codes, Minimum Spanning Tree Revisited, Task Scheduling, Approximation Algorithms. | Chapters 16, 35. |
| 13-14 | NP-Complete Problems and Reductions | Chapter 34. |
| 15 | Mathematical Algorithms, or String Matching - (if time allows) | Chapters 28-32 (selections) |