## CS 660: Combinatorial Algorithms Leda Assignment

[To Lecture Notes Index]
San Diego State University -- This page last updated October 3, 1995

CS 660 Programming Assignment - Trees and Dynamic Lists
Problems 1 & 2 Due Oct. 12
Problems 3 & 4 Due Oct. 17

1) Write a program to time the following loop:

```float why;
int k, N;
start time
for (k = 0; k < N; k++)
why = sin(k);
end time
```
We would like to get an answer within 5% of the actual running time of the loop. How many times must you time the loop with the same value of N to be within 5% of the actual value with 95% confidence? What happens when you vary N?

2) Compare the time it takes to build a binary search tree with N items in random order with the time it takes to build a-b tree (AVL tree, BB[alpha], binary search tree, hash table, persistent tree, red-black tree, random search tree, skip list) with N items in random order. You to investigate the performance of two structures. One is the binary search tree, the other is given by the table below. Compare the average access time for the two structures.

3) Write a program to produce a list containing the integers 1 through N randomly distributed with Zipfian (Lotka's , 80% - 20% ) probability distribution. Recall that the Zipfian probability distribution is given by for k = 1, 2, ..., n, where . Lotka's distribution is given by . 80% - 20% distribution is given by .

4) a) Write a program to perform move-to-front (transpose) algorithm on an array (linked-list) of the integers 1 - N. Use the list(s) generated in 3) for the input. Time how long the algorithm takes to find all items in the list. See table below.

b) Write a program to produce the optimal static ordering on an array (linked-list) of the integers 1 - N. Use the list(s) generated in 3) for the input. Time how long it takes to search for the integers once you have the optimal static order.

c) Time the algorithms developed in 4a & b on different files of the same size. How do the results of the same algorithm vary between different files of the same size and distribution. How do the different algorithms compare on the same file?