CSE 7350/5350

D.W. Matula

Homework Set # 1

Spring 2005

Due date:

8 Feb. '05

Measuring Algorithm Efficiency

Total Points:  CSE 7350 - 90 (CSE 5350 -70)

Reading:

 

 

(1) Chapters 1, 2 and 3 (pp 5-61) of text (Cormen,et.al., 2nd ed.);

(2) Preface and pp 1-33 of Computers and Intractability(Garey and Johnson)

 

Grading Policy:

Unless otherwise stated all problems are 10 points each. Partial credit is available on all problems. Late homework submitted within one week after the due date will incur a 10 point penalty on that homework set. (Videotape students add two weeks to deadlines.)

 

1.      [Comparing Running Times] Text problem 1-1, p. 13 measuring f(n) in nanoseconds.

2.      [Asymptotic Growth Rates]

a.   Text problem 3-2, p. 58. Do only for O, W, and Q.

b. Follow the instructions for problem 3-3 (a) for the following functions:

 

(5/2)n

n2

(lg n) !

lg2n

lg lg n

n2n

2n

2lg n

n!

n / lg n

1(constant)

 

3.     [Solution vs. Validation] (CSE 5350 do only Part 1 for 10 points / CSE 7350 do Parts 1 and 2 for 20 points)

Express the following five loosely described problems in Part 1 carefully in             { Instance, Question } form as utilized in "Computers and Intractability". For each problem discuss the best time and space complexity you are aware of for solving the problem along with a few words naming or describing the method. Then describe a certificate ("checkable" solution) having the best time and space complexity you can find for validating the certificate for each problem along with a few words naming or describing the method. In describing space you may assume the data is processed "on-line" and need not be stored unless necessary.

Part 1

 (i)     Sorting n integers.

(ii)     Finding the 15th  largest of n integers.

(iii)    Finding the 2 largest and 2 smallest of n integers.

 (iv)   Determining the number of ways to score 11 on 3 dice.

 (v)    Determining the greatest common divisor of (n,m).

Part 2

For the following just describe the certificate and the method and efficiency of checking the certificate. Problem numbers and pages refer to Gary and Johnson.

                                    (vi)    Traveling salesperson problem. (Decision question version).

(vii)   Clique of size J (see page 47 of Gary and Johnson).

(viii)  SP3 (p. 221)

(ix)        GT27 (p. 197)

(x)    Graph Isomorphism (discuss interactive probabilistic verification using the     zero knowledge proof technique).

  1. [Implementation Testing] (20 points)

You are to implement and test a program for summing 1/x as x runs over all approximately eight million (23 fraction bit mantissa) single precision floating point numbers in the interval [1,2). You are to do this on a server, PC(or Mac) of your choice. You are first asked to predetermine estimates of your implementation’s computation time and result accuracy.

a.       Discuss the computational environment for your tests, including the compiler, operating system, machine MHz and cycle times for appropriate instructions and whether pipelining affects your execution time.

b.      Predetermine an estimate of the time utilizing single precision for the variables for all computations from any documentation you can find.

c.       Predetermine an estimate of the accuracy by bounding the sum above and below. (Single precision computation should be done in round to nearest mode as provided by standard C implementations)

d.      Give the measured running time and the computed result for your implementation. Compare the results with your estimates of running times and accuracy.

5.      [Algorithm Complexity] (CSE5350 do only Part 1 for 20 points / CSE7350 do Parts 1 and 2 for 30 points)

Write an essay (4-5 word processor pages) discussing the issues involved in implementation independent measurement of the space and time complexity of algorithms. Include an analysis from your current perspective of the following fundamental issues:

Part 1 

a.       bit/basic element level space measurement

b.      polynomial/exponential growth in time or space measurement

c.       absolute/relative growth time measurement

d.      upper/lower asymptotic bounds

e.       worst/average case analysis

Part 2

f.     deterministic/probabilistic algorithm

g.    deterministic/nondeterministic algorithm

h.    solution vs. certificate

i.      verification by “zero knowledge proof” (interactive algorithm)

[Note: This exercise is designed to familiarize you with basic concerns in the analysis of algorithms and deep comprehension is not expected at this time. This same question later in the course should elicit a more comprehensive response.]