Scribd
Upload
28 views38 pages

(Algorithms) Algorithms 10 Class Notes None

The document outlines a lecture by Aditya Sir focused on data science and artificial intelligence, specifically discussing algorithms and a test series with over 1500 questions. It includes various topics such as Dijkstra's algorithm, edge disjointness in graphs, and sorting algorithms. The document also features sample questions and solutions related to these topics.

Uploaded by

xiridov484
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
28 views38 pages

(Algorithms) Algorithms 10 Class Notes None

The document outlines a lecture by Aditya Sir focused on data science and artificial intelligence, specifically discussing algorithms and a test series with over 1500 questions. It includes various topics such as Dijkstra's algorithm, edge disjointness in graphs, and sorting algorithms. The document also features sample questions and solutions related to these topics.

Uploaded by

xiridov484
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 38

Data Science &

Artificial Intelligence

Algorithms
Test Series 1500+

Lecture - 10 By- Aditya sir


Recap of Previous Lecture

Topic MisiGuestions

Topic
Topics to be Covered

Topic
Questions
Topic
pyas

Doubts

3
Topic : Test Series 1500+

#Q. Suppose Kn is a complete graph with ‘V’ vertices. How many edge
disjointness spanning trees are possible ?

A V B v 1x

C D

c 7 4 921
n 4 4X B n u 3x
D n 4 IX
Soln kn Contraph
Common
edge disjointness No edge in

A
91 K 13 or

o_0
B
on

4
12 Ky v4
mess
my
1 7

3edges

0 0 o_0

11

o
o edge disjoint 0

4
MCSTS
Topic : Test Series 1500+

#Q. Assume Dijkstra's algorithm is used to find the shortest path from node ‘A’
in the following graph G :

Am 4

A The number of edges are not included in any of the shortest path from
node A is ________.
B sum cost of these edges
of
Dijkstra SSSP
Spanningtree

20 A
A B

soul SSSP
E
501A Spondee
C D
CDX
40 B
3043
EBX
4CEX
EDX
13 Cost 10 60
of missing edges 40
55
1169

4
Topic : Test Series 1500+ w cycle may be present

#Q. Consider the following statements: whichareTI

S1: If graph contain positive and negative edge weight then, Bellman

Talk S2:
0
ford always give the correct answer. tosssp
Bellman ford algorithms find out all negative edges weight cycle in
PY the given graph if they are reachable form source.
A S1 only B S2 only
Am B
C Both D None
x
Bellman Ford SSSP
Sold to Solve
Algos SSSI
net
meat _man
edges edges but Cycle
no
water
Ziggy

a Bellmanford
Dynamic
Programmig
5
Topic : Test Series 1500+

#Q. Consider the following directed graph G:


What will be shortest path from B to E by using Dijkstra's algorithms?

A BADCFE B BADE
x
C BADFE
X D BDE
x
Sold A
BADCFE

A D C F E
B
4 6 12 10 5 370
B BADE B A D E
4 6 50 60X
F E
c BADFE B A D

6
4 6 X
D BDE B D E

7
SSSP Spanning Tree
Dijkstra
source
1ps
10 A

B
JD
75
A 804 13
4453
E 3243
90 B 60403
ED 37173
D C F E
B8 A
Topic : Test Series 1500+

#Q. Consider the following directed graph G:


What will be the cost of shortest path from B to E by using Dijkstra's
algorithms?

Solve Matrix Apps


using
Soln

Perth A B C D E F

113
010080
B A 1 9010000 80

4 0 11 60 80
BIA D
BA D I 40 22 10 60
BADCF
I E TI 32

10 37 32
IBADCFE 40 22

24 Iv
Topic : Test Series 1500+

AI elem
wisecomparisons
merging Ago

2 way merging
dfFet
In genal merging Algo

is
D
min
Blase min

Worst Case Mtn 1

24
m n

lg Lists
780 Fs Fs 8

x
x
4 lists
BC 1 8
Do 1
we
na I
2 list
Bc My
we 1
X
last
BC M D
WC n s

24
overall
1
Best case 4 1 8 2x Ny 1
1
comp 12 2
min
at every 3
12
merge
1 Ix n 1
Worst Case 4 4
1 2 12
1
1 4 1 2
1
3
24
BC Given n 1000
WC
Diff
3h 7 31 3
101
7

3h 7 7
31 3 500

1500 7
7
31 14930

24
Topic : Test Series 1500+

#Q. Consider an array which contain n indexes [1 to n] Number of inversions in

o
this array are atmost n then which algorithm is best suitable to sort the
above arrays.

A Insertion sort B Bubble sort

C Selection sort D Merge sort

Amit
Sol

atmuxno.ofinvesions.­TL
Sort On d
insertion
of
d
elems
n total no
of
d inversions
max no
of
d 01m

24
TC 01mn
If
W C Insertion Sort 01m

1 ei.me
question
given
not a valid case
for sorted away
almost
at most Invxnsy

y
24
Topic : Test Series 1500+

#Q. Let G be the directed , weighted graph shown below:

0
If the cost of the shortest path from A to F is X and number of same cost
of A to F is Y then the value of X * Y is_____________.
path
A F
HI Solm using Dijkstra min lost

Affi possible paths from It


2
1 A B F 18 4 2

B F 612 513
2 A C E D B F 6 2 4 1 3

A C F
6 4 12 18 IT
24
min lost A F 16

Such paths 2

16 2
Y
1321

24
PII 2021 2m
the below graph
distinct
MCST of
The no
of
b c

V41 d
a g

TEE
24
Sold
KniskalAly
n 7
in MIST
edges
v v e n 1

1b y 7 1
Ed
D
i
3C
Lose
24
MISTS
Total
31 34 3 3 X

3 3

24
Topic : Test Series 1500+

#Q. Which of the following algorithm can be used to sort n integers in the range
3 so
[1,…10 ] in O(n) time?

01m 01m
we we

A Selection sort B Bubble sort

C Radix sort D Quick sort


we 09m

Amit
i 51000

need
Oln d
TC O n
Basot TC

n no
of ellen
d max no of digits
10 max digits d g in elem ofippan
any
looo

24
TC Ofn 4
011
Topic : Test Series 1500+

#Q. Suppose, a graph contain 50 vertices and 120 edges the weight of MST is
300. If the weight of each edge of G is increased by 6, then the weight of
MST becomes___________.

Given n 50 9 120 1
Cost MIST
Cost MCST 300

A
E
7
6

A most yt

8
111
I niedges

24
vertiles nu edges
n
Inguinal in most

s
MCST 1 6
300 n

300 300 50 1 6

300 49 6
300 6
300

300 294 15943


24
2 mins Summary

Topic

Topic

Topic

Topic
THANK - YOU

Telegram Link for Aditya Jain sir:


https://t.me/AdityaSir_PW

27

You might also like