Scribd
Upload
5 views1 page

Tutorial 3

The document outlines instructions for a DAA course tutorial, emphasizing preparation and participation in problem-solving sessions. It includes specific recurrence relation problems to be solved using various methods such as Master method, recursion tree, and iterative method. Additionally, it discusses sorting algorithms and their efficiency in terms of swap operations and comparisons during merging sorted lists.

Uploaded by

40jee2023
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
5 views1 page

Tutorial 3

The document outlines instructions for a DAA course tutorial, emphasizing preparation and participation in problem-solving sessions. It includes specific recurrence relation problems to be solved using various methods such as Master method, recursion tree, and iterative method. Additionally, it discusses sorting algorithms and their efficiency in terms of swap operations and comparisons during merging sorted lists.

Uploaded by

40jee2023
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

Tutorial Sheet 3

Instructions
1.​ Tutorials in DAA course would majorly be doubt removal sessions.
2.​ Students are advised to come prepared in tutorial by revising the lectures of that particular week so that
doubts related to topics covered in that week are resolved.
3.​ Few practice questions will also be posted as Tutorial Sheet on your Google Classrooms. You can try
solving them before the scheduled tutorial and discuss the doubts.
4.​ As tutorials will be purely problem solving based, always join the tutorial with a notebook and pen
with you.
5.​ Whatever questions are discussed in tutorial, you are supposed to submit them on your respective
classrooms every week.

Recurrence Relations

1.​ Solve the following recurrences using Master method


a)​ T(n) = T(2n/3) + 1
b)​ T(n) = 3T(n/4) + n log n
c)​ T(n) = 4T(n/2) + n2

2.​ Solve the following recurrence Relation using Recursion tree method
a)​ T(n) = 4T(n/2)+n
b)​ T(n) =T(n/2)+T(n/4)+T(n/8)+n

3.​ Solve the following recurrences using Iterative method


a)​ T(n) = 8T(n/2) + n 2 , (T(1) = 1)
b)​ T(n) = n.T(n-1)​ if n>1
=1​ if n<=1
c)​ T(n) = T(n/2) +c if n>1
=1​ if n=1

4.​ Consider a situation where swap operation is very costly. Which of the following
sorting algorithms should be preferred so that the number of swap operations are
minimized in general?
a)​ Merge Sort b) Selection Sort c) Insertion Sort d) Heap Sort

5.​ Running merge sort on an array of size n which is already sorted is

a)​O(n) b) O(nlogn) c) O(n2) d) None

6.​ For merging two sorted lists of size m and n into sorted list of size m+n, we
require comparisons of

a)​O(m)​ b) O(n)​ c) O(m+n)​ d) O(logm + logn)

You might also like