Assignment 2: Poking Holes in Algorithms

Due: 10:30 p.m., 2 February 2016

Summary: For this assignment, you will identify the parts of an algorithm, find some problems with that algorithm, and write an improved version.

Purposes: The purpose of this assignment is for you to practice identifying the parts of algorithms, and to get some experience thinking carefully about the edge cases where an algorithm could go wrong.

Collaboration: You must work with your assigned partner(s) on this assignment. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.

Submitting: Email your answer to <CSC151-02-grader@grinnell.edu>. The title of your email should have the form CSC 151 Assignment 2: Exploring Algorithms and should contain your answers to all parts of the assignment. Scheme code should be in the body of the message.

Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.

Background

In any sufficiently large group of people, the likehood that at least two people have the same birthday is surprisingly high (over 50% for a group of 23 people, source: Wikipedia). While this is an interesting theoretical result, it would be nice to test it in class. The following algorithm is supposed to tell us whether we have any common birthdays in this class, but it has some problems. Use this algorithm for all four parts of the assignment.

Everyone in the class should run around the room at random, and then line up.
We will call the first student in line the current student, and the student behind them the "next student".
The current student asks the next student what day of the month they were born on (e.g. the 12th).
If the current student was born on a larger-numbered day of the month than the next student, go to step 1.
If the current student is not at the end of the line, call the next student in line the current student and the student behind them the next student, then go to step 3. Otherwise, continue on to step 6.
Let the number of students with a shared birthday be zero.
Let the current student be the first student in line.
If the current student was born on the same day of the month as the next student in line, add one to the number of students with a shared birthday.
If the current student is not last in line, let the next student in line be the current student and go to step 8. Otherwise, continue.
Report the number of students with a shared birthday. The algorithm is complete.

Assignment

Problem 1: Understanding the Birthday Algorithm

Many algorithms can be broken down into smaller steps. For example, this algorithm has two "stages," steps 1-5 and steps 6-9. Explain, in your own words, what each of these stages is supposed to accomplish.

a. What is the purpose of steps 1-5 in the algorithm above?

b. What is the purpose of steps 6-9 in the algorithm above?

Problem 2: Parts of the Birthday Algorithm

The algorithm above uses all six of the parts of an algorithm covered in the Algorithms Reading. Find an example of each piece of an algorithm and list the step(s) that demonstrate that algorithmic building block. Briefly explain your choice.

a. Identify an example of sequencing in the algorithm above. Identify the step(s) that demonstrate this algorithmic building block, and explain your choice.

b. Identify an example of repetition in the algorithm above. Identify the step(s) that demonstrate this algorithmic building block, and explain your choice.

c. Identify an example of a conditional in the algorithm above. Identify the step(s) that demonstrate this algorithmic building block, and explain your choice.

d. Identify an example of a variable in the algorithm above. Identify the step(s) that demonstrate this algorithmic building block, and explain your choice.

e. Identify an example of a parameter in the algorithm above. Identify the step(s) that demonstrate this algorithmic building block, and explain your choice.

f. Identify an example of a subroutine in the algorithm above. Identify the step(s) that demonstrate this algorithmic building block, and explain your choice.

Problem 3: Problems with the Birthday Algorithm

The birthday algorithm provided with this assignment has some problems. Find two problems with the algorithm and explain them below. At least one of the problems you identify should relate to the correctness of the algorithm rather than issues with clarity, efficiency, or precision. When you describe a problem with the algorithm that will cause it to produce an incorrect result, provide an example situation where you would get the wrong answer.

Problem 4: Fixing the Birthday Algorithm

Write a new birthday algorithm that will produce the right answer. Make sure to address the issues you identified in problem 3. Explain why you think your new algorithm will work, and the high level idea behind your approach.

Problem 5: Translating Math to Scheme

You may recall from your mathematics classes that there is a nice formula for the two roots of the quadratic equation ax² + bx + c = 0. (If you don't recall, ask a friendly math major.)

Suppose we've defined three variables, a, b, and c.

> (define a ...)
> (define b ...)
> (define c ...)

Write instructions for computing the two roots of the corresponding quadratic equation.

> (define root1 ...)
> (define root2 ...)

In turning in your assignment, make sure to show a few different examples of your instructions in action. For example,

> (define a 1)
> (define b 2)
> (define c -3)
> (define root1 ...)
> (define root2 ...)
> root1
-3
> root2
1

Important Evaluation Criteria

We will evaluate your work on the accuracy and level of detail you put into your answers. For problem 1, we expect that you will provided a correct high-level description of each stage, not just a reiteration of the steps in the provided algorithm. For problem 2, you will receive credit for correctly identified parts of the algorithm and the quality of your explanation. For problem 3, we will give credit for real issues that you identify and the example situations that show where the algorithm will go wrong. Finally, for problem 4 we will evaluate your algorithm's correctness, clarity, and the quality of your high-level description.