Lecture 01

Overview of Data Structures and Algorithms

Asma Sattar
Lecturer
Department of Computer Science
asma.sattar@nu.edu.pk
 Some Rules

 Raise your hand before asking any question and then

WAIT for the permission
 Never ever Miss a class
 Never ever “sleep” in the class

2 Design and Analysis of Algorithm Tuesday, January 17, 2017

 Course Objectives

 To introduce the basic theory of complexity and data

structures as basic building blocks.
 To develop the skills to analyze time (and space)
requirements for a data structure and associated
algorithms
 To pick the right data structure for a given problem.

3 Design and Analysis of Algorithm Tuesday, January 17, 2017

 Course Policy

 Credit hours :(3+1)

 Quizzes 10%
 Assignments 10%
 Mid term I 15%
 Mid term II 15%
 Final exam 40%
 Project 10%

4 Design and Analysis of Algorithm Tuesday, January 17, 2017

 Reference Books

 Data Structures by Seymour Lipschutz

 Fundamentals of Data Structures in C++ by E. Horowitz, S.

Sahni, and D. Mehta,

5 Design and Analysis of Algorithm Tuesday, January 17, 2017

 Today’s Lecture

 Basic Definitions

6 Design and Analysis of Algorithm Tuesday, January 17, 2017

 Some basic Definitions

 Data : Simple values or set of values

for e.g 18
 Elementary data Item
 Group data Item

 Information : Anything which give you meaning full

information for e.g my age is 18

7 Data Structures and Algorithms (CS-210) 1/22/2016

  Record : Collection of field values of an instance
 Attributes: Name Age Gender
 Values : abc 18 F
 Field: Its single elementary unit of column. It represent a
attribute e.g field of name
 File : Collection of records
 Key : which uniquely identify data.
 For e.g Regestration number of a student.

8 Data Structures and Algorithms (CS-210) 1/22/2016

  We need to be store in data so it can be used by
programs to produce some useful information
 E.g.
 List of students
 List of books and their prices
 Table of colors
 Record of universities

9 Data Structures and Algorithms (CS-210) 1/22/2016

 What is Data Structure
 Data Structure is the mechanism to store data
 Different data structures are used to store different type
of data
 A data structure is chosen to retrieve the information
efficiently
 More specifically, Data structure provides a way of
organization for a collection of data items

10 Data Structures and Algorithms (CS-210) 1/22/2016

 Few Data Structures

11 Data Structures and Algorithms (CS-210) 1/22/2016

 Efficiency

 A solution is said to be efficient if it solves the problem

within its resource constraints
 Space (memory)
 Time
 The cost of any solution is the amount of resources that
the solution consumes

12 Data Structures and Algorithms (CS-210) 1/22/2016

 Examples
 A collection of 3,000 texts with average of 20 lines each
with average 10 words / line
 600,000 words
 Find all occurrences of word “happy”
 Suppose it takes 1 sec, to check a word for correct
matching
 What to do?

13 Data Structures and Algorithms (CS-210) 1/22/2016

 Example (cont.)
 Choices we have:
Sol. 1 Sequential matching: 1 sec. x 600,000 words = 166 hours
Sol. 2 Binary searching:
- order the words
- search only half at a time
Ex. Search 25 in 5 8 12 15 15 17 23 25 27
25 ? 15 15 17 23 25 27
25 ? 23 23 25 27
25 ? 25
How many steps?
 log 2 600000 = 19 sec. vs .166 hours!

14 Data Structures and Algorithms (CS-210) 1/22/2016

 Need for Data Structures
 Programs’ design depends crucially on how data is
structured for use by the program.

 It can affect in several ways:

 Implementation of some operations may become easier or
harder.
 Speed of program may dramatically decrease or increase.
 Usage of memory may decrease or increase.

15 Data Structures and Algorithms (CS-210) 1/22/2016

 Algorithm
 An algorithm is some procedure for solving a problem in
finite number of steps
 We can say algorithm is the sequence of
instructions/steps that are performed to transform some
input to some output
 Each instructions having a clear meaning
 Each instruction requires finite amount of effort

16 Data Structures and Algorithms (CS-210) 1/22/2016

 Good Algorithm?
 Run in less time
 Consume less memory

 But computational resources (time complexity) is usually

more important
 More mathematical  Big-O notation

17 Data Structures and Algorithms (CS-210) 1/22/2016

 Time Complexity
 Exact count of operations T(n) as a function of input size
n
 Complexity analysis using big O(...) bounds
 By using constant time, linear, logarithmic, exponential,
complexities
 Used to analyze data structures
e.g. Searching Algorithms, Sorting Algorithms etc.

18 Data Structures and Algorithms (CS-210) 1/22/2016

 Time Complexity
Factors that should not affect time complexity analysis:
 The programming language chosen to implement the
algorithm
 The quality of the compiler
 The speed of the computer on which the algorithm is to
be executed

19 Data Structures and Algorithms (CS-210) 1/22/2016

 Time Complexity?
Objectives of time complexity analysis:
 To determine the feasibility of an algorithm by
estimating an upper bound on the amount of work
performed
 To compare different algorithms before deciding on
which one to implement

20 Data Structures and Algorithms (CS-210) 1/22/2016

 Measuring Efficiency
 The efficiency of an algorithm is a measure of the
amount of resources consumed in solving a problem of
size n.
 The resource we are most interested in is time
 We can use the same techniques to analyze the consumption of
other resources, such as memory space.

 How to measure the efficiency of the algorithm?

21 Data Structures and Algorithms (CS-210) 1/22/2016

 Ways to measure Efficiency
 Run the program and see how long it takes
 Run the program and see how much memory it uses

 We need to observe Lots ofVariable

 What is the input data?
 What is the hardware platform?
 What is the programming language/compiler?

 If a program is faster than another at the moment does this

means it will always be faster?
22 Data Structures and Algorithms (CS-210) 1/22/2016
 Want to achieve platform
independence
 Use an abstract machine that uses steps of time and
units of memory, instead of seconds or bytes

 Each elementary operation takes 1 step

 Each elementary instance occupies 1 unit of memory

23 Data Structures and Algorithms (CS-210) 1/22/2016

 Running Time of an Algorithm
 Running time is measured in terms of number of
steps/primitive operations performed

 Generally time grows with size of input, so running time

of an algorithm is usually measured as function of input
size n.

 Independent from machine, OS

24 Data Structures and Algorithms (CS-210) 1/22/2016

 Simple Example - 1
// Input: int A[N], array of N integers
// Output: Sum of all numbers in array A
int Sum(int A[], int N)
{
int s=0;
for (int i=0; i< N; i++)
s = s + A[i];
return s;
}
How should we analyse this?
25 Data Structures and Algorithms (CS-210) 1/22/2016
 Simple Example - 2
// Input: int A[N], array of N integers
// Output: Sum of all numbers in array A

int Sum(int A[], int N){

int s=0; 1
for (int i=0; i< N; i++)
2 3 4
s = s + A[i];
5 1,2,8: Once
return s;
6 7
3,4,5,6,7: Once per each iteration
}
8 of for loop, N iteration
Total: 5N + 3
The complexity function of the
algorithm is : f(N) = 5N +3

26 Data Structures and Algorithms (CS-210) 1/22/2016

 Simple Example – 3 Growth of
5n+3
Estimated running time for different values of N:

N = 10 => 53 steps
N = 100 => 503 steps
N = 1,000 => 5003 steps
N = 1,000,000 => 5,000,003 steps

As N grows, the number of steps grow in linear proportion

to N for this function “Sum”

27 Data Structures and Algorithms (CS-210) 1/22/2016

 What Dominated in previous
example?
What about the +3 and 5 in 5N+3?
 As N gets large, the +3 becomes insignificant
 5 is inaccurate, as different operations require varying
amounts of time and also does not have any significant
importance

Fundamental is that the time is linear in N

Asymptotic Complexity: As N gets large, concentrate on

the highest order term:
 Drop lower order terms such as +3
 Drop the constant coefficient of the highest order
28
term and
Data Structures i.e.Algorithms
N (CS-210) 1/22/2016
 Complexity
 The 5N+3 time bound is said to "grow asymptotically"
like N
 This gives us an approximation of the complexity of the
algorithm
 Ignores lots of (machine dependent) details, concentrate
on the bigger picture

29 Data Structures and Algorithms (CS-210) 1/22/2016

 Difference in Analysis
for(i=0;i<m;i++) for(i=0;i<m;i++)
for(j=0;j<n;j++) { }
for(j=0;j<n;j++)
for(k=0;k<q;k++)
{ } { }
for(k=0;k<q;k++)
{ }
O(n3)
O(n)

30 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 Counting Primitive Operations
 By inspecting the pseudo code, we can determine the maximum
number of primitive/basic operations executed by an algorithm,
as a function of the input size

31 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 Task
for (i=0; i<n; i++){
for (j=i; j<n;j++){
Sequence of statements….
}
}

32 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 Task

33 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

34 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016
 Asymptotic Notations
 O notation :Big-O is the formal method of expressing
the upper bound of an algorithm's running time.
 It's a measure of the longest amount of time it could
possibly take for the algorithm to complete.
 Formally, for non-negative functions, f(n) and g(n), if
there exists an integer n0 and a constant c > 0 such that
for all integers n > n0, f(n) ≤ cg(n), then f(n) is Big O of
g(n).

35 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 Asymptotic Notations
 O-notation

36 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 Asymptotic Notations
 Big-Omega Notation Ω
 This is almost the same definition as Big Oh, except that "f(n) ≥
cg(n)”
 This makes g(n) a lower bound function, instead of an upper bound
function.

 For non-negative functions, f(n) and g(n), if there exists an integer

n0 and a constant c > 0 such that for all integers n > n0, f(n) ≥
cg(n), then f(n) is omega of g(n). This is denoted as "f(n) = Ω(g(n))".

37 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 Asymptotic notations (cont.)
  - notation

38 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 Example : Big Omega (Ω)
 f(n)=3n +2 & g(n)=n
F(n)>=c(n) ?
let c=1 , 3n+2>=n
n0=1
For every n>=1 and c=1
f(n)>=c(g(n))
or
f(n)= Ω(g(n))

39 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 => (3n+2)=Ω (n2) ?????
 No

=> f(n)= Ω (n)

if f(n) is lower bounded by ‘n’ then it can be lower
bounded by any g(n) which is lower bounded by ‘n’
i-e (3n+2)=Ω (logn)
(3n+2)=Ω (log (log (n)))
But we always go for the closest lower bound or tighter
lower bound

40 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 Asymptotic Notations
 Theta Notation Θ
 Theta Notation For non-negative functions, f(n) and g(n),
f(n) is theta of g(n) if and only if f(n) = O(g(n)) and f(n) =
Ω(g(n)). This is denoted as "f(n) = Θ(g(n))".

This is basically saying that the function, f(n) is bounded

both from the top and bottom by the same function, g(n).

41 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 Asymptotic Notations (cont.)
 -notation

42 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 Example : Theta(Θ)
 f(n)=3n +2 & g(n)=n
F(n)<=c1 g(n) ??
F(n)>=c2 g(n) ??
let c1=4 , 3n+2>=4n, n0>=2, => F(n)=O(g(n))
let c2=1 , 3n+2>=n, n0 >=1, => F(n)=Ω (g(n))
For all values of n => n0>=1
For every n>=1 and c=1
c2g(n)<=f(n)<=c1(g(n))
or
f(n)= Θ (g(n))
43 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016
  3n+2=Θ(n)
 3n2+2n+1=Θ(n2)
 6n3+n2=Θ(n3)

44 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 Function of Growth rate

45 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016

 Rate of Growth
 Consider the example of buying elephants and goldfish:
Cost: cost_of_elephants + cost_of_goldfish
Cost ~ cost_of_elephants (approximation)
 The low order terms in a function are relatively
insignificant for large n
n4 + 100n2 + 10n + 50 ~ n4

i.e., we say that n4 + 100n2 + 10n + 50 and n4 have the

same rate of growth

46 Data Structures and Algorithms (CS-210) 46 Tuesday, January 27, 2016

 procedure bubbleSort( A : list of sortable items )
n = length(A)
for j = 1 to n-1
swapped = false
for i = 1 to n-1 inclusive do
/* if this pair is out of order */
if A[i-1] > A[i] then
/* swap them and remember something changed */
swap( A[i-1], A[i] )
swapped = true
end if
end for
if not swapped
return
end for
end procedure
47 Data Structures and Algorithms (CS-210) Tuesday, January 27, 2016
 Home Task

 Algorithm of Bubble sort in descending order

48 Data Structures and Algorithms (CS-210) 1/22/2016

 Questions?
Question in my Should I ask
mind is ? this ?

hmmmmmmmmm?
Sorry I was
sleeping
madam !

Data Structures and Algorithms (CS-210) 1/22/2016

 If you have any query please feel free to ask

Phone: 111-128-128 (ext 173)

Email: asma.sattar@nu.edu.pk
Office hours:
Monday to Friday 11:00AM to 3:00PM

FAST – NU FAISALABAD CHINIOT CAMPUS, PAKISTAN

50 Data Structures and Algorithms (CS-210) 1/22/2016