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.

2 Exams

Your midterm exam will be at 6:00pm-7:30pm on Wednesday February 19 in lieue of a normal class meeting. If you anticipate conflicts with this time, please let Prof. Brunelle know during the first week of class.

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.