1 Homework

Important: Before starting your homework, please review our homework guide for requirements and suggestions!

1.1 HW 0: Sample

To help you see what we expect good solutions to look like, provided below are the sample solutions to a sample problem. In particular, you can view the LaTeX source to get started learning how to write in LaTeX, and you can watch a video option to see how you should record a video if you so choose.

• Problem statement/written solution
• LaTeX source
• Video solution

To use the LaTeX source, we recommend uploading the .zip file to Overleaf, and using its online compiler to compile and edit the file sample.tex.

1.2 HW 1: Intro/Correctness

Quick links:

• Problem statements
• LaTeX template
• Problem 1 extension 1 programming spec
• Problem 1 extension 1 starter code

In the homework you will be asked to:

1. Reason with the definition of a stable matching.
2. Reflect on the use of LLMs for reasoning.
3. Prove a simple algorithm to be correct.

Please read the instructions in the problem statements PDF. Happy problem solving!

1.3 HW 2: Gale–Shapley/Running time

Quick links:

• Problem statements
• LaTeX template

In the homework you will be asked to:

1. Review the running time analysis and proof of the Gale–Shapley algorithm, and extend the arguments to the many-to-one case
2. Reflect on the appropriateness of the Gale–Shapley algorithm in applications
3. Encode a more complicated algorithm in pseudocode and analyze running time in two variables

Please read the instructions in the problem statements PDF. Happy problem solving!

1.4 HW 3: Divide and conquer

Quick links:

• Problem statements
• LaTeX template
• Problem 5X.1 programming spec
• Problem 5X.1 starter code

In the homework you will be asked to:

1. Extend the closest pair of points algorithm to related contexts.
2. Experimentally benchmark a divide and conquer algorithm against a brute force algorithm.
3. Develop and prove correct your own divide and conquer algorithm.

Please read the instructions in the problem statements PDF. Happy problem solving!

1.5 HW 4: Graph Algorithms

Quick links:

• Problem statements
• LaTeX template
• Problem 7X.2 programming spec
• Problem 7X.2 starter code

In the homework you will be asked to:

1. Extend algorithms for minimum spanning trees to solve a new problem.
2. Determine when an algorithm that is mathematically correct may still be inappropriate for some uses.
3. Use graph modeling to solve an algorithmic problem.

Please read the instructions in the problem statements PDF. Happy problem solving!

1.6 HW 5: Dynamic Programming

Quick links:

• Problem statements
• LaTeX template
• Extra hint/reading for P9

In the homework you will be asked to:

1. Extend the edit distance algorithm to solve a more realistic variant used in practice.
2. Think about other variations or applications of edit distance.
3. Use dynamic programming to solve a novel problem.

1.7 HW 6: Greedy Algorithms

Quick links:

• Problem statements
• LaTeX template
• Problem 11X.2 programming spec
• Problem 11X.2 starter code

In the homework you will be asked to:

1. Extend the concepts behind Huffman codes to solve a different problem.
2. Construct counterexamples by hand and/or by computer.
3. Use greedy algorithms to solve a novel problem.

Please read the instructions in the problem statements PDF. Happy problem solving!

1.8 HW 7: Network Flows

Quick links:

• Problem statements
• LaTeX template
• Problem 11X.2 programming spec
• Problem 11X.2 starter code

In the homework you will be asked to:

1. Analyze an improvement to the Ford-Fulkerson algorithm.
2. Use network flows to model a realistic situation.

Please read the instructions in the problem statements PDF. Happy problem solving!

1.9 HW 8: SAT and NP-completeness

Quick links:

• Problem statements
• LaTeX template
• Problem 15X.2 programming spec
• Problem 15X.2 starter code

In the homework you will be asked to:

1. Reduce a problem to SAT
2. Answer questions related to the definitions of P, NP, NP-Complete, and the state of human knowledge about their relationships

Please read the instructions in the problem statements PDF. Happy problem solving!

2 Quizzes

We will have 2 quizzes this quarter, which will be held in class on the following dates. We will allocate the full 50 minute lecture period for the quiz.

1. Friday 10/24
2. Friday 11/21

You will be permitted to bring 1 letter-sized page, front and back, of notes of your own creation to reference. You are welcome to collaborate on the construction, but there are well-supported studies that suggest a lot of learning happens during the construction of that notes page, so we strongly suggest that you actively participate in building it. You may type it or hand-write it.

Besides this one page, we will also provide you a reference sheet with the quiz. The quiz will otherwise be closed resources (i.e. no textbook, electronics, neighbors, etc.).

2.1 Quiz 1

Quiz 1 (on 10/24) will cover all material from the beginning of the quarter through Divide and Conquer (i.e. Homeworks 1,2, and 3). This includes all of:

• Stable Matching
• Algorithm correctness
• Running time and asymptotic analysis
• Divide and Conquer Algorithms

Here’s a link to the quiz reference sheet.

To give you a sense for what to expect, we have provided a practice quiz. This practice quiz is intended to be representative of what we believe would be a reasonable quiz, but is not necessarily going to resemble your quiz. We recommend using this quiz as a tool to self-evaluated your preparedness after studying, rather than as a guide on what to study.

• Practice quiz 1 and solutions

We will additionally have a quiz review in the lecture prior to the quiz (so Wednesday 10/22).

2.2 Quiz 2

Quiz 2 (on 11/21) will cover all material from the end of quiz 1 content through Greedy Algorithms (i.e. Homeworks 4,5, and 6). This includes all of:

• Graph Algorithms
• Dynamic Programming Algorithms
• Greedy Algorithms

It does NOT include max flow.

As with Quiz 1, we will provide a reference sheet for Quiz 2, and you are additionally welcome to bring a 1-page (front and back) reference sheet of your own to the quiz. Below you can find a practice quiz, which includes the reference sheet we will provide on your actual quiz.

As with quiz 1, the practice quiz is intended to be representative of a reasonable quiz, but may not necessarily be substantially similar to your quiz (we were surprised by how similar we could make quiz 1 to the practice quiz, and we cannot expect that degree of similarity on every assessment).

• Practice quiz 2 and solutions

We will additionally have a quiz review in the lecture prior to the quiz (so Wednesday 11/19).

2.3 Final

Your final exam will occur at 8:30am on Monday December 8 in our regular classroom (CSE2 room G10).

You will be permitted 2 letter-sized pages, front and back, of notes to reference for the exam. You are welcome to construct that independently or in groups. You may type it or hand-write it. Besides these pages, the exam will otherwise be closed resources (i.e. no textbook, electronics, neighbors, etc.). The exam will additionally have some information provided for you (see what will be included by looking at the practice exam below). It’s wortwhile to keep in mind what we include there when designing your personal notes sheet.

The exam is cumulative, and so may include any topic from the entire quarter. In particular, this means all content covered by quizzes 1 and 2 as well as content from homeworks 7 and 8, which cover:

• Max flow, min cut, and applications thereof
• NP Completeness
• SAT

The final exam contains 8 questions, each worth 1 ESNU grade. We have provided a sample exam below. practice final (solutions)

We will include some final exam review in our last class on December 5.