Scribd
Upload
4 views1 page

Tutorial 01

The document outlines the first tutorial for the Design and Analysis of Algorithms course, scheduled for January 6, 2026, lasting 40 minutes and worth 14 marks. It provides instructions for an open book, handwritten tutorial where students must solve one of three problems related to divide and conquer algorithms. The problems involve tiling a defective chessboard, using Karatsuba’s algorithm for integer multiplication, and designing an algorithm for multiplying an n-digit integer by a single digit.

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
4 views1 page

Tutorial 01

The document outlines the first tutorial for the Design and Analysis of Algorithms course, scheduled for January 6, 2026, lasting 40 minutes and worth 14 marks. It provides instructions for an open book, handwritten tutorial where students must solve one of three problems related to divide and conquer algorithms. The problems involve tiling a defective chessboard, using Karatsuba’s algorithm for integer multiplication, and designing an algorithm for multiplying an n-digit integer by a single digit.

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 1 January 6, 2026

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

Instructions:
1. This is an open book (take-home) tutorial. Only handwritten notebooks are al-
lowed.
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 weigh-
tage.

1. Tile the follwoing 8 × 8 defective chessboard using triominoes using the divide and
conquer algorithm, and draw the divide and conquer graph for the solution.

2. Find 2323×3232 using Karatsuba’s Divide and Conquer Integer Multiplication Algorithm
showing the computations in a divide and conquer graph.

3. Design a divide and conquer algorithm for multiplying an 𝑛-digit long integer to
a single digit. Derive its time complexity. Show the working of your algorithm for
computing 87654321 × 9 in a divide and conquer graph.

1 of 1

You might also like