abhi shelat

Midterm: Study guides and hints

Format

The midterm will be a take-home exam with no collaboration allowed. All work must be done individually, and you should not discuss the exam with anyone except the course staff. You can post private questions on Piazza for clarifications. I expect the exam to require 3-4 hours to solve and write up. You will have 36 hours (10x what I expect it to take) to finish the exam and submit to Gradescope.

You are allowed to use the lecture slides as a resource, but you are not allowed to use any other resources as aides on the exam, including but not limited to the internet, Wikipedia, the solutions to the homeworks, links from Piazza, etc.

  • Released: March 1st at Noon.
  • Due date: March 2nd at 11:59pm. No late exams will be accepted.

Topics

  • Divide and Conquer
  • Recurrences, Master’s theorem
  • Dynamic programming

Ways to prepare

  • Be sure to review the solutions to all of the homework problems.
  • Look over the problems presented in lecture on the “input/output” slide. Ask yourself, if you were presented this problem, would you know how to derive the proposed solution? If not, where do you get stuck? You can use the rest of the slides to check yourself. We have 12+ examples of problems that you should be able to solve by yourself.
  • You can look over the problems in CLRS and KT textbooks in the Divide and Conquer and Dynamic Programming sections and see if you can solve them.
  • Take a look over the quiz questions that I’ve asked. Can you answer them?

Sample midterm questions

We will post sample midterm questions that do not make the cut for the actual midterm here. We unfortuntaely do not have solutions for these problems. If you write up a solution, we are happy for you to share it on Piazza for others to study.

  1. Make sure you can solve and understand the following problems covered in class: Counting students, Karatsuba multiplication, Strassen Matrix multiplication, Arbitrage, Closest Pair of points, Median or i-th order statistics, FFT, LogCutter, Billboards, matrix-chain multiplication, typesetting, Gerrymandering, Seam carving.

  2. Recall Karatsuba multiplication could multiply $2$ $n$-word numbers using $3$ smaller $n/2$-word multiplication operations. In Toom-Cook multiplication, we divide the $n$-word inputs into 3 parts of size $n/3$, and we can compute the product using only 5 of the smaller multiplications. What is the running time of this approach? Express your answer in $\Theta$-notation.

  3. The Greek Diogenes spent his life searching for an honest man. Consider the Greek system today with a group of $n$ people. We can test a pair—lets call them Alice and Bob for simplicity—by asking them whether the other is honest. Honest Greeks always report truthfully, but the dishonest can report arbitrarily. Thus, the following outcomes are possible:

    • Alice says & Bob says

      • “Bob is honest” & “Alice is honest” : Either both are honest or both are dishonest
      • “Bob is honest”, “Alice is dishonest” : at least one is dishonest
      • “Bob is dishonest” & “Alice is honest” : at least one is dishonest
      • “Bob is dishonest” & “Alice is dishonest” : at least one is dishonest

    • A group of $n$ Greeks is moral if more than half are honest. Suppose we start with a moral group of $n$ Greeks. Describe a method that uses only $\lfloor n/2\rfloor$ pair-wise tests between the Greeks to find a smaller moral group of at most $\lceil n/2 \rceil$ Greeks.

    • Using this approach, devise an algorithm that classifies all Greeks as honest or dishonest using only $\Theta(n)$ pairwise tests. Prove the correctness of your algorithm and prove that only $\Theta(n)$ tests are used.

  4. (Take from Jeff Erickson’s book) Vankin’s Kilometer is a solitaire game played on an $n \times n$ square grid. The player starts by placing a token on any square of the grid. Then on each turn, the player moves the token either one square to the right, one square to the left, or one square down. However, to prevent infinite scores, the token cannot land on the same square more than once. The game ends when player moves the token off the edge of the board. Each square of the grid has a numerical value, which could be positive, negative, or zero. The player starts with a score of zero; whenever the token lands on a square, the player adds its value to his score. The object of the game is to score as many points as possible. For example, given the grid below, the player can score 8−6+7−3+4 = 10 points by placing the initial token on the 8 in the second row, and then moving down, down, right, down, down. (This is not the best possible score for this grid of numbers.)
    $$ \begin{array}[ccccc] -1 & 7 & -8 & 10 & 5 \\\ -4 & -9 & \color{red}{8} & -6 & 0 \\\ 5 & -2 & \color{red}{-6} & -6 & 7 \\\ -7 & 4 & \color{red}{7} & \color{red}{-3} & -3 \\\ 7 & 1 & -6 & \color{red}{4} & -9 \end{array} $$ Describe and analyze an efficient algorithm to compute the maximum possible score for a game of Vankin’s Kilometer, given the $n \times n$ array of values as input.

  5. Counting coin changes: Given a denomination of positive coins $c_1, c_2, \ldots, c_m$ and a value $n$ as input, how many ways can you make change for $n$? For example, with coins being ${1,2,3}$ the number of ways to get the value $4$ is $4$ as follows: ${1, 1, 1, 1}$, ${1, 1, 2}$, ${2, 2}$, ${3, 1}$. With coins being ${2, 5, 3, 6}$ the number of ways to get the value $10$ is $5$ as follows: ${2,2,2,2,2}$,${2,2,3,3}$,${2,2,6}$,${2,3,5}$,${5,5}$.