COP 4531: Analysis and Complexity of Algorithms and Data Structures

Programming Homework Assignments

(Total of 130 Points)

1. (30 points) For the following sorting algorithms: insertion sort, merge sort, heap sort, quicksort, counting sort, radix sort, and bucket sort:

A.   Implement each algorithm

B.    Using either U[0,k) integers or U[0,1) reals as your inputs to the above sorting algorithms, compute the running time of your implementations for 10 different samples of  length N=10, 50, 100, 500, 1000, 5000, 10,000, 50,000, 100,000, 500,000, and 1,000,000.  Plot your results.

Intsruction to submit programming assignment #1 and #2:
1. Two attchment files to cop4531@cs.fsu.edu with subject your name. One file is your source codes, and the other file is your plots. Please write your name in the beginning of each file.
2. Codes written in C++, VC, VB, C or JAVA are acceptable.
3. Instruction how to run the code with attachment or in your email.

2. (40 points) Consider the various probe sequences we studied for collision resolution when hashing with open addressing:

·        Linear (every probe sequence is a fixed jump of one step)

·        Quadratic (every probe sequence is the same sequence of jumps)

·        Double hashing (each probe sequence is a fixed jump of h2(k) steps)

A.   Construct a new method of probing where each probe sequence has a different sequence of jumps, as a function of h1(k), but still searches the entire hash table.

B.    Implement all four of the above probing schemes and plot the number of probes required to insert a key in the hash table for a hash table of size 1,000,000 as a function of the load factor, , for values of the load factor from 0.5 to 1.0.  Note; count an insert that had no collision as a 1.  In addition, plot the function , as a reference for the best case behavior as this is the expected number of probes required to insert an element in a has table with load factor under the simple uniform hashing assumption.

C.   Consider the problem of finding the discrete logarithm of a given number, modulo a prime, m.  Recall that the discrete logarithm is defined with the help of g, a primitive root modulo m, as: is the discrete logarithm of x modulo m with respect to the primitive root, g if (mod m) x.

Let m = 231-1, which is prime, and create a hash table of successive values of (mod m) of size 210, 211, 212, 213, 214, 215, 216, 217.  Pick x randomly, and use your hash table to find .  Plot the average length of searches for each value of the hash table size averaging over 1000 random x values.  Use this information to estimate what the optimal hash table size is for this problem.

Note, use g = 7 in this problem, and note that 231-2 = (2)(32)(7)(11)(31)(151) (331).

In part C you will need to define the following functions:

·        mult(a,b) which takes numbers a,b, reduced residues modulo m, and returns ab (mod m), note: you must realize that to properly compute a product modulo 231-1, you must save all the bits in the product of a and b, and then reduce the product modulo 231-1

·        modexp(g,i) which takes g, a reduced residue modulo m-1, and an exponent, i, and  returns gi (mod m), this routine will use the square-and-multiply method and will need mult(a,b), see below for code

·        modadd(a,b) which takes numbers a,b, reduced residues modulo m, and returns a+b (mod m-1)

·        hash(key,j) inserts key with index j into an open-address hash table

·        intable(key) returns the index of key if it is in the hash table, otherwise it returns 0

·        gcd(a,b) returns the greatest common divisor of a and b (see below for pseudocode

Here is an outline of the main code you will need to write and the modexp(g,i) routine.  Here x and g are defined as above:

key = 1

for i = 1 to n ! hash table is size n

key = modmult(key,g)

hash(key,i)

jump = m-1

while(gcd(jump,m-1) <> 1)

jump = rand(m-1)

j = modexp(g,jump)

x_temp = x

count = 0

while( not intable(x_temp))

count = count + 1

x_temp = modmult(x_temp,j)

index = intable(x_temp)

index = modadd(index,-count*jump) !solves for the index

plot(n,count)

modexp(g,i) !modular exponentiation of g to power i

gtemp = g

n = howlong(i) !the number of bits in i

for j = n-1 downto 1

gtemp = modmult(gtemp,gtemp)

if (extract(i,j)) !get’s out the jth bit of i

gtemp = modmult(gtemp,g)

return gtemp

gcd(a,b) !returns the gcd of a and b, positive

if (a < b) !make sure a > b by swapping

a_temp = a

a = b

b = a_temp

while(b > 0)

a_temp = a

a = b

b = a_temp % b !regular mod function

return a

Here are some extra hints about how to implement modmult(a,b).  First of all you must store a and b in (unsigned) integer arrays of dimension two.   Each element of the array will hold only 16 bits of the original integer.  Thus we can think of a = a0 + a1216, and b = b0 + b1216.  We do this so that we may retain the full 64-bit product of a and b, which is:

ab = (a0b0) + (a0b1+a1b0)216 + (a1b1)232

Note that each of the individual products is computable as simple 32-bit integer multiplications as a0, a1, b0, and b1 have only 16 bits in them!!  Once this is computed, one must extract the least-significant 31 bits from the product and the next most significant 31 bits.  This requires bit shifting, and masking.  Call these (ab)0 and (ab)1 respectively.  Then we have finally:

a b (mod 231-1) = (ab)0 + (ab)1 (mod 231-1)

This latter sum can be computed with 32-bit integer addition with a secondary check and subtraction (if necessary) for the modular reduction.

Intsruction to submit programming assignment #3:
1. Two attchment file to cop4531@cs.fsu.edu with subject your name. One file is your source codes, and the other file is your output with W=335732, n=100. Please write your name in the beginning of each file.
Sample for output
#ID          Weight
2           34
13          23
45       87
:         :
:         :
----------------------------
Total 3         144
#ID is the chosen item number.
2. Codes written in C++, VC, VB, C or JAVA are acceptable.
3. Instruction how to run the code with attachment or in your email.

3.  (30 points)  Implement a dynamic program to solve the 0-1 knapsack problem in O(nW) time, where n is the number of items and W is the maximum weight of items that fit in the knapsack.  Note, you should write a general program to solve this problem, which is problem 16.2-2 in the text.

Hint:  Define c[i,w] to be the value of the solution to the knapsack problem for items 1 through i,  and maximum weight of items that fit in the knapsack of w.  This function is defined as:

c[i,w] = 0                                                             if i=0 or w=0

c[i,w] = c[i-1,w]if wi > w

c[i,w] = max( vi +c[i-1,w-wi], c[i-1,w])                 if i > 0 and w wi

Thus, solve the problem by computing the table of c[i,j] values for i=0 to n and j=0 to W.

When you have implemented this program, solve the following 0-1 knapsack problem:

Let W=335732, n=100, with the weights as wi=INT(1000 i1/2), and the values are all the same, vi=v=1, i= 1,2, …, 100.  Here INT(x) is the integer part of x rounded to the nearest integer.  This is different than either the floor or ceiling function!

4. (30 points of extra credit) Consider the probabilistic primality testing algorithm, MILLER-RABIN(n,s) as defined in section 33.8 of the text.  Implement this for algorithm for integers up to 232.  To do so you will need to:

A.     Implement a multiprecise arithmetic package for 32-bit integers that does what is required for modular reduction, i.e. both multiplication and division.  You should use “schoolbook” multiplication, and bit-by-by division.

B.      Test out your code on random integers of length 32-bits, and print out your results.

5. (20 points of extra credit) For the following sorting algorithms: Bubble Sort, bi-directional Bubble Sort and Bitonic Sort

A.   Implement each algorithm (include source code with your assignment)

B. Using either U[0,k) integers or U[0,1) reals as your inputs to the above sorting algorithms, compute the  running time of your implementations for 10 different samples of length N=10, 50, 100, 500, 1000, 5000, 10,000, 50,000, 100,000, 500,000, and 1,000,000.  Plot your results.  Note: bitonic sort works only with power-of-two items to be sorted, so for that use N=16, 32, 64,128, 256, 512,1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072.

Bubble Sort

Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done.

Since at least one item is moved into its final place for each pass, an improvement is to decrement the last position checked on each pass.

The Bubble Sort Algorithm:

for  i <- length[A] to 0

for j <- 0 to i

if a[j] > a[j+1]

then exchange A[j] < -- > A[j+1]

Bi-Directional Bubble Sort

A variant of bubble sort which compares each adjacent pairs of items in a list in turn, swapping them if necessary, and alternately passes through the list from the beginning to the end then from the end to the beginning until no swaps are done.

Complexity is O(n2) for arbitrary data, but approaches O(n) if the list is nearly in order at the beginning. Bi-directional bubble sort usually does better than bubble sort since at least one item is moved forward or backward to its place in the list with each pass. Bubble sort moves items forward into place, but can only move items backward one location each pass.

The Bi-Directional Bubble Sort Algorithm:

limit <- length[A];

st = -1;

while (st < limit)

flippedflag = false;

st++;

limit--;

for j _ st to limit

if  a[j] > a[j + 1]

then exchange A[j] < -- > A[j+1]

flippedflag = true;

if (!flipped)

return;

for (j = limit; --j >= st;)

if  a[j] > a[j + 1]

then exchange A[j] < -- > A[j+1]

flippedflag = true;

if (!flipped)

return;

Bitonic sort:

A sorted sequence is a monotonically non-decreasing (or non-increasing) sequence. A bitonic sequence is composed of two subsequences, one monotonically non-decreasing and the other monotonically non-increasing. A "V" and an A-frame are examples of bitonic sequences.

Moreover, any rotation of a bitonic sequence is a bitonic sequence, or if you prefer, one of the subsequences can wrap around the end of the bitonic sequence.

Of course, a sorted sequence is itself a bitonic sequence: one of the subsequences is empty.

Now we come to a strange property of bitonic sequences, the property that is uses in bitonic sort:

Suppose you have a bitonic sequence of length 2n, that is, elements in positions [0,2n). You can easily divide it into two halves, [0,n) and [n,2n), such that each half is a bitonic sequence, and every element in half [0,n) is less than or equal to each element in [n,2n). (Or greater than or equal to, of course.)

Simply compare elements in the corresponding positions in the two halves and exchange them if they are out of order.

for (i=0;i<n;i++) {

if (get(i)>get(i+n)) exchange(i,i+n);

}

This is sometimes called a bitonic merge.

So here's how we do a bitonic sort:

We sort only sequences a power of two in length, so we can always divide a subsequence of more than one element into two halves. We sort the lower half into ascending (=non-decreasing, remember) order and the upper half into descending order. This gives us a bitonic sequence.

We perform a bitonic merge on the sequence, which gives us a bitonic sequence in each half and all the larger elements in the upper half. We recursively bitonically merge each half until all the elements are sorted.

The Bitonic Sort Algorithm

This first version actually uses recursion. It uses methods sortup, sortdown, mergeup, and mergedown, to sort into ascending order or descending order and to recursively merge into ascending or descending order. Method void sortup(int m, int n) will sort the n elements in the range [m,m+n) into ascending order. It uses method void mergeup(int m, int n) to merge the n elements in the subsequence [m,m+n) into ascending order. Similarly for void sortdown(int m, int n) and void mergedown(int m, int n).

The overall sort is performed by a call:

sortup(0,N);

Both sortup and sortdown recursively sort each half to produce an A-frame

shape and then recursively merge that into an ascending or descending

sequence.

void sortup(int m, int n) {//from m to m+n

if (n==1) return;

sortup(m,n/2);

sortdown(m+n/2,n/2);

mergeup(m,n/2);

}

void sortdown(int m, int n) {//from m to m+n

if (n==1) return;

sortup(m,n/2);

sortdown(m+n/2,n/2);

mergedown(m,n/2);

}

Methods mergeup and mergedown are fairly straightforward. They compare

elements in the two halves, exchange them if they are out of order, and

recursively merge the two halves. Call mergeup( m,  n) sorts into

ascending order the 2*n elements in the range [m,2n).

void mergeup(int m, int n) {

if (n==0) return;

int i;

for (i=0;i<n;i++) {

if (get(m+i)>get(m+i+n)) exchange(m+i,m+i+n);

}

mergeup(m,n/2);

mergeup(m+n,n/2);

}

void mergedown(int m, int n) {

if (n==0) return;

int i;

for (i=0;i<n;i++) {

if (get(m+i)<get(m+i+n)) exchange(m+i,m+i+n);

}

mergedown(m,n/2);

mergedown(m+n,n/2);

6. (20 points of extra credit) Consider computing the ith Fibonacci number, Fi, defined by:

F0 = 0,

F1 = 1,

Fi = Fi-1 + Fi-2, i > 1.

Write code for computing Fi using:

A.   Recursion

B.    Iteration

C.   Formula (3.23) in the book(page 56)

D.   A memoized dynamic program

Plot the running time of each of these codes as a function of i, for values from 100 to 100000 increments of 100.  Also include your codes.