# Syllabus: Colorado CSCI 5454, Fall 2021

Instructor: Bo Waggoner
Course webpage: https://www.bowaggoner.com/courses/2021/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 and graphs; random walks
• 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; (2) consider reading linked resources; (3) post on Zulip and discuss with fellow students; (4) attend office hours.
• Confidential or non-course-related: email instructor.

### Assignments and Evaluation

• Readings and videos: Prior to each class we will typically assign a video and a reading. Students should expect to spend an hour to 90 minutes with this material before each class. This will allow us to use class time to solve problems (including homework problems).
• Homework (50% of grade): Assignments will usually be due every week and turned in using Gradescope.
• HW peer feedback (10% of grade): Students will use the sample solutions available on Canvas to briefly give feedback on a peer's assignment. It will be graded for effort and completion.
• Midterm exam (15% of grade), details to be announced on course homepage.
• Final exam (20% of grade), details to be announced on course homepage.

The final score will be calculated by a weighted average of the grades in each component, subject to Drop policies below. The instructor does not have discretion over the student's final score. Course letter grades will be assigned based on final scores, possibly adjusted upward.

### Peer Feedback

In peer feedback, you will be asked to give a classmate feedback on one of their problems from homework. You should do THREE things:

1. Review the sample correct solutions posted on Canvas. Note there may be more than one way to do a problem.
2. Provide any specific feedback, such as parts you didn't understand or statements you think were not correct. It's okay to say you had trouble following. Clarity is an important part of homework, so this is useful feedback.
3. At the top, provide an overall assessment from the following scale:
• (4) Perfect solution as far as you can tell. (Use sparingly!)
• (3) Generally correct solution, but may have very minor mistakes, or style or presentation can be improved.
• (2) You believe the solution has an important mistake, or the presentation is too difficult to follow.
• (1) You believe the solution has serious mistakes, is on the wrong track, or the problem was not attempted.
• (N/A) You did not feel you understood the problem and your peer's solution well enough to provide feedback this time.

It is okay to use N/A sometimes if you are made an effort to understand the problem. Consider asking classmates, at office hours, or on Zulip for help understanding the problem before writing your feedback.

It is expected that students spend about 10-20 minutes per week on providing peer feedback. If a solution is very difficult to follow, after about 20 minutes of effort, it is appropriate to use N/A.

## CSCI 5454 Policies and Logistics

### Remote and Asynchronous Students

Students, including those enrolled in the remote (virtual) section, are expected to attend synchronously unless they have another class or work conflict. Students who have a conflict will be asked to notify the instructor so that exams and other work can be coordinated.

### 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. Th corresponding homework self-assessment scores will be dropped as well.

Because of this, we will not accept late homework for any reason (it will be dropped instead).

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 exceptional situation 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 Zulip.
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 Zulip.