Homework answers / question archive / COSC 3320 Assignment 1 1)Solve the Towers of Hanoi game for the following graph G=(V

COSC 3320 Assignment 1 1)Solve the Towers of Hanoi game for the following graph G=(V

Computer Science

Share With

---

COSC 3320 Assignment 1

1)Solve the Towers of Hanoi game for the following graph G=(V.E) with V={Start, Al,

A2. A3, A4, Dest} and E = {(Start,Dest), (Dest, Al), (A1,A2), (A2,A3), (A3,A4),

(A4,A1), ((Al,Dest)}.

 

(a) Design an algonthm and determine the time and space complexities of moving n disks

from Start to Dest.

 

(b) Implement this algorithm whereby your program prints out each of the moves of

every disk. Show the output for n=1, 2, 3, 4, 5, 6, 7, 8, 9, and 10. (If the output is too

long, print out only the first 100 and the last 100 moves.)

 

2. Determine for the following code how many pages are transferred between disk and

main memory (you must count reads and writes separately!), assuming each page has

1000 words, the active memory set size is 2000 (i. e., at any time no more’ than 2000

pages may be in main memory), and the replacement strategy is LRU (the Least Recently

Used page is always replaced); also assume that all two-dimensional arrays are of size

(1:4000, 1:4000), with each array element occupying one word, N=4000

fom -— 1 to 4000 do

 

for J :=1 to 4000 do

 

(GoA (ele Ji] =A ee cel eB ey Uli, Bleeds) - —C [N-I+1,J]*C[J,I] }

 

provided the arrays are mapped into the main memory space

(a) in row-major order, (b) in column-major order.

 

3. Consider QuickSort on the array A[1:n] and assume that the pivot element x (used to

split the array A[lo:hi] into two portions such that all elements in the left portion A[lo:m]

are <x and all elements in the right portion A[m:hi] are >x) is the penultimate element of

the array to be split (i. e., A[hi-1]).

 

Construct an infinite sequence of numbers for n and construct an assignment of the

numbers |...n to the n array elements that causes QuickSort, with the stated choice of

pivot, to

 

(a) execute optimally (that is A[lo:m] and A[m:hi] are always of equal size)

__ (b) execute in the slowest possible way.

 

Programming

 

Remember: For each of the next three programs, you are expected to write a report

that uses that program as a research tool. The fourth is a standard programming

exercise, with standard documentation required.