Scribd
Upload
18 views21 pages

1.Introduction to Alg Analysis

The document serves as an introduction to data structures, emphasizing their importance in programming and interviews. It covers various data types, operations, and the significance of algorithms in organizing and manipulating data efficiently. Additionally, it discusses computational complexity, efficiency measurement, and different notations used to analyze algorithm performance.

Uploaded by

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

1.Introduction to Alg Analysis

The document serves as an introduction to data structures, emphasizing their importance in programming and interviews. It covers various data types, operations, and the significance of algorithms in organizing and manipulating data efficiently. Additionally, it discusses computational complexity, efficiency measurement, and different notations used to analyze algorithm performance.

Uploaded by

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

INTRODUCTION TO DATA STRUCTURES

Dr. S. Vidhusha

Computer Science and Engineering


School of Engineering

Shiv Nadar University Chennai


Purpose of Study..

Most important subject for Interviews

Why study Most of the time you will be judged based


Data on your knowledge in this subject

Structures This is your chance to improve your


Course? programming Skills

Lets you think of better solutions for


problems
Programs too Require Organization of Data
What are • Data may be organized in many
Data ways;
• Logical or Mathematical model of
Structure a particular organization of data
is called a data structure
s?
Data Types that
You Know Already
• Primitive Data Types
• Int
• Char
• Float
• Boolean
• Non-Primitive Data Types
• Arrays
Int

What are the Float


operations
allowed to be Double
performed on:
Char

Array
Abstract
Data Type
Classification of Data Structures
Time Complexity

Complexity
Analysis
Space Complexity
Definition of an Algorithm

• An algorithm consists of a sequence of explicit and unambiguous


finite steps which, when carried out for a given set of initial
conditions, produce the corresponding output and terminate in a
finite time.
• A finite set of statements that guarantees an optimal solution in
finite interval of time.
What are Data Structures?
•Data structures let the input and output be represented in a way that can be
handled efficiently and effectively.

•It’s a way of organizing, storing and retrieving data and their relationship with each
other.
Array

Linked List

Stack
Queue
Tree
Why Data Structures?

Goal: To organize data

Criteria: To facilitate efficiency and effectiveness

Actions : Storage of data


Retrieval of data
Manipulation of data

Design Issue: Select and design the algorithm appropriately.


Data Structure Operations
1) Traversing

Accessing each record exactly once so that certain items in the record may be processed

2) Searching

Finding the location of the record with the given key value or finding the location of all records which satisfy one or more conditions

3) Insertion

Adding a new record to the structure

4) Deletion

Removing a record from the structure

5) Sorting

Arrange the records in a logical order

6) Merging

Combining records from two or more files or data structures into a single structure.
Approaches in Solving a Problem

• According to top-down strategy we can employ the following steps as


an approach to solve a given problem,
1. Breaking a problem into sub-problems
2. Choice of the suitable data structure
3. Construction of loops
4. Establishing initial condition for loops
5. Finding iterative construct
6. Termination of loops
Computational Complexity
• The computational complexity can be measured in terms of space and time required by
an algorithm.
Space Complexity : Amount of memory required to run the algorithm.
Time Complexity : Amount of time required to run the algorithm.

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.
Running Time of an Algorithm

• Factors affecting running time:


• Nature of input
• Number of inputs
• Number of steps/primitive operations

Running time is measured in terms of number of steps/primitive operations.

Generally time grows with size of input, so running time of an algorithm is usually
measured as function of input size.

• Should be Independent from machine, OS & H/W.


Analysing a Strategy - Example

// 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 1,2,8: Once
s = s + A[i]; 3,4,5,6,7: Once per each iteration
5 6 7 of for loop, N iteration
return s; Total: 5N + 3
}
8 The complexity function of the
algorithm is : f(N) = 5N +3
Growth of 5N+3

• Estimated running time for different values of N:

• If,
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.


Asymptotic Notation
• The methodologies that are used to estimate and represent the efficiency of an algorithm.
• This notation compares and classifies functions that ignores constant factors.
• Represented in O, o, , Ω.

1. Big-oh notation (O)-Worst case running time of an algorithm concerned with large values of N.

2. Big-omega notation (Ω)-Best case running time of an algorithm concerned with large values of N.

3. Big-theta notation ) - Average case running time of an algorithm concerned with large values of N

4. Little-oh notation (o)-Worst case running time of an algorithm concerned with small values of N.
Classifications of Algorithm Analysis

1. Worst – Case Efficiency : The worst–case efficiency of an algorithm can be


defined as its efficiency for the worst-case input of size n for which the
algorithm runs for the longest among all possible inputs of that size.

2. Best – Case Efficiency : The best–case efficiency of an algorithm can be


defined as its efficiency for the best-case input of size n for which the
algorithm runs for the fastest among all possible inputs of that size.

3. Average – Case Efficiency : The average–case efficiency of an algorithm can


be defined as its efficiency for the random input of size n, which makes some
assumptions about possible inputs of size n.
Example – Sequential Search
Algorithm – Sequential Search (A[0…n-1], K)
// Input : An array A[0…n-1] and a search key K.
// Output : Returns the index of first element of A that matches R or returns -1 if
there are no matching elements.
i -> 0
while i<n and A[i] # k do
i -> i+1
if i<n return i
else return -1
• Here, Best case efficiency is O(1) where 1st element itself is the search element
& worst case is O(n) where last element is the search element or search
element can’t be found in array.

You might also like