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:

  1. Scientific Computing
  2. FFT and Audio Processing
  3. Intelligent Scissors for Image Processing
  4. DNA Sequence Alignment on Corona Viruses, including SARS
  5. 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.