Data Structures and Algorithms (CS
F211) – L1
BITS Pilani Prof.N.L.Bhanu Murthy
Hyderabad Campus
Two discoveries that changed the world !!
Johannes Gutenberg (1398 - February 3, 1468)
BITS Pilani, Hyderabad Campus
Two discoveries that changed the world !!
Decimal System invented in India around 600AD
Al Khwarizmi (780 AD – 850 AD) from Baghdad laid
out basic methods for adding, subtracting, multiplication
and dividing numbers
These procedures were precise, unambiguous,
mechanical, efficient, correct
In short they were called Algorithms (a term coined
to honor Al Khwarizmi - algorithm stem from Algoritmi,
the Latin form of his name)
BITS Pilani, Hyderabad Campus
What is an algorithm?
A clearly specified set of simple instructions to be followed to solve
a problem
Takes a set of values, as input and
produces a value, or set of values, as output
May be specified
In English or Hindi or Telugu
As a computer program
As a pseudo-code
BITS Pilani, Hyderabad Campus
Some Vocabulary with an example
Problem: Sorting of given keys
Input: A sequence of n keys a1, . . . , an.
Output: The permutation (reordering) of the input sequence such that
a1 ≤ a2 ≤ · · · ≤ an−1 ≤ an.
Instance: An instance of sorting might be an array of names, like {Mike,
Bob, Sally, Jill ,Jan}, or a list of numbers like {154, 245, 568, 324,
654, 324}
Algorithm: An algorithm is a procedure that takes any of the possible
input instances and transforms it to the desired output.
BITS Pilani, Hyderabad Campus
Which algorithm is better?
Who is topper in BPHC?
Algorithm 1: Algorithm 2:
Sort A into decreasing order int i;
int m = A[1];
Output A[1]. for (i = 2; i <= n; i ++)
Which is better?if (A[i] > m)
m = A[i];
return m;
BITS Pilani, Hyderabad Campus
Who’s the champion?
BITS Pilani, Hyderabad Campus
“Better” = more efficient
Time
Space
Measure efficiency (asymptotic notation)
O(n)
o(n)
Ω(n)
Ө(n)
BITS Pilani, Hyderabad Campus
Sorting Algorithms
3 7 9 17 5 2 21 18 33 4 Comparison Based
Bubble Sort
Quick Sort
Insertion Sort
Merge Sort
17 9 7 5 3 33 21 18 4 2 Heap Sort
Non-Comp Based
? Radix Sort
Bucket Sort
33 21 18 17 9 7 5 4 3 2
Lower bound on comparison based algorithms
BITS Pilani, Hyderabad Campus
Name of array (Note that all
elements of this array have the
Data Structures
same name, c)
c[0] -45
c[1] 6
Array
c[2] 0
Linearly Ordered Set c[3] 72
c[4] 1543
c[5] -89
c[6] 0
Head Linked List c[7] 62
node node
c[8] -3
c[9] 1
Data Next Data Next c[10] 6453
c[11] 78
object2 object Position number of the
element within array c
BITS Pilani, Hyderabad Campus
Data Structures
Hash Tables
Stack
Set with delete operation
specified (LIFO)
Queue
Remove Insert
(Dequeue) front rear (Enqueue)
BITS Pilani, Hyderabad Campus
Data Structures
Binary Tree
Heap
26
17 41
14 21 30 47
Red Black Tree
10 16 19 23 28 38
7 12 15 20 35 39
BITS Pilani, Hyderabad Campus
Data Structures
Skip List
BITS Pilani, Hyderabad Campus
Algorithm Techniques – Divide and Conquer
Matrix Multiplication
Nearest Points
BITS Pilani, Hyderabad Campus
Algorithm Techniques – Dynamic Programming
Efficient algorithm
to compute F(n)
Leonardo Fibonacci
1170-1250
BITS Pilani, Hyderabad Campus
Algorithm Techniques – Dynamic Programming
Matrix Chain Product
BITS Pilani, Hyderabad Campus
Algorithm Techniques – Dynamic Programming
If the postage is n, what is the minimum number of stamps to
cover the postage?
BITS Pilani, Hyderabad Campus
Algorithm Techniques – Greedy Approach
Krusal’s Minimum Spanning Tree Algorithms
8 10 14 10 14
1 3 5 7 1 3 5 7
7 3 7 4 6 3
2 4 12 6 2
2 4 6 8 2 4 6 8
9
Prim’s Minimum Spanning Tree Algorithms
8 10 14 10 14
1 3 5 7 1 3 5 7
7 3 7 4 6 3
2 4 12 6 2
2 4 6 8 2 4 6 8
9 BITS Pilani, Hyderabad Campus
Algorithm Techniques – Greedy Approach
Task Selection Problem: Selecting as many disjoint tasks
as possible.
19
BITS Pilani, Hyderabad Campus
P, NP, NP-Complete, NP Hard
Complexity Class P
Set of all decision problems (or languages) that can be solved in polynomial time
Complexity Class NP
Set of all decision problems (or languages) that can be verified by a polynomial-
time algorithm
NP NPC
NP-completeness
A language L is NP-complete if
L is in NP and
All other languages in NP are polynomially reducible to L P
BITS Pilani, Hyderabad Campus
P, NP, NP-Complete, NP Hard
Home city
Visit city
Millennium problems (US $1,000,000 per problem)
Birch and Swinnerton-Dyer Conjecture
Hodge Conjecture
Navier-Stokes Equations
Is P = NP?
Poincaré Conjecture
Riemann Hypothesis
Yang-Mills Theory
BITS Pilani, Hyderabad Campus
Evaluation (300 Marks)
8)
Q1 (1
8)
(1
5 )
Q2
(7
em
Co S
mp id
re ( M e st (60)
120 T
) Mid
La
Ev b C
alu on
La
ati tinu
b
)
on ou
t (30
Co
Tes (24)
(75 s
)
nt
Lab pre
st
Ev
ComTe
al
b
La
(75)
BITS Pilani, Hyderabad Campus
Teaching & Evaluation
CS F 211 – L P U – 3 1 4
Team
Prof. N.L.BHANU MURTHY (Lecture)
Dr. Barsh Mitra (2 Tutorials + 1 Labs)
Dr. Odelu Vanga (1 Tutorial + 2 Labs)
Dr. Manjanna
Dr. Ramaswamy Venkatakrishnan
Ms.BSAS Rajita (1 Lab)
Ms.Priyanka Rishikesh Chaudhary
Ms. Sahithi T(TA)
Make-up Policy
No makeup for quizzes, lab assignments and lab test.
Make-up for other tests will be granted on prior permission and on justifiable grounds only.
Course Notices
All notices pertaining to this course will be displayed on the LTC Notice Board as well as
the CS & IS Notice Board.
Chamber Consultation
Thursday 1500 Hrs – 1600 Hrs
BITS Pilani, Hyderabad Campus
Text Book
Also known as CLRS book
Introduction to Algorithms, 2nd edition, 2001,
- Cormen, Leiserson, Rivest, and Stein
BITS Pilani, Hyderabad Campus
Reference Book
Micheal T. Goodrich and Roberto Tamassia:
Algorithm Design: Foundations, Analysis and Internet examples
(John Wiley &Sons, Inc., 2002)
BITS Pilani, Hyderabad Campus
Reference Books
Jon Kleinberg and Eva Tardos. Algorithm Design. Pearson Education. (2007)
BITS Pilani, Hyderabad Campus
Reference Books
Data Structures and Algorithms - Alfred V. Aho, John E. Hopcroft,
Jeffery D.Ulman
BITS Pilani, Hyderabad Campus
Reference Books
Sanjoy Das Gupta, Christos Papadimitriou, Umesh Vazirani: Algorithms
(Tata McGraw-Hill Publishers)
BITS Pilani, Hyderabad Campus
Reference Books
Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran. Computer Algorithms
BITS Pilani, Hyderabad Campus
Thank You!!
BITS Pilani, Hyderabad Campus
