Compsci 100e, Fall 2009, Group Quiz/Prelab

We will do the rest of the problems together.

Group members: name and NetID for each

___________________     ___________________   ___________________


___________________     ___________________   ___________________

Prelab/In-class Exercises

0. Consider the following three algorithms for determining whether anyone in the room has the same birthday as you.
   
   Algorithm 1: You say your birthday, and ask whether anyone in the room has the same birthday. If anyone does have the same birthday, they answer yes.
   
   Algorithm 2: You tell the first person your birthday, and ask if they have the same birthday; if they say no, you tell the second person your birthday and ask whether they have the same birthday; etc, for each person in the room.
   
   Algorithm 3: You only ask questions of person 1, who only asks questions of person 2, who only asks questions of person 3, etc. You tell person 1 your birthday, and ask if they have the same birthday; if they say no, you ask them to find out about person 2. Person 1 asks person 2 and tells you the answer. If it is no, you ask person 1 to find out about person 3. Person 1 asks person 2 to find out about person 3, etc.
   
   
   1. For each algorithm, what is the factor that can affect the number of questions asked (the "problem size")?
      
      
   2. In the worst case, how many questions will be asked for each of the three algorithms?
      
      
   3. For each algorithm, say whether it is constant, linear, or quadratic in the problem size in the worst case.

1. An algorithm takes 0.5ms for input size 100. How long will it take for input size 500 if the running time is the following?

   What assumptions do you have to make in order to answer this problem?

   1. O(n)

   2. O(nlogn)

   3. O(n²)

   4. O(n³)

2. Order the following functions by growth rate. Indicate which functions grow at the same rate.
   n, √n, n^1.5, n², n log n, n!, n log log n, n log² n, n log (n²), 2/n, 2ⁿ, 2^n/2, 37, n³, nⁿ, n² log n

3. For each of the methods below indicate the running time of the method, in terms of n, using O-notation. You must justify your answers for credit. In all examples assume n is positive.
   1. public int calc(int n){ int sum = 0; for(int k=0; k < n; k++){ sum++; } for(int k=0; k < n; k++){ sum++; } return sum; }
   2. public int clunk(int n){ int sum = 0; for(int j=0; j < n; j++){ for(int k=0; k < j; k++){ sum++; } } return sum; }
   3. public int goduke(int n){ int sum = 0; for(int k=1; k <= n; k = k * 2){ sum++; } return sum; }
   4. public int stuff(int n){ int p = 0; while (p*p < n){ p++; } return p; }

4. What is the complexity (using big-Oh) of the call calc(N) for the function below? Why? int calc(int n) { int sum = 0; for(int k=0; k < n; k++) { sum += k; } for(int j=1; j <= n; j++) { sum *= j; } return sum; }

5. What is the complexity (using big-Oh) of the call calc2(N) for the function below? Why? int calc2(int n) { int sum = 1; for(int k=0; k < n; k++) { for(int j=1; j <= k; j++) { sum *= j; } } return sum; }
6. What is the complexity (using big-Oh) of the call calc3(N) for the function below? Why? int calc3(int n) { int prod = 1; for(int k=n; k >= 1; k = k/2) { prod *= k; } for(int k=0; k < n; k++) { prod += k; } return prod; }

7. What is the complexity (using big-Oh) of the call calc4(N) for the function below? Why? int calc4(int n) { int prod = 1; for(int k=0; k < n; k++) { for(int j=k; j >= 1; j = j/2) { prod *= j; } } return prod; }
8. The method closetPair below returns the two points in an array that are closest to each other (the points are returned in a two-element array so that two values can be returned).

   What is the big-Oh complexity of this code for an N-element array? It is one of O(N), O(N²), O(log N) or O(N log N). Justify your answer briefly.

   public class PointStuff { public static class Point { int x; int y; public Point(int x, int y){ this.x = x; this.y = y; } public double distanceFrom(Point p){ return Math.sqrt( (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y) ); } } public Point[] closestPair(Point[] list){ double closest = Double.MAX_VALUE; Point[] ret = new Point[2]; for(int j=0; j < list.length; j++){ for(int k=j+1; k < list.length; k++){ if (list[j].distanceFrom(list[k]) < closest){ ret[0] = list[j]; ret[1] = list[k]; } } } return ret; } }
9. Bill shows you an algorithm to optimally choose classes for all students at Duke. You, being a good Computer Science student, notice that the big-Oh complexity of the algorithm is O(2ⁿ) where n is the number of students. However, Bill demonstrates the program for a sample of 100 students and it returns the schedules almost immediately.

   Bill says that his algorithm is good enough for Duke. He mentions something about Moore's Law and states that ``Computers are getting faster at an exponential rate. That is, every 18 months, they double in speed. Even if the program is not fast enough now, it will be soon.''

   Bill is off a little bit on what Moore's law means. However, given that computers continue doubling in speed every 18 months, will the O(2ⁿ) algorithm ever be practical? Explain why or why not?

Submitting