Exercises should be completed on your own.

1. Have you thoroughly read the course policies on the webpage?

[We are expecting: The answer yes.]

1. See the IPython notebook ipynb for Exercise 1. Modify the code to generate a plot that convinces you that T(x) = O(g(x)).¹

[We are expecting: Your choice of c, n₀, the plot that you created after modifying the code in Exercise 1, and a short explanation of why this plot should convince a viewer that T(x) = O(g(x)).]

2. See the IPython notebook ipynb for Exercise 2, parts A, B and C.
   • What is the asymptotic runtime of the function numOnes( lst ) given in the Python notebook? Give the smallest answer that is correct. (For example, it is true that the runtime is O(2ⁿ), but you can do better).

[We are expecting: Your answer in the form The running time of numOnes( lst ) on a list of size n is O( )., and a few sentences informally justifying why this is the case. ]

• Modify the code in ipynb to generate a picture that backs up your claim from Part (A).

[We are expecting: Your choice of c, n₀, and g(n); the plot that you created after modifying the code in Exercise 2; and a short explanation of why this plot should convince a viewer that the runtime of numOnes is what you claimed it was.]

• How much time do you think it would take to run numOnes on an input of size n = 10¹⁵?

[We are expecting: Your answer (in whichever unit of time makes the most sense) with a brief justification, that references the runtime data you generated in part (B). You dont need to do any fancy statistics, just a reasonable back-of-the-envelope calculation.]

3. Using the definition of big-Oh, formally prove the following statements.

• 2 n + 6 = O( n) (Note that you gave a proof-by-picture of this in Exercise 1).
• n² = (n) (c) log₂(n) = (ln(n)) (d) 4ⁿ is not O(2ⁿ).

[We are expecting: For each part, a rigorous (but short) proof, using the definition of O(),(), and ().]

¹Note: There are instructions for installing Jupyter notebooks in the pre-lecture exercise for Lecture 2.

Problems

You may talk with your fellow CS161-ers about the problems. However:

• Try the problems on your own before
• Write up your answers yourself, in your own words. You should never share your typed-up solutions with your collaborators.
• If you collaborated, list the names of the students you collaborated with at the beginning of each problem.

1. In class we discussed Karatsubas algorithm for n-digit integers written in base 10. That is, for an integer x, we wrote , for x_i {0,,9}. But we can also consider an n-bit integer y written in base 2: , for y_i {0,1}. Or we can think about an n-hexadecimal integer z written in base 16: , for z_i {0,,15}.^[1]

Your friend has come up with the following argument that integer multiplication can be done in O(1) time. The argument has three parts:

• Whatever base we choose to write the numbers out in, Karatsubas algorithm correctly findsthe product of those numbers. For example, if we wanted to multiply the numbers 11010011 and 01011010 (which are written in binary), we could do that by recursively performing three multiplications involving the numbers 1101,0011,0101, and 1010.
• For a given number x, the length of xs base-b representation is decreasing as b For example, the same number x = 1024 (base 10) can be written as
  • 1000000000 base 2 (10 bits)
  • 1024 base 10 (4 digits)
  • 400 base 16 (3 hexits)

(c) Suppose we want to multiply two numbers x and y. Part (b) means that theres some largeenough b so that the base-b representations of x and y have length n = O(1). Then we run Karatsubas algorithm in this base (which works by part (a)), and it takes time O(n^1.6) = O(1) because n = O(1). Therefore we can multiply any two integers in time O(1).

Unfortunately (from the perspective of fast integer multiplication) your friends argument is flawed in at least one place. Which of their steps are faulty and why?

[We are expecting: For each of (a), (b), and (c), either assert that your friends logic is correct, or give a brief argument about why it is wrong. You do not need to give a formal proof in either direction.]

2. On an island, there are trustworthy toads and tricky toads. The trustworthy toads always tell the truth; the tricky toads may lie or may tell the truth. The toads themselves can tell who is tricky and who is trustworthy, but an outsider cant tell the difference: they all just look like toads.

You arrive on this island, and are tasked with finding the trustworthy toads. You are allowed to pair up the toads and have them evaluate each other. For example, if Tiffany the Toad and Tomas the Toad are both Trustworthy Toads, then they will both say that the other is trustworthy. But if Tiffany the Toad is a Trustworthy Toad and Tyrannus the Toad is a Tricky Toad, then Tiffany will call Tyrannus out as tricky, but Tyrannus may say either that Tiffany is tricky or that she is trustworthy. We will refer to one of these interactions as a toad-to-toad comparison. The outcomes of comparing toads A and B are as follows:

Suppose that there are n toads on the island, and that there are strictly more than n/2 trustworthy toads.

In this problem, you will develop an algorithm to find all of the trustworthy toads, that only uses O(n) toad-to-toad comparisons. Before you start this problem, think about how you might do thishopefully its not at all obvious! Along the way, you will also practice some of the skills that weve seen in Week 1. You will design two algorithms, formally prove that one is correct using a proof by induction, and you will formally analyze the running time of a recursive algorithm.

• Give a straightforward algorithm that uses O(n²) toad-to-toad comparisons and identifies all of the trustworthy toads.

[We are expecting: A description of the procedure (either in pseudocode or very clear English), with a brief explanation of what it is doing and why it works.]

• Now lets start designing an improved algorithm. The following procedure will be a building block in our algorithmmake sure you read the requirements carefully!

Suppose that n is even. Show that, using only n/2 toad-to-toad comparisons, you can reduce the problem to the same problem with less than half the size. That is, give a procedure that does the following:

• Input: A population of n toads, where n is even, so that there are strictly more than n/2 trustworthy toads in the population.
• Output: A population of m toads, for 0 < m n/2, so that there are strictly more than m/2 trustworthy toads in the population.
• Constraint: The number of toad-to-toad comparisons is no more than n/

[We are expecting: A description of this procedure (either in pseudocode or very clear English), and rigorous argument that it satisfies the Input, Output, and Constraint requirements above.]

• [This problem is NOT REQUIRED, but you may assume it for future parts.] Extend your argument for odd n. That is, given a procedure that does the following:
  • Input: A population of n toads, where n is odd, so that there are strictly more than n/2 trustworthy toads in the population.
  • Output: A population of m toads, for 0 < m dn/2e, so that there are strictly more than m/2 trustworthy toads in the population.
  • Constraint: The number of toad-to-toad comparisons is no more than bn/

(?) For all of the following parts, you may assume that the procedures in parts (b) and (c) exist even if you have not done those parts.

• (1 pt.) Using the procedures from parts (b) and (c), design a recursive algorithm that uses O(n) toad-to-toad comparisons and finds a single trustworthy toad.

[We are expecting: A description of the procedure (either in pseudocode or very clear English). ]

• Prove formally, using induction, that your answer to part (d) is correct.

[We are expecting: A formal argument by induction. Make sure you explicitly state the inductive hypothesis, base case, inductive step, and conclusion.]

• Prove that the running time of your procedure in part (d) uses O(n) toad-to-toad comparisons.

[We are expecting: A formal argument. Note: do this argument from scratch, do not use the Master Theorem.]

• Give a procedure to find all trustworthy toads using O(n) toad-to-toad comparisons.

[We are expecting: An informal description of the procedure. ]

[1] You may be used to representing number in hex on a computer, where it doesnt use symbols 0,,15 but rather 0,,9, along with the symbols A,B,C,D,E,F. In fact, this is the same thing, we just read A as 10, B as 11, and so on. So in hex, 1AF = 1 16² + 10 16¹ + 15 16⁰ = 431 base 10.

[2] This is the trickiest part of the problem set! You may have to think a while.