Scribd
Upload
8 views2 pages

Algorithm Design and Analysis Tutorial 2025

The document is a tutorial on the design and analysis of algorithms, covering various topics such as logarithmic functions, algorithmic proofs, divide and conquer strategies, and search algorithms. It includes problems and exercises related to logarithmic complexities, chessboard tiling, binary and ternary search algorithms, and disjoint set checks. Additionally, it discusses the Karatsuba algorithm for integer multiplication and provides examples for practical application.

Uploaded by

harshsinghrajput061
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
8 views2 pages

Algorithm Design and Analysis Tutorial 2025

The document is a tutorial on the design and analysis of algorithms, covering various topics such as logarithmic functions, algorithmic proofs, divide and conquer strategies, and search algorithms. It includes problems and exercises related to logarithmic complexities, chessboard tiling, binary and ternary search algorithms, and disjoint set checks. Additionally, it discusses the Karatsuba algorithm for integer multiplication and provides examples for practical application.

Uploaded by

harshsinghrajput061
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 1, Design and Analysis of Algorithms, 2025

1. For a real number the function log( ) is de ned as follows: log( ) is the
n n n

smallest natural number so that after applying logarithm function


i
  (base 2) i

times on  we get a number


n
 2
less than or equal to 1. E.g.
 2
log 2 is 2 because
 2

log(log 2 ) = 1  1. log 2 is 3 because loglog(log 2 ) = 1  1.


2 2 2

Either prove or disprove:


(a) log(log( )) = (log(log( ))).
n O n

(b) log(log( )) = (log(log( ))).


n O n

2. Assume you have functions and such that ( ) is ( ( )). For each of the
f g f n O g n

following statements, decide whether you think it is true or false and give a proof
or counterexample:
(a) log ( ) is (log ( )).
2f n O 2g n

(b) 2f n is (2g n ).
( )
O
( )

(c) ( ) is ( ( ) ).
f n
2
O g n
2

3. Prove that
( 1)+( ) = ( )
n n n :

Does it follow that


( ) = ( ) ( 1)?
n n n

Justify your answer.


4. 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.

1
5. In an in nite array, the rst cells contain integers in sorted order and the rest
n

of the cells are lled with 1. Present an algorithm that takes as input and
x

nds the position of in the array in (log ) time. You are not given the value
x O n

of .n

6. Device a \binary" search algorithm that splits the set not into two sets of (almost)
equal sizes but into two sets, one of which is twice the size of the other. How does
this algorithm compare with binary search?
7. Device a ternary search algorithm that rst tests the element at position 3 forn

equality with some value , and then checks the element at 23 and either discovers
x
n

x or reduces the set size to one-third the size of the original. Compare this with
binary search.
8. The sets and have elements each given in the form of sorted arrays. Design
A B n

( ) algorithms to compute [ and \ .


O n A B A B

9. Two sets and have elements each. Assume that each element is an integer
A B n

in the range [0 ]. These sets are not necessarily sorted. Design an agorithm
;n
100

to check whether these two sets are disjoint in ( ) space and time.
O n

10. Find 12122121 using Karatsuba's Divide and Conquer Integer Multiplication
Algorithm showing the computations in a divide and conquer graph.

You might also like