CS 312: Algorithm Analysis
Professor Sean Warnick
Course Description
CS 312 is an introductory algorithms analysis course; it is about problems and heir solutions, about information and how it is organized to meet specific objectives. Students learn what a well formulated problem is, as well as the difference between analytic and algorithmic solutions to such problems. We analyze the quality of algorithmic solutions using various notions of correctness and efficiency, and we explore the application of these ideas in a variety of settings. These settings include scientific computing, signal processing (audio and image), cryptography, computer graphics, data compression and coding, search engine ranking, DNA sequence alignment, inventory management, scheduling of manufacturing systems, radiation therapy, bandwidth allocation, computational finance, clustering, and games. In the design of algorithmic solutions to well formulated problems, connections are drawn between data structures and computational performance; the role of mathematical models in making these connections is emphasized. CS 312 provides a strong foundation for the second semester, advanced algorithms elective, CS 412: Linear Programming and Convex Optimization.
Text
Algorithms by Dasgupta, Papadimitriou, and Vazirani.
Supplemental texts include:
- Introduction to Dynamic Systems: Theory, Models, & Applications by Luenberger
- Algorithm Design by Kleinberg and Tardos
- Introduction to Algorithms by Cormen, Clifford, Leiserson, Rivest, and Stein
- Fundamentals of Algorithmics by Brassard and Bratley
- Dynamic Programming and Optimal Control by Bertsekas
Typical Schedule
| Week 1 | Reading | Assigned | Due | |
| T | Problems and Solutions | The Turing Omnibus, Chapter 30; Dynamic Systems, Chapter 1, 2.1-2.3 | ||
| Th | Algorithm Analysis | Algorithms, Chapter 0; Dynamic Systems, Chapter 1, 2.4-2.7 | HW1, Lab1 | |
| F | Recitation: C# and Visual Studio | |||
| Week 2 | ||||
| T | Difference Equations | |||
| Th | Solving Difference Equations | Algorithms, Chapter 2.1-2.5 | HW2 | HW1 |
| F | Recitation: Difference Equation Practice | |||
| Week 3 | ||||
| T | Master Theorem | |||
| Th | Average Case Analysis | Algorithms, Chapter 2.6 | HW3, Lab2 | HW 2 |
| F | Recitation: More Difference Equation Practice | |||
| Week 4 | ||||
| T | Signal Processing | |||
| Th | FFT | Algorithms, Chapter 1.1-1.4 | HW4 | HW 3, Lab1 |
| F | Recitation: Elementary Probability Theory Practice | |||
| Week 5 | ||||
| T | Cryptography | |||
| Th | Randomized Algorithms | Algorithms, Chapter 1.5 | HW5, Lab3 | HW 4 |
| F | Recitation: Data Structures and Complexity | |||
| Week 6 | ||||
| T | Randomized Algorithms | |||
| Th | Page Rank | Algorithms, Chapter 3-4 | HW6 | HW5, Lab2 |
| F | Recitation: Midterm Review | |||
| Week 7 | ||||
| T | Shortest Paths | |||
| Th | Minimum Spanning Trees | Algorithms, Chapter 5 | HW7 | HW6 |
| F | Midterm 1 | Covers material through Randomized Algorithms | ||
| Week 8 | ||||
| T | Knapsack | |||
| Th | Huffman Codes | Algorithms, Chapter 6 | HW8, Lab4 | HW7, Lab3 |
| F | Recitation: Homework/Project Q&A | |||
| Week 9 | ||||
| T | Dynamic Programming | |||
| Th | Computational Biology | Dynamic Programming, Chapter 1 | HW9 | HW8 |
| F | Recitation: Data Structures and Dynamic Programming | |||
| Week 10 | ||||
| T | Sequential Decision Making | |||
| Th | Inventory Management | Dynamic Programming, Chapter 2 | HW10 | HW9 |
| F | Honors Lunch | |||
| Week 11 | ||||
| T | TSP | |||
| Th | Linear Programming | Algorithms, Chapter 7 | HW11, Lab5 | HW10, Lab4 |
| F | Recitation: Midterm Review | |||
| Week 12 | ||||
| T | Simplex | |||
| Th | Linear Regression | Algorithms, Chapter 8 | HW12 | HW11 |
| F | Midterm 2 | Covers material through TSP | ||
| Week 13 | ||||
| T | NP-Complete Problems | |||
| Th | Backtracking | Algorithms, Chapter 9 | HW13 | HW12 |
| F | Honors Lunch | |||
| Week 14 | ||||
| T | Branch and Bound | |||
| Th | Examples | HW13, Lab5 | ||
| F | Recitation: Final Exam Review | |||
Assignments
Reading: There are daily reading assignments.
Homework: There are weekly homework assignments, generally drawn from the course texts.
Projects: There are five programming assignments in C# using Microsoft Visual Studio:
- Scientific Computing
- FFT and Audio Processing
- Intelligent Scissors for Image Processing
- DNA Sequence Alignment on Corona Viruses, including SARS
- Portfolio Optimization in Computational Science
External Observations: By the end of the semester, each student is required to submit a set of reports describing how the student has observed the ideas from CS 312 applied in other settings (5 pages, single spaced). Generally this will be five distinct single-page reports, each one summarizing a distinct activity, such as a talk from the CS Colloquium, or a connection to a project in another class, etc.
Honors Section
Any student in either of the regular sections may register for the Honors Section by enrolling in HONRS 345 and dropping CS 312. Students in the Honors Section meet with the regular section for lectures and exams, and they participate in all the same assignments except the External Observations. Instead, each student in the Honors Section selects a "Great Idea" from Computer Science, such as any of those listed in The New Turing Omnibus by Dewdney, and explores the idea in some depth. Students discuss their progress with the instructor and each other periodically during Honors Lunch, and they present their final results to the Honors Section at the end of the semester. A response to the Great Idea (e.g. paper, about five pages; or a coded application; etc.) is submitted for grading. The Honors Section is not designed to be more work than the regular section; rather, it is an opportunity for students who want more interaction with the instructor (e.g. for potential letters of recommendation for graduate school) to have that opportunity. Also, it provides a vehicle for students participating in the Honors Program to earn their honors credits and one of their Great Works responses while meetings their core CS requirements.
Recitation
Every Friday, a recitation is provided by the TAs to review key concepts, practice solving problems, discuss implementation details for the programming projects, emphasize particular points, and review for the exams. As with lectures or office hours, attendance is optional.
Tests
There are two midterm exams and a comprehensive final. Each test is usually proctored in the testing center. Each exam is about three hours long (although generally up to five hours is allowed, if necessary).
Preparation Time
"The expectation for undergraduate courses is three hours of work per week per credit hour for the average student who is appropriately prepared; much more time may be required to achieve excellence. These three hours may include one hour of lecture plus two hours of work outside class, three hours in a laboratory with little outside work, or any other combination appropriate to a particular course." (page 56, University Catalog)
Grades
Grades will be weighted by the following distribution and scale:
- Final Exam 25%
- Midterm #1 15%
- Midterm #2 15%
- 5 Programming Projects 25%
- Homework 25%
- External Observations (or Great Idea response for the Honors Sections) 5%
| 100-93 A | 93-90 A- | 90-87 B+ |
| 87-83 B | 83-80 B- | 90-77 C+ |
| 77-73 C | 73-70 C- | 70-67 D+ |
| 67-63 D | 63-60 D- | 60-0 E |
We reserve the right to curve grades in your favor. The University policies on UW and I grades will be strictly followed.