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.

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 know during the first week of class.