We finished Chapter 4 on sorting and searching and most of Chapter 7 on abstraction and parity. Next week we will begin Chapter 8 on mazes and graphs.
We briefly talked about: Sokoban (this version contains the classic levels). Good brain-training.
The midterm will be 5/7 for in-class students; registration for distance learning students is open.
There will be regular class after the midterm, which will take place in the first 90 minutes of class.
Note that the homework is due the week after the midterm.
Submission: you can submit the homework to me either by hardcopy in class or email it to me.
1. [Binary Search, 20pt] You are given an array
A = [2, 5, 9, 11, 12, 22, 30, 35, 37, 40, 49, 57, 82, 89].
2. [Selection Sort, 5pt] You are playing poker and get a hand of five cards. Assume you use the idea from selection sort to sort your hand (look for the smallest card in the remaining hand and swap it with the card just beyond the part you have already sorted). What is the largest number of swaps that you might have to make? Prove your result by including a hand that requires that number of swaps.
3. [Parity, 25pt] Picture a chessboard; you want to traverse the chessboard square by square starting at the upper left corner and going to the lower right corner, entering and leaving each square exactly once, with the exception of the first square, which you leave once and never reenter, and the last square which you enter once and never leave again. From a square you are only allowed to move to an adjacent square to the left, right, top or bottom (no diagonal moves).
4. [Graphs, 10pt] There's a famous game called "The Kevin Bacon Game". Before you read the exercise, familiarize yourself with the rules of the game, and try playing the game yourself at The Oracle of Bacon at Virginia.
5. [Extra Credit] Try the following game: there are 10 matches on the table;
alternate by removing either one or two matches in each move. The player who
removes the last match wins the game.
6. [Extra Credit] If you find any typos and mistakes in the lecture notes, please let me know.