# Uttarakhand technical university btech DAA notes unit-1

Here you can find utu( Uttarakhand technical university) previous year paper with solutions along with notes of utu btech first year,second year,third year,fourth year/final year from semester 1st(first),2nd(second),3rd(third),4th(fourth),5th(fifth),6th(sixth),7th(seventh),8th(eighth).
in future we will go for other courses like BBA,BCA,MCA,BSC(Agriculture)..etc

Todays UTU notes will be on DAA (Design and Analysis of Algorithm).

Subject Title:

#### Design and Analysis of Algorithm

Subject Code: TCS- 503

Total Number of Units: 5 Maximum Marks: 100

Unit I: Contains 7 Chapters:
Introduction
Growth of Functions
Master Theorem
Heap Sort
Quick Sort
Sorting in Linear Time
Order Statistics

Unit II: Contains 6 Chapters
Red Black Tree
Augmenting Data Structures
B-Trees
Binomial Heaps
Fibonacci Heaps
D.S. for Disjoint Sets

## Unit III: Contains 4 Chapters:

Dynamic Programming

Greedy Method

Amortized Analysis

Backtracking

## Unit IV: Contains 6 Chapters:

BFS & DFS

MST

Single-Source Shortest Paths

All-Pairs Shortest Paths

Maximum Flow

TSP

## Unit V: Contains 4 Chapters:

Randomized Algorithms

String Matching

NP-Completeness

Approximation Algorithms

Total: 27 Chapters

## TCS-503: Design and Analysis of Algorithms

Unit I: Syllabus

Introduction:

–

Algorithms

–

Analysis of Algorithms

–

Growth of Functions

–

Master’s Theorem

–

Designing of Algorithms

•

Sorting and Order Statistics

–

Heap Sort

–

Quick Sort

–

Sorting in Linear Time

•

Counting Sort

•

Bucket Sort

•

–

Medians and Order Statistics

## Algorithm

### Algorithm

Any well-defined < 31,41,59,26,12,58 >
computational procedure
that takes some value,

or

set of values

as input

EXAMPLE

31,41,59,26,12,58 > Output and <12,26,31,41,58,59>

produces some value,

or

set of values

as output.

Algorithm

Input

< 31,41,59,26,12,58 > < 31,41,59,26,12,58 >

Bubble Sort Algorithm

<31,41,26,12,58,59>

< 31,41,59,26,12,58 >

<31,26,12,41,58,59>

………

Output <12,26,31,41,58,59> <12,26,31,41,58,59>

Algorithm

Input Input <2,3>

Algorithm Sum(a,b)

c=a+b

Print c

Sum(2,3)

C=2+3

Print c

Output Output <5>

## Design of Algorithm Analysis of Algorithm

Design algorithms predict the cost of an algorithm
which in terms of
minimize the cost. resources
Cost: Resource:
Memory Space Occupied by Algorithm Memory
CPU Time
Running Time taken by Algorithm

DAA: Design and Analysis of Algorithm

Features of Algorithm

1.Finiteness                                             2. Definiteness

Terminates after a finite                          Rigorously and unambiguously specified

number of steps

3.Input

Zero or more valid inputs

are clearly specified

4. Output

At least one output can

be proved to produce the

correct output given a

valid input

5. Effectiveness

Steps are sufficiently

simple and basic

## Algorithm V/s Pseudo Code V/s Flowchart

An algorithm is a formal structure for solving a

problem that may be expressed in Pseudo Code or

Flowchart.

We say that write an algorithm in Pseudo Code to

implement Bubble Sort.

We say that write an algorithm using Flow Chart to

implement Bubble Sort.

Algorithm Types: Pseudo Code and Flowchart.

Pseudo Code: describes how you would implement an

algorithm without getting into syntactical

details of programming languages.

: Written in Natural Language.

: Preferred notation for describing

algorithms

Pseudo Code: Flow Chart:

1. Begin

2. Input A and B

3. Calculate A + B

4. Print result of SUM

5. End

start

Input A and B

Calculate A + B

Print Sum

End

Pseudo Code to implement

sum algorithm

Flow Chart to implement sum

algorithm

## Different Algorithm Design Techniques

1.Divide And Conquer

Reduce the problem to smaller problems (by a factor of at least 2), solves recursively and

then combine the solutions 🔜

2.Greedy Approach

1. “Take what you can get now” strategy.

2.Work in phases.

3.In each phase the currently best decision is made

3.Dynamic programming

Bottom-Up Technique which smallest instances explicitly in the sub-are solved first and the results of these used to construct solutions to progressively larger sub-
instances.

4.Backtracking

Generate-and-

Test methods:

Based on exhaustive search in

multiple choice

problems

## Different Algorithm Design Techniques

Divide And Conquer                 Greedy                      Dynamic                                Backtracking                                                               Approach                 programming

Examples:                          Examples:                    Examples:                                      Examples:

Merge sort                 Fractional Knapsack         Binary(0/1)Knapsack                        n-queens Problems

Problem                                           Sum of Subset

Quick sort                          Problem                    Assembly Line Scheduling

Binary Search             Activity Selection               Matrix Chain

Problems                       Multiplication

Finding Minimum

Spanning Tree

Shortest Path Problems

## Why to Analyze Algorithm?

Factors affecting the running time:

Computer Translator Algorithm used Input to the algorithm

Example: sorting ten million (107) numbers

Insertion sort:

Insertion sort:

Computer A: 109 instruc/s

World¡¦s craftiest programmer

Machine language

T(n)ƒ­2n2

7 2

5

9

2 (10 ) instruc 2 10 s 55.56h

Merge sort:

Computer B: 107 instruc/s

Average programmer

High-level language

2 T(n)ƒ­c nlgn

T(n)ƒ­50nlgn

7 7

7

50 10 lg10 instruc 19.38m

10 instruc/s

t „ª

ƒ­ „l

## How do we compare/analyze algorithms?

1. Compare execution times?

Not good: times are specific to a particular computer !!

2. Count the number of statements executed?

Not good:

number of statements vary with the programming

language as well as the style of the individual

programmer.

3. Express running time as a function of the input size n(i.e.,

f(n)).

Ideal Solution: Compare different functions corresponding

to running times.

Such an analysis is independent of machine

time, programming style, etc.

## How do we compare/analyze algorithms?

Growth of Functions

Asymptotic Notations

Design and Analysis of Algorithm

Subject Code: TCS- 503

Total Number of Units: 5 Maximum Marks: 100

Unit I: Contains 7 Chapters: Unit II: Contains 6 Chapters:

Introduction Red Black Tree

Growth of Functions Augmenting Data Structures

Master Theorem

B-Trees

Heap Sort

Binomial Heaps

Quick Sort

Fibonacci Heaps

Sorting in Linear Time

D.S. for Disjoint Sets

Order Statistics

## Different Algorithm Analysis Techniques

Best-Case Analysis

Minimum number of

steps for any possible

input.

Provides a lower

bound on running time

Not a useful measure.

Search for 12

1 23 45

One step

Worst-Case Analysis

Maximum number of

steps the algorithm

takes for any possible

input.

Provides an upper

bound on running time

Most tractable measure.

Search for 98

6 7 8 9 10 11

Search for 200

Average-Case Analysis

Average of the

running times of all

possible inputs.

Demands a definition

of probability of

each input, which is

usually difficult to

provide and to

analyze.

Assumes that the input

is random.

Provides a prediction

time.

12 15 21 23 27 45 76 77 90 95 98

## What is more important to analyze?

### Best case? Worst case? Average case?

The worst-case running time gives a guaranteed upper bound for

any input.

For many algorithms, the worst case occurs often.

e.g. When searching, the worst case often occurs when the

item being searched for is not present, and searches for

empty items may be frequent.

The average case is interesting and important because it gives a

closer estimation of the realistic running time.

However, its consideration usually requires more efforts

(algebraic transformations, etc.)

The worst case is the most interesting.

The average case is interesting, but often is as “bad” as the

worst case and may be estimated by the worst case.

The best case is the least interesting.

In the next post we will talk about random access machine model and further related topics from unit 1