[go: up one dir, main page]
Scribd
Upload
41 views2 pages

Assignment 1: 1 Coding

This document provides details for Assignment 1 which is due on October 12, 2020 at 5:30 PM IST. It includes two coding questions and five theory questions. The coding questions involve writing C++ programs to calculate the greatest common divisor (GCD) of two positive integers given certain arithmetic operations. The theory questions involve analyzing algorithm time complexities, proving programs always return the right answer, solving recurrence relations, categorizing functions by order, and determining the return value and running time of a nested loop function.

Uploaded by

Shashank Uttrani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
41 views2 pages

Assignment 1: 1 Coding

This document provides details for Assignment 1 which is due on October 12, 2020 at 5:30 PM IST. It includes two coding questions and five theory questions. The coding questions involve writing C++ programs to calculate the greatest common divisor (GCD) of two positive integers given certain arithmetic operations. The theory questions involve analyzing algorithm time complexities, proving programs always return the right answer, solving recurrence relations, categorizing functions by order, and determining the return value and running time of a nested loop function.

Uploaded by

Shashank Uttrani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Assignment 1

September 28, 2020

Deadline:-12/October/2020 5:30 PM IST

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 arith-
metic 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
2
• If I prove that an algorithm takes O(n ) 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 be
making. 5
• T (n2 ) = 7T (n2 /4) + cn2 and T (1) = 1
√ i
• T (n) = n ∗ T ( n) and T (2) = 4 (Assume n to be of the form 22 )
• 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) + c log n
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
n1.2
• log n
2
• n
• n log n
• 1.1n
• 0.9n
• log3 n
5. What value is returned by the following function? Express your answer as
a 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)

You might also like