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: 
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 
Binomial Heaps 
 Fibonacci Heaps 
D.S. for Disjoint Sets 

Unit III: Contains 4 Chapters: 

Dynamic Programming         

Greedy Method                         

Amortized Analysis                  


Unit IV: Contains 6 Chapters: 



Single-Source Shortest Paths 

All-Pairs Shortest Paths 

Maximum Flow 


Unit V: Contains 4 Chapters: 

Randomized Algorithms 

String Matching 


Approximation Algorithms 

Total: 27 Chapters 

TCS-503: Design and Analysis of Algorithms 

Unit I: Syllabus 





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 



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


set of values 

as input 


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

produces some value, 


set of values 

as output. 



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

Bubble Sort Algorithm 


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



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


Input Input <2,3> 

Algorithm Sum(a,b) 


Print c 



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 


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 


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 


Pseudo Code: Flow Chart: 

1. Begin 

2. Input A and B 

3. Calculate A + B 

4. Print result of SUM 

5. End 


Input A and B 

Calculate A + B 

Print Sum 


Pseudo Code to implement 

sum algorithm 

Flow Chart to implement sum 


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-



Test methods: 

Based on exhaustive search in 

multiple choice 


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


7 2



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


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 


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


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 


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 


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 


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 


Assumes that the input 

is random. 

Provides a prediction 

about the running 


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