CSE 7350/5350

D.W. Matula

Homework Set # 1

Due date:

5 Feb. '04

 


Total Points:
CSE5350 - 85
CSE7350 - 105

 

 

 

Measuring Algorithm Efficiency

 

 

 

 

Reading: Chapters 1 and 2; preface and pp 1-33 of Computers and Intractability

 

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.)

 

Website updated Jan 22, 2004.

 

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.      [Decision Trees and Lower Bounds] (20 points)

a. Use a decision tree and provide an argument that the minimum number of comparisons necessary to determine the median of an n = 2k+1 membered set is at least:

Ceiling of log2 [product of (2k +1 choose k) and (k + 1)]

 

Evaluate this bound for n = 3, 5, 7, 9, 11 and provide a sharp asymptotic formula for this bound as

n ® ¥.

b. Construct a decision tree that finds the median of 5 elements in at most 6 comparisons

c. Construct a decision tree for inserting 5 numbers into a heap that employs the smallest number of comparisons:

(i)        in the worst case,

(ii)    in the average case. 
 

4. [Solution vs. Validation] (CSE5350 do (i)-(iii) for 10 points / CSE7350 do (i)-(vii) for 20 points)

Express the following five loosely described problems in careful { 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 give the best time and space complexity you can for finding a certificate ("checkable" solution), and finally the best time and space for validating the certificate for each problem along with a few words naming or describing the method. In descibing space you may assume the data is processed "on-line" and need not be stored unless necessary.

(i)      Max of n integers.

(ii)     Sorting n integers.

(iii)    Finding the 15 largest of n integers.

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

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

(vi)    Finding a maximal complete subgraph.

(vii)   Finding the two closest of n points in the unit square.

 

  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 (Unix machine) of your choice and a PC(or Mac) of your choice and discuss and compare results.

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

b.Estimate the time for each machine utilizing single precision for the variables for all computations.

c. Estimate the accuracy by bounding the sum above and below. (Single precision computation should be done in round to nearest mode as provide by standard C implementations)

d.Give the measured running time and the computed result for both the workstation and PC implementations. Compare the results between the two machines and with your estimates of running times and accuracy.

6.   [Algorithm Complexity] (CSE5350 do a-e only for 15 points / CSE7350 do a-g for 25 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:

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

f.  solution vs. certificate

g. deterministic/probabilistic algorithm

h. deterministic/nondeterministic 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.]