need help with this Algorithm and Data Structure assignment(using java for programing part). Thanks!

(p.s this time with correct attachment)

CSC 225 SPRING 2017
ALGORITHMS AND DATA STRUCTURES I
ASSIGNMENT 2
UNIVERSITY OF VICTORIA 1. Consider an implementation of a stack using an extendible array. That is, instead of giving
up with a “StackFullException” when the stack becomes full, we replace the current array
S of size N with a larger one of size f (N ) and continue processing the push operations.
Suppose that we are given two possible choices to increase the size of the array: (1)
f (N ) = N + c (for convenience, we start with an initial array of size 0) (2) f (N ) = 2N
(we start with an initial array of size 1). Compare the two strategies and decide which
one is better.
To analyse the two choices, assume the following cost model: A “regular” push operation
costs one unit of time. A “special” push operation, when the current stack is full, costs
f (N ) + N + 1 units of time. That is, we assume a cost of f (N ) units to create the new
array, N units of time to copy the N elements and one unit of time to copy the new
element.
2. Suppose that we are given an array A with n keys and k inversions. Here, an inversion is
defined as a pair of entries that are out of order in the array. What is the running time of
Insertion sort when it is used to sort A in Big Oh notation? Why?
3. Develop a O(n log n) algorithm for computing the number of inversions in a given array.
4. Solve the following recurrence equation to get a closed-formula for T (n). Assume the n is
a power of two. T (n) = 1 if n = 1
 
n
= 4T
+ n log n if n ≥ 2
2
5. Suppose we are given a sequence S of n elements, each of which is an integer in the range
[0; n2 − 1]. Describe a simple method for sorting S in O(n) time. 1

• 1493693683-assignment2-Spring17.pdf

ComputerScienceExpert

(11)

Status NEW Posted 02 May 2017 02:05 AM My Price 11.00

-----------

Attachments

file 1493693686-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer