CS & IT
ENGINEERING
Algorithms
Analysis of Algorithms
Lecture No.- 01 By- Aditya sir
Topics to be Covered
Topic Schedule
Topic Outcomes
Topic Intro to Algorithms
3
About Aditya Jain sir
1.
2. Represented college as the first Google DSC Ambassador. 0
Appeared for GATE during BTech and secured AIR 60 in GATE in very first attempt - City topper
The only student from the batch to secure an internship at Amazon. (9+ CGPA)
9.09
3.
4. Had offer from IIT Bombay and IISc Bangalore to join the Masters program 1
5.
I
Joined IIT Bombay for my 2 year Masters program, specialization in Data Science
Published multiple research papers in well known conferences along with the team
6.
7. Received the prestigious excellence in Research award from IIT Bombay for my Masters thesis
I
8. Completed my Masters with an overall GPA of 9.36/10
9. Joined Dream11 as a Data Scientist
10. Have mentored 12,000+ students & working professions in field of Data Science and Analytics
11. Have been mentoring & teaching GATE aspirants to secure a great rank in limited time
12. Have got around 27.5K followers on Linkedin where I share my insights and guide students and
professionals.
Aditya Jain
the Sir PW
snail
Telegram Link for Aditya Jain sir: https://t.me/AdityaSir_PW
TTTe
Syllabus Age
Topic : Lecture Schedule
1. Analysis of Algorithms
DAA
1. Algorithm Concept and Lifecycle
2. Analysis of Algorithms 1
3. Methodology & Types of Analysis n Analysis
4. Asymptotic Notations
f
mm
Algorithms
5. Framework for Analysing Recursive Algorithms
c of
6. Apriori analysis of Non-Recursive Algorithms
O
7. Analysing Loops
8. Space Complexity Tmpacecompliity
9. Mathematical Background
Design
1 2 3
Divide Guerdy Dynamic
conquerO A Programing
Topic : Lecture Schedule
2. Divide & Conquer (Design Strategies) Rule
British
1. General Method
mindset
2. Max-Min Problem
3. Merge Sort
4. Binary Search Firing
5. Quick Sort
MM
6. Matrix Multiplication Strasser's
7. Long Integer Multiplication (LIM)
Bonds
8. Master Method for D and C Recurrences
9. Recursion Tree
Topic : Lecture Schedule
3. Greedy Method
ᵈ
1. General Method
2. Knapsack Problem
mode
DPP
3. Job Sequencing with Deadlines
4. Optimal Merge Patterns WT
4. Huffman Coding merge
class
_te
5. Minimum Cost Spanning Trees
1. Prims Method
Questions in
2. Kruskal's Method
6. Dijkstra's Shortest Paths Problem
SSSI
Topic : Lecture Schedule
4. Dynamic Programming (DP) Ind
1. The Framework
2. Difference between DP, Greedy Method and Divide and Conquer
o
3. Multistage Graphs
4. Travelling Salesperson Problem
T
5. Binary Knapsack Problem All Pairs Shortest Paths hÑÑ
7. Bellman-Ford Single Source Shortest Paths
8. Longest Common Subsequence us Floydwanshall
10. Matrix Chain Multiplication sum of Subsets
can
11. Optimal Cost Binary Search Tree
Topic : Lecture Schedule
we
5. Graph Algorithms
Directed
1. Representation of Graphs Isundirectedfunnt
2. Graph Traversals
DFS
OF stack
5.2.1 Undirected Connected Graphs
5.2.2 Undirected Disjoint Graphs: DFT
5.2.3 Directed Graphs & Types of Edges
5.2.4 DAG
BFS
QticGraph
5.2.5 FIFO BFS
Head FIFO
Bonus 5.2.6 LIFO BFS
default
Topic : Lecture Schedule
6. Heap Algorithms
GBE
1. Operations : Create, Insert, Delete, Modify
2. Applications : Heapsort
Topic : Lecture Schedule
7. Sets
1. Representations KniskalyEDf
2. Operations
his
final
Topic : Lecture Schedule
8. Sorting Algorithms
1.
At
Basic terminology merge Dna
2. Methods Quick
1. Bubble Sort
I
2. Selection Sort
Heap Heaps
3. Insertion Sort
4. Radix Sort
Topic : Lecture Schedule
9. Backtracking & Branch- Bound Bones
Last
Topic : Lecture Schedule
Reference Books:
a
1. Introduction to Algorithm → Cormen
ftp
2. Fundamentals of Algorithm → Sahni
oananA
Ago 1
Topic : Lecture Schedule
Scope/ Outcomes 1ˢᵗInterni
GATE, TIFR, ISRO, BASIC…..BARC
Placement → Product/service based DE ICI 70011
Google Infosys
Microsoft WIPRO
Accenture
Coding Tests
Topic : Lecture Schedule
Pre-Requisites
1. Data Structures Fundamental i
• [Stacks, Ques, Tree… ]
_e
2. Programming Fundamental
•
else
If-de
• Loops
3. Basic Maths
Series (AP, GP) Revision
In
To 3h
Es
30ᵗʰ Jan
Anecdigest 00
8
at
L.LI
Interview
5ᵗʰ Feb
1m01s
Algorithm
Topic : Lecture Schedule
Algorithm:-
problem.
O
An Algorithm is a collection of finite number of instruction to solve a given
e
These instruction are fundamental and should follow a proper sequence.
a
step by step
atomic
I
BSC
Topic : Lecture Schedule
Tweet
Input (i/p) Algorithm Output (o/p)
[An algorithm may take [Must always produce
we
or more i/ps] at least one output]
or
may
not take Belt
may void greet c
on
itp
Hello AJ
print
Topic : Lecture Schedule
Python:- for Ii in range (0, n+1)
vs
Ag
C++:- For (i =0, I < =0, i + +)
Et
I java python
Program→ Algorithm implemented using some programing language
Algorithm → Pseudo code- for i → o : n
for i = 0 to n pseudo code
(Set of sequential rules /statement /instructions)
logis
fori
for i in range ont
i ic n itt
for o
Topic : Lecture Schedule
Algorithm Lifecycle College
Problem statement → Requirements /constraints → Logic
Design Algorithm
ME
Testing →Coding programming→ Analysis (Time complexity) → check its
↓ (To run it own machine) (efficiency) correctness
Debug To solve problem in
the most efficient way
completed
Topic : Lecture Schedule
Algo AJSir ( ) → 0 inputs
{
print (“Hello students!”)
}
Algo AJsir2( )
{
return 100
}
Topic : Lecture Schedule
Analysis of Algorithm:-
or more
1. Why to analysis ?→ Compare two Algo.
2.
so shffomption
What to analysis?→ on the basis of time/space {Resudece consume point}
3. How to analysis?
Def
Topic : Lecture Schedule
#Q. Why to Analysis ? Algo
In 0
To compare and decide which sudation is the best among different available
solution (Algo.)
P
Problem :- Nagpur → Delhi ON
1. Walk → Soln. (A1)
A1 A2 A3 A4 ?
it
2. Bike /Car→ (A2) r
3. Train→ (A3)
2
4. Flight→ (A4) Time ↓ cos ↑ (Money)
F
Topic : Lecture Schedule
Maggie (P)
Self Cook Chef Zomato Visit Restaurant
(A1) (A2) (A3) (A4)
Topic : Lecture Schedule
#Q. What to Analysis ?
Analysis the consumption of Resources
Resources – Time, space /memory → GATE
Money, Internal Bandwidth, etc.
Number of programmers.
other
metrics
Topic : Lecture Schedule
#Q. How to Analysis ?
How to Analysis ?
Aparna
1
1. Apposition Analysis 2. Apriori Analysis
Analyzing After
Implementation of Algo.
00
Analyzing before
implementation of Algo.
F
Put no code
just logic
Code
Topic : Lecture Schedule right Stowe
1. Apostcriori Analysis
Advantages
1
• Given the exact measurement of time units. faster
High level long → User Programm friendly
1
Low level long → Machine friendly
Disadvantage
• Platform dependent
Software → OS (Linux, windows MAC)
Hardware → (Process /CPU memory (RAM))
Tonict
Programming language dependent cash
Algol Algos
3sec
I
efficient inefficient 7 see
1 1Windows 7
i20 windows 15 is
I
U
F
251
2 A
elys.si
Before implementation
Did app 4
Adv 1 independent
Platform
2
Bog inder
3
Howcoe
feseable
Summary
1 detail
Syllabus
Resources
2 Pre requisite
THANK - YOU
3
Introfoanalysis
6.3011ft
30
