Homework Assignment 6

CS1311-Scheme Spring 2001
Due 8:00 AM, Friday March 30, 2001

Objectives:

• Learn about vectors.
• Learn about ninjas.

The Scheme pirates have been overrun by a sneaky clan of Scheme ninjas. They crept aboard in the middle of the night and took control of the ship before the night watch could sound the alarm. How did they accomplish such an astounding feat? You see, ninjas are a sneaky lot. Their chief weapon is surprise, and they achieve this surprise by being fast. Really fast. I mean quick-like-a-rabbit. Seriously.

It's up to you to save the crew from these ninjas, and to beat these ninjas you're going to have to be fast. Really fast. I mean quick-like-a-rabbit. Seriously.

Problem 1
10 points
You know that the ninjas are going to try to break into Captain Kurt's computer by trying to guess his password. Kurt keeps all of the ship's passwords in a Scheme list, and the password to his computer is the last element in the list. Fortunately, you just happen to have these same passwords in a vector. You know those ninjas are trying as hard as they can to get to that last element in the list, but you know you can beat them there. Explain how it is that you can beat the ninjas to the last element. For maximum credit include Big-O reasoning in your answer.

Problem 2
25 points
You've stopped the ninjas from getting into the computer, so they're momentarially stunned. Now's the time to confuse them! The ninjas are systematically searching the ship to find any stowaways, and they're keeping the room numbers in a vector. You've got some ninja repellant somewhere in your room, but unfortunately your room's a mess! It's going to take you some time to find the spray, but your room number is early in the list. Buy yourself some time by writing a function called my-reverse-vector which will reverse a vector and return the number of items in the vector. (Remeber the difference between pass-by-value and pass-by-reference). Sample usage:

#t
> (define x #(1 2 3 4 5 6 7 8 9))
> x
#9(1 2 3 4 5 6 7 8 9)
> (my-reverse-vector x)
9
> x
#9(9 8 7 6 5 4 3 2 1)

Problem 3
5 points
Let's say you wanted to leave the original vector alone and return a new vector instead. Explain how you'd go about doing this.

Problem 4
30 points
Reversing the order of the rooms bought you just enough time to sneak out of your room and into a janitor's closet. There's a crack in the floorboard and from here you can see into the cargo hold where the ninjas have all of the crew tied up inside one of those big cargo-net things that you always see in movies. You think you can reach your arm through the crack and swing the net, but you're not sure if you can swing them far enough. You do some scratchwork and get to the point where you need to take the dot product of two vectors to get the answer. Write a function called dot-product which will take in two vectors of the same length and return their dot product. You get the dot product of two vectors by summing the product of corresponding elements. Or to put it another way, you add the product of the first two elements with the product of the second elements with the product of the third elements, etc... So for example:

>(dot-product #(1 2 3) #(4 5 6))
32

Problem 5
30 points

HA HA! we goofed.

Yup, we put on a problem for homework 6 which will not technically be covered
until next weekish.

Thus, we are simplifying problem 5.

You do not have to write Selection-sort.  Rather, we are having you
write swap:

   

   Write a function called swap that takes in a vector and two indecies and
   swaps the values at the indecies.  You may assume that the indecies will
   be in the range of the vector:

   > (define x #(1 2 3 4 5))
   > x
   #5(1 2 3 4 5)
   > (swap x 0 4)
   > x
   #5(5 2 3 4 1)
   > (swap x 3 0)
   > x
   #5(4 2 3 5 1)

If you've already finished selection sort, good for you!  That problem will
appear on the next homework.

Sorry

Dan

1. Go through the vector and find the index of the largest element.
2. Swap the largest element into the last entry of the vector. Now the largest element is in place.
3. Go through the vector up through the next-to-last element and find the largest element.
4. Swap the element you just found (it'll be the second largest element) with the second element from the end. Now the largest two elements are in place.
5. Repeat this process until you've moved all of the elements into their proper place.

Our Vector:
+---+---+---+---+---+
| 4 | 2 | 5 | 8 | 1 |
+---+---+---+---+---+
  0   1   2   3   4   <----index

Find the index of the largest value:

+---+---+---+---+---+
| 4 | 2 | 5 | 8 | 1 |
+---+---+---+---+---+
  0   1   2   3   4  
              ^   ^
              |	  +-----Last place
	      |
             Largest

Swap this element with the element in the last place:

		  +---Largest element now in last spot.
                  |
                  V
+---+---+---+---+---+
| 4 | 2 | 5 | 1 | 8 |
+---+---+---+---+---+
  0   1   2   3   4  


Now the last element is in place.  Look through the vector from index
0 to index 3 for the largest element (this will be the second largest
element in the vector).  

	  +---Largest element from index 0 to index 3
          |
          V
+---+---+---+---+---+
| 4 | 2 | 5 | 1 | 8 |
+---+---+---+---+---+
  0   1   2   3   4  

Swap this element with the element in index 3:

              +---+----Now the two largest elements are in position.
              |   |
              V   V
+---+---+---+---+---+
| 4 | 2 | 1 | 5 | 8 |
+---+---+---+---+---+
  0   1   2   3   4  

Repeat until you've swapped all of the elements into place:

+---+---+---+---+---+
| 1 | 2 | 4 | 5 | 8 |
+---+---+---+---+---+
  0   1   2   3   4