Homework 5 (due 5/14)
CSC 202

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].

  1. [10pt] Perform a binary search to see whether x = 40 occurs in the array. Show what calls to the binary search algorithm are made (and the midpoint that is computed), similarly to how we did it in class.
  2. [10pt] Perform a binary search to see whether x = 17 occurs in the array. Show what calls to the binary search algorithm are made (and the midpoint that is computed), similarly to how we did it in class.

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).

  1. [3pt] Can you traverse an 7 x 7 chessboard this way? If so, show how it can be done.
  2. [2pt] Can you traverse a 8 x 8 chessboard this way? If so, show how it can be done.
  3. [5pt] After investigating the 7 x 7 and 8 x 8 cases, state a general result about the possibility of traversing an n x n chessboard in the manner described above. Hint: your answer will have to depend on n.
  4. [15pt] Prove the result you stated in part c. Hint: there will be two cases, depending on n.

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.

  1. [6pt] Describe how you would model the Kevin Bacon game as a graph. Hint: you need to determine what the vertices and the edges of your graph are. As a start: How would you model the actors in terms of graphs?
  2. [4pt] In your graph model what does it mean for somebody (like Paul Robeson) to have a Bacon number of 3?

5. [Extra Credit] Try the following game: there are 10 matches on the table; two players
alternate by removing either one or two matches in each move. The player who
removes the last match wins the game.

  1. Show that the player who goes first in this game can always win the game, by
    describing a winning strategy. Hint: A winning strategy is a set of rules
    that the player can follow in each move that guarantees a win in the end.
  2. If we start with 11 matches on the table, who can force a win, the first or
    the second player? Give a winning strategy for the player.
  3. Phrase a general result on which player can force a win in this
    game if we start with n matches on the table, n > 0.

6. [Extra Credit] If you find any typos and mistakes in the lecture notes, please let me know.
Marcus Schaefer
Last updated: May 1st, 2007.