Due 1:00 PM, Wednesday, 11 April 2018


CPSC 101b  Homework #8  D&C and Backtracking

REMINDER:  When discussing an assignment with other students, you may write on
a board or a piece of paper, but you may not retain any written or electronic
record of the discussion.  Moreover, you must engage in a full hour of mind-
numbing activity (e.g., watching back-to-back episodes of Gilligan's Island)
before you work on the assignment again.  This ensures that you can reconstruct
what you learned from the discussion, by yourself, using your own brain.  The
same rule applies to nonstudents and on-line sources.


1. (5 points) A majority element in a sequence of length N is an element that
   appears more than N/2 times.  For example, 2 is a majority element in the
   sequence {1, 2, 2, 2, 3} but no element is a majority element in the
   sequence {0, 1, 1, 1, 2, 0}

   Describe a divide-and-conquer algorithm that finds the majority element (or
   reports that none exists).  The only operation permitted is testing whether
   or not two elements of the sequence are equal.  Explain why your algorithm
   works as well as how.  You must explicitly identify the divide step, the
   subproblems that must be solved (which must be of this same form), the
   conquer step, and the base case(s).  For simplicity you may assume that N
   is a power of two.

   Note:  You can move elements around in the sequence if you think that would
   help, but there is no ordering of the elements (think of them as pictures,
   where it does not make sense to say that one picture is less than or greater
   than another).


2. The bishop in chess is a piece that can move to any square along either
   diagonal passing through its current square.  A One-Step Bishop's Path on an
   N x N board is a sequence of bishop's one-step moves (i.e., from the current
   square to one diagonally adjacent) that start at a given square and land on
   every other square of the same color.  A One-Step Bishop's Tour is such a
   path that leaves the bishop adjacent to the starting square (and thus able
   to complete the circuit).  For example, using the notation we developed for
   knight's paths, on a 3x3 board the sequence A2-B3-C2-B1 is both a path and
   a tour.

   a. (2 points) The four corners on a 5x5 board are all the same color.  Use
   backtracking to find a One-Step Bishop's Path on a 5x5 board starting from
   a square of the _other_ color (e.g., B1 or A2).  Is your path a tour?  If
   not, is there a tour?  You need not draw the search tree with all branches
   explored.

   Aside:  Since the four corners have only one diagonally adjacent square,
   there cannot be a One-Step Bishop's Path starting from any square of that
   color.

   b. (4 points) Use backtracking to search for a One-Step Bishop's Path on
   a 4x4 board, starting at an edge square that is next to a corner square
   (e.g., B1 or A2).  Draw the search tree with all branches explored while
   backtracking.

   Hint: There is no solution; the tree will have 20-30 nodes.


3. (1 point) How many hours did it take you complete the first two problems?


Reading:  Kernighan, Chapters 1 (What's In a Computer) and 3 (Inside the CPU).

							     CPSC-101b-04/03/18