Courses

Course Description:

CS 312 is an introductory algorithms analysis course; it is about problems and their 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.

Lectures:

TTH 8-9:15 (Section 1)
TTH 9:30-10:45 (Section 2)
HONRS 345 may meet with either section

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 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	HW2
F Recitation: More Difference Equation Practice

Week 4
T Signal Processing
TH FFT	Algorithms, Chapter 1.1-1.4	HW4	HW3,LAB1
F Recitation: Elementary Probability Theory Practice

Week 5
T Cryptography
TH Randomized Algorithms	Algorithms, Chapter 1.5	HW5,LAB3	HW4
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
TH-S 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
TH-S 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.
    Project 1: Scientific Computing
    Project 2: FFT and Audio Processing
    Project 3: Intelligent Scissors for Image Processing
    Project 4: DNA Sequence Alignment on Corona Viruses, including SARS
    Project 5: Portfolio Optimization in Computational Finance

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 are 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-	80-87 B+
87-83 B	83-80 B-	80-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.