Project #72993 - INFR 2820U: Algorithms & Data Structures

 

INFR 2820U: Algorithms & Data Structures

Assignment 1

 

 

Exercise V ( 60 points) For each of the following five program fragments:

a.       Computing the theoretical time complexity: Count the number of multiplication as basic operation, and state the Big-Oh for each complexity. Prove only how did you get the big-Oh only for part 1.

b.      Computing the actual running times: Implement the code in the language of your choice, and find the running time for several values of n. Plot results in a graph.

c.       Compare the theoretical time complexity with the actual running times. Do you see any relationship between the two?

1.

NegativeSumSquare = 0;

for (i = 1; i <= n; i++)

Sum = Sum – i*i;

 

2.

Negative3SumSquare = 0;

for (i = 1; i <= 3*n; i++)

Negative3Sum = Negative3Sum – i*i;

 

3.

NegativeSubSumSquare = 0;

for (i = 1; i <= n; i++)

for (j = 1; j <= i; j++)

NegativeSubSum = NegativeSubSum – j*j;

 

Exercise VI: (20 points) Put the following recurrence relations into closed forms:

a.       T(n) = T(n-1) +3

T(1) = 9

b.      T(n) =  T(n-1) + n

T(1) = 3

 

Exercise VII: (20 points) Use the Master Method to find the approximate solution for the following recurrence relations. Be sure to identify the values of a, b, and d in your answer.

a.       T(n) = 2 * T(n/2) + n -3

b.      T(n) = 4 * T(n/7) + n2 + 4

c.       T(n) = 3 * T(n/5) + n3 –n+ 2

 

 

 

Project does not have any attached files

Subject Computer
Due By (Pacific Time) 06/05/2015 04:00 am
Report DMCA
TutorRating
pallavi

Chat Now!

out of 1971 reviews
More..
amosmm

Chat Now!

out of 766 reviews
More..
PhyzKyd

Chat Now!

out of 1164 reviews
More..
rajdeep77

Chat Now!

out of 721 reviews
More..
sctys

Chat Now!

out of 1600 reviews
More..
sharadgreen

Chat Now!

out of 770 reviews
More..
topnotcher

Chat Now!

out of 766 reviews
More..
XXXIAO

Chat Now!

out of 680 reviews
More..
All Rights Reserved. Copyright by AceMyHW.com - Copyright Policy