lab 7: challenge problems

EN47/COMP9, Fall 2009

Out: November 5, 3:00pm
Due: November 17, 3:00pm (Note: This is a Tuesday.)

overview

In today's lab, you will choose one of the three "challenge problems" below. This is an opportunity to apply your knowledge to an unfamiliar scenario, in which the terms of a problem are not necessarily well-defined.

challenge 1: binary search

This problem is very similar to Lab 6. Given an array of integers sorted in ascending order, your program should allow the user to search through the sorted array. Your program interaction should look something like that of Lab 6, however, instead of linear search, you should implement binary search. Below is an outline of the recursive binary search algorithm. The algorithm looks for a target in a a pre-sorted array A. The parameters low and hi specify the range of array elements to search.

int binary_search(int A[], int low, int hi, int target) 
   mid = (low + hi) / 2 
   IF (low is greater than hi) 
      RETURN -1 // Base case. Target was not found. 
   ELSE IF (value at mid equals target) 
      RETURN mid 
   ELSE IF (value at mid is greater than target) 
      RETURN binary_search ( A, low, mid - 1, target ) 
   ELSE // value at mid is less than target 
      RETURN binary_search ( A, mid + 1, hi, target )

To start this program, you may want to copy all of your files from Lab 6 to a new directory. You can use your bubble sort function to sort the array. You may use the LEDA functions to visualize the steps in your search algorithm, but this is not required.

When you are satisfied with your program, submit it using provide:

provide comp9 lab7binary lab7.cpp

(Substitute the name of your file for lab7.cpp if necessary)

challenge 2: fractals

Consider this fractal pattern below, which is composed of asterisks and spaces.

*
* * 
  *
* * * *
    *
    * *
      *
* * * * * * * *
        *
        * *
          *
        * * * *
            *
            * *
              *

Write a program that uses recursion to generate patterns such as this. Your program should take as input the length of the longest line in the pattern (this should be a power of 2 greater than 0). Think about how the pattern is a fractal. (You may like to read more about fractals online.) Can you find two smaller versions of the pattern within the large pattern?

When you are satisfied with your program, submit it using provide:

provide comp9 lab7fractal lab7.cpp

(Substitute the name of your file for lab7.cpp if necessary)

challenge 3: towers of hanoi

The Towers of Hanoi is a famous mathematical puzzle. You have three pegs and a number of disks of different radii which can slide onto any peg. You start with the disks stacked on one peg; the disks are stacked in order of size, with the largest disk at the bottom.

The objective of the puzzle is to move the entire stack to another peg, while obeying the following rules:

• You may only move one disk at a time.
• Each move consists of taking the topmost disk from one of the pegs and sliding it onto another peg (on top of the disks that are already on that peg).
• No disk may be placed on top of a smaller disk.

The website linked above outlines one recursive approach to solving this problem. Write a program that asks the user to enter the initial number of disks, then prints the list of moves required to solve the puzzle. Each move should be of the form "Move the disk from peg 1 to peg 3". You are welcome to consult books and the web to find algorithm outlines, however you must write your own solution and cite any references used.

When you are satisfied with your program, submit it using provide:

provide comp9 lab7hanoi lab7.cpp

(Substitute the name of your file for lab7.cpp if necessary)