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
Growth of Functions
Master Theorem
Heap Sort
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.
0 Comments
Please do not post any spam link