All tasks will be submitted and graded on Gradescope.

1 Homework

Links to homeworks will be posted here as they are released (typically Wednesday evenings). Please review our homework guide for requirements and suggestions on writing up your submissions.

1.1 Homework 1: Stable Matching and Proof Writing

In the homework you will be asked to:

  1. reason about the properties of stable matchings
  2. adapt to generalizations of assumptions made for inputs to the Gale-Shapley algorithm
  3. apply an inductive argument

The problem statements can be found in this pdf.

You may draft your solutions in Overleaf using this LaTeX template (preferred), in a document (please use the equation editor for all math notation), or hand-written (so long as you are able to do so neatly). To use the template, download it by clicking the link, then re-upload it to an Overleaf project, then change the compiler to XeLaTeX within the menu (the button in the top-left corner of the page with the Overleaf logo).

You will submit your solutions to gradescope. Keep in mind that you have a distinct gradescope assignment per problem. Since this assignment has 3 problems, there are 3 distinct gradescope submissions you must make.

Happy problem solving!

In this homework you will be asked to:

  1. Compare the asymptotic growth rates of functions
  2. Adapt graph search procedures (BFS and DFS) into novel algorithms.

The problem statements can be found in this pdf.

You may draft your solutions in Overleaf using this LaTeX template (preferred), in a document (please use the equation editor for all math notation), or hand-written (so long as you are able to do so neatly). To use the template, download it by clicking the link, then re-upload it to an Overleaf project, then change the compiler to XeLaTeX within the menu (the button in the top-left corner of the page with the Overleaf logo).

You will submit your solutions to gradescope. Keep in mind that you have a distinct gradescope assignment per problem. Since this assignment has 4 problems, there are 4 distinct gradescope submissions you must make.

Happy problem solving!

1.3 Homework 3: Greedy

In this homework you will be asked to:

  1. Find a counterexample for a give (flawed) greedy algorithm.
  2. Design and analyze greedy algorithms of your own.

The problem statements can be found in this pdf.

As always, you may draft your solutions in Overleaf using this LaTeX template (preferred), in a document (please use the equation editor for all math notation), or hand-written (so long as you are able to do so neatly). To use the template, download it by clicking the link, then re-upload it to an Overleaf project, then change the compiler to XeLaTeX within the menu (the button in the top-left corner of the page with the Overleaf logo).

You will submit your solutions to gradescope. Keep in mind that you have a distinct gradescope assignment per problem. Since this assignment has 4 problems, there are 4 distinct gradescope submissions you must make.

1.4 Homework 4: Divide and Conquer

In this homework you will be asked to:

  1. Show how to apply the master theorem to solve recurrence relations, or else show that you can’t.
  2. Design and analyze divide and conquer algorithms of your own.

The problem statements can be found in this pdf.

As always, you may draft your solutions in Overleaf using this LaTeX template (preferred), in a document (please use the equation editor for all math notation), or hand-written (so long as you are able to do so neatly). To use the template, download it by clicking the link, then re-upload it to an Overleaf project, then change the compiler to XeLaTeX within the menu (the button in the top-left corner of the page with the Overleaf logo).

You will submit your solutions to gradescope. Keep in mind that you have a distinct gradescope assignment per problem. Since this assignment has 4 problems, there are 4 distinct gradescope submissions you must make.

1.5 Homework 5: Dynamic Programming

In this homework you will be asked to:

  1. Modify the edit distance algorithm from class to add new parameters
  2. Design and analyze dynamic programming algorithms of your own

The problem statements can be found in this pdf.

As always, you may draft your solutions in Overleaf using this LaTeX template (preferred), in a document (please use the equation editor for all math notation), or hand-written (so long as you are able to do so neatly). To use the template, download it by clicking the link, then re-upload it to an Overleaf project, then change the compiler to XeLaTeX within the menu (the button in the top-left corner of the page with the Overleaf logo).

You will submit your solutions to gradescope. Keep in mind that you have a distinct gradescope assignment per problem. Since this assignment has 4 problems, there are 4 distinct gradescope submissions you must make.

1.6 Homework 6: Dynamic Programming and Max Flow

In this homework you will be asked to:

  1. Execute Ford Fulkerson by hand on a given graph
  2. Solve a problem related to max flow
  3. Design and analyze more dynamic programming algorithms of your own

The problem statements can be found in this pdf.

As always, you may draft your solutions in Overleaf using this LaTeX template (preferred), in a document (please use the equation editor for all math notation), or hand-written (so long as you are able to do so neatly). To use the template, download it by clicking the link, then re-upload it to an Overleaf project, then change the compiler to XeLaTeX within the menu (the button in the top-left corner of the page with the Overleaf logo).

You will submit your solutions to gradescope. Keep in mind that you have a distinct gradescope assignment per problem.

1.7 Homework 7: Max Flow and Linear Programming

In this homework you will be asked to:

  1. Write algorithms which use max flow and reductions
  2. Solve a problem involving linear programming
  3. Design an algorithm combining the ideas of linear programming and max flow

The problem statements can be found in this pdf.

As always, you may draft your solutions in Overleaf using this LaTeX template (preferred), in a document (please use the equation editor for all math notation), or hand-written (so long as you are able to do so neatly). To use the template, download it by clicking the link, then re-upload it to an Overleaf project, then change the compiler to XeLaTeX within the menu (the button in the top-left corner of the page with the Overleaf logo).

You will submit your solutions to gradescope. Keep in mind that you have a distinct gradescope assignment per problem.

1.8 Homework 8: Hardness

In this homework you will be asked to:

  1. Answer T/F questions relating to the classes P, NP, NP-Hard, and NP-Complete
  2. Demonstrate problems to belong to NP-Complete
  3. Show the relationship between a decision problem and a search problem

The problem statements can be found in this pdf.

Question 1 will be answered directly in Gradescope. You may draft your solutions to the other problems in Overleaf using this LaTeX template (preferred), in a document (please use the equation editor for all math notation), or hand-written (so long as you are able to do so neatly). To use the template, download it by clicking the link, then re-upload it to an Overleaf project, then change the compiler to XeLaTeX within the menu (the button in the top-left corner of the page with the Overleaf logo).

You will submit your solutions to gradescope. Keep in mind that you have a distinct gradescope assignment per problem.

2 Exams

2.1 Midterm

Your midterm exam will be at 6:00pm-7:30pm on Wednesday February 19 in Bagly 131 in lieue of a normal class meeting.

You will be permitted 1 letter-sized page, 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 this one page, 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 midterm will cover all material from the beginning of the quarter through Dynamic Programming (i.e. everything through Homework 5). This includes all of:

  • Stable Matching
  • Graph Algorithms and aymptotic analysis
  • Greedy Algorithms
  • Divide and Conquer Algorithms
  • Dynamic Programming Algorithms.

To give you a sense for what to expect, here are some practice exams for you:

We will additionally have a review session at 4:30pm on Tuesday February 18 in Bagly 131 (i.e. the exam room). During that review session we will discuss practice exam 1. There will be additional review in your regular section on 2/13. Office hours are also certainly a resource for preparing for the exam (Nathan will hold some on Tuesday 2/18 since 2/17 is a holiday).

2.2 Final

Your final exam will occur at 2:30pm on Monday March 17. Because the course scheduled into the final exam block after ours does not have a final exam, you will have until 5:20pm to take the exam. Again, if you have anticipated conflicts with this time, please let Prof. Brunelle.

You will be permitted 1 letter-sized page, 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 this one page, 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 midterm content as well as:

  • Max flow, min cut, and applications thereof
  • Linear Programming
  • NP Completeness

Expect the exam to contain roughly 8 short answer questions and roughly 4 long-form questions (the exact numbers will depend on the diffucly level of the specific questions selected). We have provided a sample exam below. Note that this sample exam is actually slightly longer than the actual final will be (it has 10 short answer and 6 long-form questions). We provided more questions in the practice in order to demonstrate a broader variety of questions you might see on the actual exam.

practice final (solutions)

We will discuss this practice exam during a review session on Friday 3/14 4:30pm-6:30pm in CSE2 room G20.