CSE 373 Homework Assignment 2

Problem 1

(5 pts) For each of the following scenarios, indicate stack, queue, or neither, based on whether or not it is best simulated with a stack (or multiple stacks), a queue (or multiple queues), or is too complex for either a stack or a queue to simulate with constant time operations:

1. Customers wait in line at a bank. A customer can only enter the line at the very end. When a teller is ready, the first person in line is handled by the teller.

2. Customers wait in checkout lines at a supermarket. A customer can enter any of the lines, but only at the very end. When a cashier is ready, the first person in the line corresponding to the cashier is handled by the cashier.

3. Several identical resources, each with a unique ID, are being used by many processes. Only one process can have access to a single resource at a time. When a process needs one of the resources, it takes the one that was most recently freed.

4. Same as above, but this time, when a process needs one of the resources, it takes the free one with the smallest ID.

5. A user is browsing the web. He/she can either click on a link in the current page (which causes a new page to be displayed), or press the "Back" button, which causes the previous page to be displayed.

Problem 2

(18 pts) For this problem, you will need to write some code in either C++ or Java. We've provided everything you need to get started:

• C++ skeleton file
• Java skeleton file

For each of the following six program fragments:

1. Give an analysis of the running time. Big-Oh will suffice.

2. Implement the code in either C++ or Java, and give the running time (in milliseconds) for several values of n. We've set up the skeleton files to make this easier. Look for an "INSERT YOUR CODE HERE" comment. Also, the skeleton is set up to read the value of n from the command line.

3. Compare your analysis with the actual running times.

   1. sum = 0;
      for (i=0; i<n; i++)
      	sum++;
      

   2. sum = 0;
      for (i=0; i<n; i++)
      	for (j=0; j<n; j++)
      		sum++;
      

   3. sum = 0;
      for (i=0; i<n; i++)
      	for (j=0; j<n*n; j++)
      		sum++;
      

   4. sum = 0;
      for (i=0; i<n; i++)
      	for (j=0; j<i; j++)
      		sum++;
      

   5. sum = 0;
      for (i=0; i<n; i++)
      	for (j=0; j<i*i; j++)
      		for (k=0; k<j; k++)
      			sum++;
      

   6. sum = 0;
      for (i=1; i<n; i++)
      	for (j=1; j<i*i; j++)
      		if (j % i == 0)
      			for (k=0; k<j; k++)
      				sum++;
      

Problem 3

(12 pts) For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t assuming that the algorithm to solve the problem takes f(n) microseconds. (A microsecond is one millionth of a second.) The first row has been completed to get you started.

Extra Credit Problem

(10 pts) Recall the definition of the Fibonacci numbers:

• f₀ = 1
• f₁ = 1
• f_i = f_i-1 + f_i-2 for i > 1.

In this problem, you will take steps towards an algorithm that computes the n^th Fibonacci number in O(log n) time.

1. Use induction to prove that, for all i > 1:

   • f_i² + f_i-1² = f_2i
   • f_if_i-1 + f_i-1f_i-2 = f2i-1

2. How could we use this fact to design a better Fibonacci number algorithm? Give a high level description of the algorithm.