Assignment 2: Poking Holes in Algorithms

Due: Tuesday, September 6 by 10:30pm

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-01-grader@grinnell.edu. The subject of your email should be [CSC 151.01] Assignment 2 and should contain your answers to all parts of the assignment. Scheme code should be in the body of the message, not in an attachment.

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 were born on the same day of the year 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 how many students share a birthday with at least one other student in class, but it has some problems:

1. All the students in the class line up in an arbitrary order.
2. The instructor erases the whiteboard.
3. We will call the student at the front of the line student A.
4. We will call the student next in line student B.
5. Student B announces their birthday while student A listens.
6. Student A compares their own birthday to student B’s birthday.
7. If both birthdays are on the same day of the year, skip to step 11. If not, continue to step 8.
8. If student B is at the end of the line, go to step 14. Otherwise, continue to step 9.
9. The name “student B” will now refer to the next student in line behind our current student B.
10. Go to step 5.
11. The instructor writes one tally on the whiteboard.
12. Both students A and B exit the classroom.
13. If there is at least one student left in line, go to step 3. Otherwise, continue to step 14.
14. the number of tallies on the whiteboard is the number of students who share a birthday with at least one other student. Exit the algorithm

Assignment

Problem 1: Understanding the Birthday Algorithm

Explain, in your own words, the high-level idea behind this algorithm. Ambiguity is okay: the goal of this problem is to guess the intent of the algorithm designer, not the exact steps. If you believe the intent does not match the actual steps, try to summarize what you believe the algorithm designer meant to do.

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. You should use an approach roughly equivalent to what you summarized in problem 1.

Problem 5: Translating Math to Scheme

It is often useful to translate mathematical expressions to code. To practice this process, convert each of the following formulas to scheme code.

a. Suppose we have defined three variables, x, y, and z.

(define x ...)
(define y ...)
(define z ...)

Write instructions to define the following expressions using x, y, and z:

Your solution should have the form:

(define expr1 ...)
(define expr2 ...)
(define expr3 ...)

When you submit your assignment, make sure you show at least two examples of your translated formulas in action. For example,

> (define x 4)
> (define y 12)
> (define z 9)
> (define expr1 ...)
> (define expr2 ...)
> (define expr3 ...)
> expr1
3/4
> expr2
1 3/5
> expr3
0.769800358919501

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 the algorithm, 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. For problem 4 we will evaluate your algorithm’s correctness and clarity. Finally, for problem 5 we will grade your work strictly on correctness.