CS142: Homework 3

Homework problems are intended to give you more practice with shorter programs than the larger “projects” do. Typically these problems will also give you an idea of what you might see on tests. You also get immediate feedback.

This homework contains 5 problems. The first three are CodeCheck problems. The last two are not in CodeCheck, and are given below. To submit the homework, you can upload problems 4 and 5 to canvas or turn in them in on paper.

Important: If CodeCheck has been not saving your work, try making sure to click the “CodeCheck” button towards the button whenever you walk away for a bit, even if you’re not ready to test your code. If you’re still having problems, you can also paste in the code and/or screenshots of all the test cases passing when you submit to Canvas.

Here’s the link for the assignment.

When you’re all done, paste your CodeCheck ID into the Canvas assignment and submit it.

Problems 4 and 5:

(Remember, these are intended to serve as practice for the midterm, so it is recommended to do these on pencil and paper, at least as a first attempt.)

• Problem 4: Using the class code for binary search linked here, draw a recursion diagram for running the recursive version of binary search on the array [7, 12, 18, 20, 25, 36, 39, 42] with key of 39. The diagram should clearly show all recursive calls to the function, plus the values for low, high, and mid as the search progresses, and the return value from each recursive call. Your diagram should resemble those done in class and during labs.

• Problem 5: Using the same code as problem 4, explain how to change the code to make binary search work on an array that is sorted in reverse order, that is, high to low rather than low to high. You may either explain each change to the code by referencing each line and saying what needs to be changed, or print out a copy of the code and physically write the changes on top of the old code, or you may re-copy (or re-type) the old code and change it.