Scribd
Upload
3 views1 page

Tutorial 04

DAA Tutorial 4 is an open book, take-home tutorial focused on the Design and Analysis of Algorithms, scheduled for January 30, 2026, with a duration of 40 minutes and a maximum score of 14 marks. Students must solve one of three provided problems using Dynamic Programming or prove a mathematical statement regarding binary trees. Calculators are permitted, and all steps and derivations must be shown in handwritten notebooks.

Uploaded by

mehulsrivastava1204
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
3 views1 page

Tutorial 04

DAA Tutorial 4 is an open book, take-home tutorial focused on the Design and Analysis of Algorithms, scheduled for January 30, 2026, with a duration of 40 minutes and a maximum score of 14 marks. Students must solve one of three provided problems using Dynamic Programming or prove a mathematical statement regarding binary trees. Calculators are permitted, and all steps and derivations must be shown in handwritten notebooks.

Uploaded by

mehulsrivastava1204
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

CS F364 DAA Tutorial 4 January 30, 2026

DAA Tutorial 4
Design and Analysis of Algorithms
Date: January 30, 2026 Time: 40 Minutes Max Marks: 14 Marks

Instructions:

1. This is an open book (take-home) tutorial. Only handwritten notebooks are allowed.

2. Calculators are allowed.

3. Show all steps of your solution and give full derivation of your results using efficient
algorithms.

4. Solve any one out of the following three problems. Each problem has equal
weightage.

1. Using the Dynamic Programming algorithm, find all possible shortest salesman tours
and cost for the following instance of the Traveling Salseman Problem for a directed
𝐾 4 graph having the following adjacency matrix:
0 6 2 9

7 0 5 2

4 .
 3 0 1
9 3 8 0

2. Using the Dynamic Programming algorithm, solve the following instance of the
Matrix Chain Multiplication Problem:
< 𝐴4×3 , 𝐵3×5 , 𝐶5×6 , 𝐷6×3 , 𝐸3×2 , 𝐹2×7 >.

3. Prove that the number of different binary trees with 𝑛 nodes is


 
1 2𝑛
.
𝑛+1 𝑛

1 of 1

You might also like