Fill This Form To Receive Instant Help
Fill This Form To Receive Instant Help
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.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.
