Scribd
Upload
60 views

DAA Assignment - 4

This document contains a tutorial sheet for the subject Design and Analysis of Algorithms. It has three sections with multiple choice and long answer questions worth a total of 64 marks. Section A contains 5 short answer questions worth 10 marks. Section B contains 3 questions worth 7 marks each on randomized algorithms, Las Vegas algorithms, and Monte Carlo algorithms. Section C contains 3 longer answer questions worth 11 marks each on minimum set cover, vertex cover, and the Chinese Remainder Theorem. The tutorial covers topics related to computational geometry, randomized algorithms, and lower bound theory.

Uploaded by

megha.garg1
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
60 views

DAA Assignment - 4

This document contains a tutorial sheet for the subject Design and Analysis of Algorithms. It has three sections with multiple choice and long answer questions worth a total of 64 marks. Section A contains 5 short answer questions worth 10 marks. Section B contains 3 questions worth 7 marks each on randomized algorithms, Las Vegas algorithms, and Monte Carlo algorithms. Section C contains 3 longer answer questions worth 11 marks each on minimum set cover, vertex cover, and the Chinese Remainder Theorem. The tutorial covers topics related to computational geometry, randomized algorithms, and lower bound theory.

Uploaded by

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

B.Tech.

(Computer Science and Engineering)


Semester-V
Subject: Design and Analysis of Algorithms
Subject code BCO023A
Marks: 64

CO3: Computational geometry, like Lower bound theory, modular arithmetic and CRT.

UNIT #4 Tutorial sheet 1


Sec-A (5x2=10marks)

1. [CO4]- What is a "Randomized algorithms? [2 marks]


2. [CO4]- Find out GCD of 96 and 36. [2 marks]
3. [CO4]- Define approximate algorithm. [2 marks]
4. [CO4]- Write Quotient Remainder Theorem. [2 marks]
5. [CO4]- Define Modular Multiplication:. [2 marks]

Sec-B
/* Note: Each question may have one or two parts */ (3x7=21 marks)

6. [CO4]-Explain Las Vegas algorithm with example. [7 marks]

7. [CO4]- Explain Monte Carlo algorithm with example. [7 marks]

8. [CO4]- Define Lower bound theory in details. [7 marks]

Sec-C
/* Note: Each question may have one, two, or three parts */ [3*11=33 marks]

9. [CO4] Find Minimum set cover [11 marks]


10. [CO4] - Find Vertex cover from below diagram. [11 marks]

11. [CO4]- State chinese remainder theorem. Solve the following congruence. [11 marks]
x ≡ 6 (mod 11)
x ≡ 13 (mod 16)
x ≡ 9 (mod 21)
x ≡ 19 (mod 25)
.

You might also like