SDSU 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;
read 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?

Al-Shetweya-b treeZipfianmove-to-frontarray
BarducciAVL treeLotka's move-to-frontarray
ChenBB[alpha]80% - 20% move-to-frontarray
Chenbinary search treeZipfiantransposearray
CianfloneHash tableLotka's transposearray
De Jacopersistent tree80% - 20% transposearray
Dundonred-black treeZipfianmove-to-frontlinked-list
Floydrandom search treeLotka's move-to-frontlinked-list
Gaoskip lists80% - 20% move-to-frontlinked-list
Graba-b treeZipfiantransposelinked-list
HironakaAVL treeLotka's transposelinked-list
HussBB[alpha]80% - 20% transposelinked-list
Leebinary search treeZipfianmove-to-frontarray
LeungHash tableLotka's move-to-frontarray
Lupersistent tree80% - 20% move-to-frontarray
Lyred-black treeZipfiantransposearray
Marcusrandom search treeLotka's transposearray
Orourkeskip lists80% - 20% transposearray
Pekera-b treeZipfianmove-to-frontlinked-list
PhamAVL treeLotka's move-to-frontlinked-list
PhillipsBB[alpha]80% - 20% move-to-frontlinked-list
Saundersbinary search treeZipfiantransposelinked-list
SchmitHash tableLotka's transposelinked-list
Scullypersistent tree80% - 20% transposelinked-list
Singerred-black treeZipfianmove-to-frontarray
Spydellrandom search treeLotka's move-to-frontarray
Sunskip lists80% - 20% move-to-frontarray
Warlopa-b treeZipfiantransposearray
WarringtonAVL treeLotka's transposearray
WilliamsBB[alpha]80% - 20% transposearray
Wongbinary search treeZipfianmove-to-frontlinked-list
WorraHash tableLotka's move-to-frontlinked-list
Xiaopersistent tree80% - 20% move-to-frontlinked-list
Yured-black treeZipfiantransposelinked-list
Yurandom search treeLotka's transposelinked-list
Zhangskip lists80% - 20% transposelinked-list