Syllabus: Colorado CSCI 5454, Fall 2019

Instructor: Bo Waggoner
Course webpage: https://www.bowaggoner.com/courses/2019/csci5454/

Course Information

Goals and topics

The goal of the course is to familiarize students with the dominant paradigms for mathematically rigorous design and analysis of classical, sequential algorithms. After taking this course, students will be prepared: to interface with and design sophisticated modern algorithms in software engineering; go on to (self-)study advanced or specialized topics in algorithms; study related topics such as machine learning.

• Module 1: Combinatorial and Graph Algorithms
• Paths and graph search
• Dynamic programming
• Flows and cuts
• Matchings
• Module 2: Approximation, Online, and Randomized Algorithms
• Approximation algs, e.g. greedy matching
• Online algs, e.g. ski rental
• Randomized (and approximation) algs, e.g. max-cut
• Settings combining all three features
• Data structures, e.g. hash tables
• Module 3: Continuous, Linear, and Convex Methods
• Linear algebra on graphs ("spectral graph theory")
• Dimensionality reduction
• Online no-regret learning; zero-sum games
• Linear programming applications

Prerequisites

This course will be theoretical, mathematically rigorous, and proof-based. We will assume familiarity with undergraduate algorithms (such as CSCI 3104), data structures (such as CSCI 2270), discrete mathematics (such as CSCI 2824), linear algebra, and calculus. Students may also be expected to implement small programs in a programming language of their choice.

Students should already have learned and reviewed the following material. Students lacking these prerequisites are strongly encouraged to take CSCI 3104 first.

• Big-O, Big-Theta, Big-Omega notation and their mathematical meanings.
• Basic data structures, heaps, binary search trees.
• Algorithm design approaches: divide-and-conquer (analysis using recurrences), greedy algorithms, dynamic programming.
• Algorithms for basic search and sorting (bubblesort, mergesort, quicksort, etc).
• Basic graph algorithms: breadth- and depth-first search, shortest paths, spanning trees.
• Definitions of P and NP complexity classes, the notion of NP-hardness.

When you have questions

• Assignments and course material: (1) re-read course notes and links; (2) post on Piazza or discuss with fellow students; (3) come to office hours.
• Confidential or non-course-related: email instructor.

Assignments and Evaluation

• Readings: Prior to each lecture we will typically assign a book chapter, external notes, or video. Students should expect to spend at least half an hour to an hour with this material before each class. This preparation will help us move at a good pace.
• References: For each lecture we will provide a reference for the material covered; usually, the same as the assigned reading above. Reviewing the reference after class will be helpful for absorbing material, as well as homeworks and exams.
• Homeworks (50% of grade): Assignments will be due approximately every one to two weeks and turned in using Gradescope.
• Homework solutions will be available on Canvas for students to go over.
• Midterm exam (20% of grade), date to be announced on the course webpage.
• Final exam (25% of grade), date to be announced.

The final score will be calculated by a weighted average of the grades in each component. The homework grade will be calculated by averaging homework percentage scores, subject to the Drop 2 Rule described below. Note that the instructor does not have discretion over the student's final score. Course letter grades will be assigned based on final score ranges, possibly with a curve.

CSCI 5454 Policies and Logistics

Homework Policy (Drop 2 Rule)

Each student's two lowest homework grades will be dropped and the homework component of their course grade will be calculated from scores on remaining assignments.

Because of this, we will not accept late homework. Late homework will be marked as zero.

This allows students two emergency or exceptional scenarios during the semester that prevent them from turning in homeworks, as these two zeros will not affect their final grade. It also allows our staff to post solutions and return homeworks to students as quickly as possible, which improves the feedback cycle and learning process.

If a student faces an on-going or series of exceptional situations that is likely to prevent on-time submission of three or more homeworks, they should notify the instructor as soon as possible.

Collaboration and Homework Policy

1. Students are encouraged to work together to understand course material, including homework material, and study for exams.
2. Students must write their own homework solutions themselves in their own words.
3. Each homework must list the people the student collaborated with and external resources consulted (people not affiliated with the course or materials not mentioned or linked on the course site).
4. Students may consult external resources for general understanding of material covered in class (such as "how does topological sort work?") and are encouraged to share useful resources with others on Piazza.
5. Students may not use external resources to find solutions to specific homework problems.
6. If this policy is unclear or you have any questions, contact the instructors e.g. by posting on Piazza.

If you feel a mistake has been made in grading a homework or your midterm exam, you may submit a specific, concise regrade request via Gradescope within 5 days of receiving the original grade. (Example: if a homework grade is released at any time on Thursday, the request is due by 11:59pm next Tuesday.) Please consult the official solutions, their peers, piazza, and/or office hours before submitting a regrade request. If there are too many incorrect requests, we may institute a policy charging some fraction of a point per request.

Exam Logistics

The logistics for the midterm and final exams will be announced on the course webpage, Piazza, and/or via email.