ID2230_DSA-Assignment 1 Solved

1           Coding
For the coding assignment you just need to know how to take input and print output in C++ and the use of various types of loops (like if, for, while). Rest is based on mathematics and logic.

1.    An old computer is capable of only performing few arithmetic operations.This computer is able to process all types of loops and comparisons. It can also take input and give output.

             All the following operations take 1 unit cycle.                                                    6

•   Compare two integers.

•   Add two integers.

•   Subtract one integer from another.

•   Multiply/Divide a number by two.

Using these and only these arithmetic operations, write a C++ code which takes two positive integers as input and returns the GCD of two positive integers. Please ensure that your code also shows the intermediate steps.

2.    Let xy denote the last two digits of your roll number. We assume a new coding language which works on the same computer mentioned in previous question. Let F denote the set of all distinct prime factors of xy.

A crazy scientist has created a language which allows the following arithmetic operations             2

•   Compare two integers.

•   Add two integers.

•   Subtract one integer from another.

•   Multiply/Divide a number by f(∀f ∈ F).

Using these and only these arithmetic operations (in addition to other operations allowed by the computer), write a C++ code which takes two positive integers as input and returns the GCD of two positive integers.

1

2           Theory
1.    For each of these questions, briefly explain your answer.           3

•   If I prove that an algorithm takes O(n2) worst-case time, is it possible that it takes O(n) on some inputs?

•   If I prove that an algorithm takes O(n2) worst-case time, is it possible that it takes O(n) on all inputs?

•   If I prove that an algorithm takes Θ(n2) worst-case time, is it possible that it takes O(n) on some inputs?

2.    Prove that your code for Quesn # 1.1 always finds the right answer.       2

3.    Solve the following recursions. Mention any assumptions you might bemaking. 5

•   T(n2) = 7T(n2/4) + cn2 and T(1) = 1

                                                √                                                                                                                                       2i)

•   T(n) = n ∗ T( n) and T(2) = 4 (Assume n to be of the form 2

•   T(n) = T(n/2) + 2T(n/4) + 3n/2 (whenever n > 3) and T(1) =

0,T(2) = 2

•   T(n) = 4T(n/2) + n3 and T(1) = 1

•   T(n) = T(n/2) + clogn

4.    If function f = o(g), then we shall say that f is less than g. Give the partial order/total order which categorizes the following functions. Justify your claims.          3

•  

•   n2

•   nlogn

•   1.1n

•   0.9n

•   log3 n

5.    What value is returned by the following function? Express your answer asa function of n. Give the worst-case running time using Oh notation. 3

function XYZ(n) r := 0

for i := 1 to n do

for j := 1 to i do

for k := j to i + j do

for l := 1 to i + j − k do

r := r + 1; return(r)

2