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 

• 

Radix 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 

ADA: Algorithm Design and Analysis 

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 

about the running 

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

FAQs (Frequently asked Questions)

1. how to find utu btech notes of  Uttarakhand technical university ?

ANSWER. you can find utu(Uttarakhand technical university) notes exclusively on utupapers.com

2.how to find utu previous year paper with solutions ?

ANSWER. click on this link to see utu previous year paper with solutions.

Leave a Comment