Binary Search (Feb 15)
As mentioned in class, it wasn't possible to cover all the steps for each question, within the single tutorial.
Try to go through them and make sure they make sense. [T10TutorialExercises.pdf][104KB]
Question 5 is all about understanding the algorithm. Specifically, we are examining all the bases cases, and showing that the preconditions and postconditions hold during recursion.
Question 6 bounds the number of recursive calls the algorithm can make in the worst case, which helps us when we need to solve the recurrence relation later.
Questions 7 and 8 use the above to conduct a correctness proof. You can see how this is done in slides 18-21, from lecture 15.
The Monday after reading week, we will go through A2. However, A2 is relatively simple compared to A1, and is mostly coding/implementation. If you were able to implement the JUnit test cases in A1, and you understood the queues tutorial, then you should be able to complete this assignment in maybe... ~3 hours (my guess). Feel free to start and finish early, or wait until we discuss it in class.