Assignment 2

Due Friday January 25, 2013 at noon.

Note: Please submit your written work in a single .txt or .pdf file.

1. Recall the Kinder Surprise Egg question from Assignment #1. Consider the following solution:

   1. Randomly choose two eggs and put them on the balance. (One egg on each side.)
   2. If the balance shows that one is lighter than the other then that is the egg we are looking for.
   3. If the balance shows that the two eggs are the same weight, then put these two eggs aside and repeat the procedure with the remaining eggs not checked yet.

   First convince yourself that this solution will always find the egg you are looking for. Each time we put two eggs on the balance we are doing a comparison. Answer the following questions:

   1. What is the minimum number of comparisons needed to find the light egg? This is the best case scenario (when we are really lucky).
   2. What is the maximum number of comparisons needed to find the light egg? This is the worst case scenario (when we are unlucky).
   3. What is worst case and best case number of comparisons needed if here were n eggs instead of just 8. (And still 1 light egg.)

2. You now have 8 Kinder Surprise Eggs and all of them have a toy inside. Each toy weighs (significantly) differently from the rest. You are told that two of the eggs have the same toy inside and all the rest of the eggs have different toys. Thus, there are 7 different toys in the 8 eggs.

   You are again given a balance, but this balance can only fit one egg on each side. You do not want to face the disappointment of opening up two eggs with the same toy inside so you need to find which two eggs have the same toy (you can give one of these to your younger sibling or friend). Answer the following:

   1. Give an algorithm to find the pair of eggs with the same toy inside.
   2. What is the best case number of comparisons needed to find the pair of eggs with the same toy with your algorithm?
   3. What is the worst case number of comparisons needed to find the pair of eggs with the same toy with your algorithm?
   4. What is the best and worst case number of comparisons needed to find the pair of eggs with the same toy with your algorithm if there were n eggs instead of just 8 (and still just one pair with the same toy inside).

3. Describe a process to plot a histogram of the ages of all the students in COMP1405/1005. (About 150 students.) Don't actually write the program, just give a plan, including listing variables and giving details of the actions you would take (if you were going to write a program).

Note: For all of your sketches, the output window should have width and height at least 200 (but do not make them extremely large).

Note: Do not use setup() or draw().

4. Consider the parametric representation of a curve in the xy-plane given by

      x = (a-b)*cos(t) + b*cos(t*(a/b-1)) 
      y = (a-b)*sin(t) - b*sin(t*(a/b-1)) 
   

   Here, a and b are some fixed constants (that you choose) and t is the only independent variable. For many values of t, you can compute x,y pairs and display them (using the point() function).

   Let k = a/b. Write a sketch that nicely shows four curves on the screen at the same time for the values k = 0.65, 1.4, 2.5, 5. The time to generate the curves should not be excessive.

   Note: Nicely means that the four curves look like curves (and not a bunch of disconnected dots), do not overlap, do not extend outside of the display window and are roughly the same size.

   Note: You can see what your curves should look like here.

5. Draw a grid on the screen. Your grid should have exactly 10 horizontal lines and 20 vertical lines. All the lines should be equally spaced on the screen, no matter how big the output window is. (Make your output window large enough to have the grid displayed nicely.)

6. Draw a rectangular spiral on the screen that fills the entire screen.

7. Make your output window have width twice as much as the height (600x300 or 500x250). Draw an ellipse centred in the window that is almost as big as possible. There should be at least 10 pixels between any wall of the window and any part of the ellipse. You will simulate an erratic bug that is on the screen and wants to move outside of the ellipse. Starting from the centre of the ellipse the bug will randomly move either one pixel up, down, left or right. The bug will keep moving until it has left the ellipse.

   When the bug escapes, you will display the number of moves the bug made. Moving backwards counts as a move.

   Note: Your sketch will not actually see the bug moving, but will show a trace of its path and the number of moves.

8. Modify the bug question from above so that when the bug is moving, it never steps backwards. The very first move can be any of the four directions.