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:

- 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. - Codes written in C++, VC, VB, C or JAVA are acceptable.
- 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 h_{2}(k) steps)

A.
Construct
a new method of probing where each probe sequence has a different sequence of
jumps, as a function of h_{1}(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 = 2^{31}-1, which is prime, and create
a hash table of successive values of _{} (mod m) of size 2^{10},
2^{11}, 2^{12}, 2^{13}, 2^{14}, 2^{15},
2^{16}, 2^{17}. 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 2^{31}-2
= (2)(3^{2})(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 2^{31}-1, you must save all the bits in the product of a and b, and then reduce the
product modulo 2^{31}-1

·
modexp(g,i) which takes g, a reduced residue modulo
m-1, and an exponent, i, and
returns g^{i} (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:

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 = a_{0} + a_{1}2^{16},
and b = b_{0} + b_{1}2^{16}. We do this so that we may retain the full
64-bit product of a and b, which is:

ab = (a_{0}b_{0})
+ (a_{0}b_{1}+a_{1}b_{0})2^{16 }+ (a_{1}b_{1})2^{32}

Note that each of the individual products is computable as
simple 32-bit integer multiplications as a_{0},
a_{1}, b_{0}, and_{ }b_{1} 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 2^{31}-1) = (ab)_{0} + (ab)_{1 }(mod 2^{31}-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:

- 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. - Codes written in C++, VC, VB, C or JAVA are acceptable.
- 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]
= max( _{ }v_{i} +c[i-1,w-w_{i}], c[i-1,w]) if i > 0 and w _{} w_{i}*

* *

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 *w _{i}=*INT(1000

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 2^{32}.
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(n^{2})
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 i^{th} Fibonacci number, F_{i}, defined
by:

F_{0} = 0,

F_{1 }= 1,

F_{i} = F_{i-1}
+ F_{i-2}, i > 1.

Write code for computing F_{i
}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.