Day:
Date: /20
y : Y a s ı r A b d u l l a h Barg
Written b M i r z a
DSA
Data Structure g Algorithms
Hand written Notes
Topics we will cover are:
DSA Introduction
History
.
OSA
• OSA Simple Algorithms
Arrays
.
•DSA Arrays
•DSA Bubble Sort
DSA selecbion Sort
•DSA Insertion Sort
DSA Quick Sort
•DSA Counting Sort
.DSA Redix Sort
-DSA Merge Sort
-OSA Linear Search
•DSA Binary Search
Linked Lists
•DSA LUnked lists
• OSA Linked Lists in Memory
•OSA linked lists Typer
•DSA Linked list Operations.
Date:_ /20
Day:
Stack and Queves
DSA Stacks
•DSA Queves
•Hash Tables
•DSA Hash Tables
•DSA Hash Sets
• DSA Hash Maps
Trees
DSA Trees
• DSA Binary Trees
• DSA Pre-ordered. Traversol
DSA In- ordered Traversal
DSA Post-ordered Traversal
DSA Array Implementation
•DSA Binary Search Trees
DSA AVL Trees
Graphs
•DSA Graphs
• Graphs Implementation
•DSA Graphs Traversal
•OSA Cycle Detection
Shortest Path
•DSA Shortest Path
DSA Dijkstra's Algorithm
• DSA Bellman - Ford
Day:
Date: /20
Minimum Spanning Thee
• DSA Minimum Sponning Tree
OSA Prim's
DSA Kruskal's
Maximum Fow
OSA Mанiтит Flow
OSA Ford- Fulkerson
DSA Edmonds- Karp
Time Complexiby
• Bubble Sort
•S'eleckion Sort
Insertion Sort
•Quick Sort
Counting Sort
Rodin Sort
Merge Sort
• Linear Search
Binary Search
DSA Advanced
• DSA Euclidean Algorithm
DSA Huffman Coding
• DSA The travelling Saleman
• DSA 0/1 Knapsack
• DSA Memoization
• OSA Tatulation
•OSA Dynamic frogramming
DSA Greedy Algorithms
Date: /20 Day:
DSA- Introduction (Depth, therniotcal)
DSA (Data Strucbures and al go ri ci ns ) is th e fo nd am en te l
pant of computer science that teaches you hows
1o think &f sdve complex probiem systermat cally
• Using the nght daka structure & algontm
makes your pragram run faster, especally wihen
working with lots of data.
Knowing OSA can help you perform bettar
in job interviews f land great jobs in companies
Example=
my-aray = [7, 12, 9, 4, 11]
minVal = my-aray[o]
for i in myarray:
if i< min Val:
mival =
Print (' Lowest value:', minval)
WWhat Should Already know
DSA s not specific bo any Jangage. You should
have basle undertanding of any programming
Languge
python
C+t
Java
•JavaSonpt.
Select any of progromming language you are
nterested in and start leaming DSA
Date: /20 Day:
DSA Htrstory
The word algorihn comes from 'al-khwarizmi'
named after a persion saolar who lived around
800.
The concept of agorithm prablem-solving can
be back back to ancient times, long after before
the invention of computer
The study of DSA really tok off with the invention
of computers in 1940s, to efficiently mange & process
data
Today DSA is key part of computer Scence.
equation & profissional pragramming, helping us
o create faster and more powerful soltwan
Inbroduction To ,Dota Structures & Algo
Data Structures are ways to store & organize dala
Agorithms are steps-bystep methods to solve probtlem
using that data
Tagether, DSA helps us handle large data and sowe
problems fasters
What are Data Structures?
4 data structure is a way bo store and
based what have and
organize data on we
want to do with 1H.
whate me
Example:
A family tze help us see how peYoopulre
are related and eosly find relatives, like manths
mother Without link in tree t would
motter's
be harder to understand relcionship
Date: /20 Day:
Data Structures help manage Jarge amounts of
data efficiently, like in databases or search engine
and are key to create fast algorithms
Types of Data Structures
Primitive: Basic types like integer foat, chars & bool
Abstracd: Bullt from primitive type e.g amays, link
lists, stacks, queves, trees, and graphs.
What are Algorithms?
An algorithm is a lear set of step-by-step
instuetions to solve a problem or reach a goal
Grample
A cooking recape is lke an algonithm,
it lists steps to make a dish In computers, the
steps are writen with in pragramming longuage
and inted of ingredients, we work with data.
• Algorithms are fundamental y foundation of
programming. ood algonthms malke programs faster
and more efficient,
Example of algorithms in real life:
GPS Fendmg the fostest route
Crvise control in car or plane.
• Search engine Ending results
Sorting movies by rating.
In programming, each algorthm Es usuaky dergned
for a specific problem and works with certain data
Structures (e-g bubble sort wortes on arrays)
Date: /20
Day:
Dato Structures bgether with Algorithms
Data Structure + Algortims (DSA) work togetmer
A data structure stores data, & algorithms let you
search, or change or use that data efficienty
DSA & aboul finding the best way to store, access
and process data to solve problems quickly
By Daaming DSA, You con:
Pick the right tool (data Structure (algorithm) for Job
• Make pragram Faster & use less memoy
Solve complex probens step by step.
WWhere DSA s Used2
DSA is everywhere tn sotaware:
Handling huge data( socal Nebwortis, search engine)
• Scheduding tosks (decrding what run first)
Planning routes (GPS Shortest pakh)
Optmizing processes (faster completion)
task
Solving complex problems ( paching, tnachine learing)
Common Areas using DSAS
Operabing Databases, web apps, machtne
systems,
leaming, vides games, cpptography, data analyie
search engines &f many more.
Key Terms In DSA
Algorithms: a
Step by step enstructions to solve
problem
Data-Structure:
A wly to store and organize data
lleg arays, line lists, trees)
Date: /20 Day:
Time Complexity:
How Fast an algorithom runs as data
stze graus.
Space Complesxty!
How much memory an algorithm uses
• Big o Notation=
A way to descoribe firme/memory
growth of an algonithm.
Recurslon:
A fonction calling itself to solve smaller
parts of a problem.
Divide and Conquer:
Breaking a big problem into
smaller ones, sdving each, & combhing results
Brute Forces
Trying 9ll pacible Solutions to find
best one.
Date: /20
Day:
DSA Simple Agonithm
Fibonacci Number
The fibonacci sequence te a list of numbes
wete
The first two numbers are o and 1
• Every next number = sum of 2 previous numbers.
example:
0,1,, 2, 3, 5, 8, 13, 21,
Why its important in programming
• Simple way to lean algorithms (step-by-step)
Can be done with loops ar reursion
Using Lnap
we store last bwo numbers, add them, print the
result, and update the number
prev2, prev1 = 0, 1
print (prev2)
print(prer 1)
for i in range (18).
newtibo = prev1 + prev2
print (newFibo)
prev2, prev1= prevs, newfibo
Using Recursion
A funetion calls itself until we have the required
numbers.
print (o)
print(1)
Lount = 2
der fibonacci ( prev1, prer2):
globl count
Date: /20 Day:
if count < = 19:
newtibo = prev1 + prer 2
print(newfibo.)
Count += 1
fibonacci (newfiba prev1)
fibonacci (,0)
Finding the n-th Fibonacci Number (Recursive)
Formwa F(n) = F(n-1) + F(n-2)
def F(n).
if ne= 1:
retum n.
retum Fi(n-1) + F(n-2)
print (E(19))
Notes
Ihis method is slow For large n, because it
recalculates the same number mony imes
F(5)
F(4) F(3)
F) F)
F(3) FD)
F(2) F11) Fl1) Flo FLL) Flo)
F1) F(o)
Date: /20
Day:
DSA Arrays.
A
What B an array?
• An aray stores mlople elements in order
Many
algorithms use arrays (erg firding the
Powest valve).
Python Example
my-ormay = [7, 12, 9, 4, 11]
Note:
(Rython list vs array): In python, the code above
creates a list (bilt-h dynamic array). for this, you
can treat a list leke an array.
Indexing (zero-based)
Arrays are indexed. Fost element is at index o
(Python, Java, C all use zerobased indexing).
print (my array [0])
Algorithm: Find the lowest valve in an array
Idea(how it works):
• Look at the elements one by one.
• Keep track of the lowest so far voluet
• After checting all elements, the store Jowat
Step-tby-step (plam words):
vañable minval y set it to frst dement.
•Create a
• Go tinugh every element in array.
than minval, set minval to elemel
•If element is less
finishes, minval is the lowest valve.
After the loop
Pseudocode:
min Val = array [0]
for each element in aray:
if element e minval
minval= element
