Introduction To Algorithms

Subject Name:
Design and Analysis of Algorithms
Tutor Name:
Shahid Hussain
1
Books
Introduction to Algorithms (Second

Edition) T.H. Cormen, C.E. Leiserson,
R.N. Rivest, C. Stein - McGraw Hill - MIT
Press, 2001
Computer Algorithms: Introduction to
Design and Analysis, Sara Baase, Allen
Van Gelder, Prentice hall, 1999
Introduction to Algorithms, A Creative
Approach, Udi Manber, Addison-Wesley,
2
1989.
Course Outline
Data Structure (Recap)

Introduction of Algorithms and its notation
Basics algorithms and its analysis
Asymptotic notations
Recursion and recurrence relations
Divide-and-conquer approach
Sorting; Search trees
Heaps
Hashing
3
Course Outline (Cont !!!)
Greedy approach
Dynamic programming
Graph algorithms; Shortest paths; Network flow;
Disjoint Sets; Polynomial and matrix calculations;
String matching
NP complete problems
Approximation algorithms.
4
Data Structure Recap
5
The term data refer to collection of

facts or figures
There are two ways to process and
manipulate data.
Data Structure
Refer to temporary and manipulation of data
E.g. Variables and array of a procedural language
Database
Refer to Permanent storage and manipulation of
6 data
Consider following C language

program Execute first time:
Output will 8
Main()
{
int a, b, c; Execute second and
other times.
a=3; Again Output will 8
b=5
// OR cin>>a>>b;
c=a+b;
What concluded here
cout<<Sum=<<c;
7 }
Type of Data Structures according to the

presentation of data (i.e. How data is
presented)
1. Linear Data Structure
1. Sequential Data Structures
1. Array
2. Queue
3. Stack
2. Pointer Data Structure (Linked List)
2. Non Linear Data Structure
8
1. Tree
Type of Data Structures according to

memory representation
1. Logical Data Structure
1. Map data according to partition structure of memory
2. E.g. One Dimensional Array
2. Physical Data Structures
1. Can not map data easily according to partition
structure of memory
2. E.g Two Dimensional Array, Tree etc
3. A special method is needed to convert physical Data
9
Structure into Logical, such as dope vector is used to
Common operation for all Data Structure

are.
Insert ( Insert new item/element into a data structure)
Delete (Remove an item from Data Structure)
Sort (Use to arrange all items in either ascending or
descending order)
Search (Use to locate an element/item of a data
structure)
Merge (Use to combine the elements of more than
one similarly data structure
Traversing (Scanning or visit of each element for
10
view etc)
Array
Linear and sequential
Array is combination of homogenous element with
N Consecutive index numbers (Such as 1,2,3,4, . . .)
Successive memory location (such as 102, 104, 106 . . . )
Successive memory location depend on the size of
data types, such as in C language size of integer data
type is 2 bytes)
Two types of array are commonly used.
One Dimensional (1-D) ( Only logical data structure)
Two Dimensional (2-D) (Physical Data structure)
11 Dope Vector method is used to convert 2-D into 1-D
Stack Data Structure

Work on following principles
LIFO (Last In First Out) OR Total
FILO (First In Last Out) Size=
Two Conditions are N=5
Overflow (It will occur when stack is full and you try to insert
new element)
Underflow (It will occur when stack is empty and you try to
delete an element)
12
Queue Data Structure

Work on following principles
FIFO (First In First Out) OR
LILO (Last In Last Out)
Two Conditions are
Overflow (It will occur when Queue is full and you try to insert
new element)
Underflow (It will occur when Queue is empty and you try to
delete an element)
Type of Queues are
Circular Queue
13 Priority Queue
Linked List Data Structure

Linear and Pointer
Each element of linked list represented through a node
which have two , three or more parts depends on types
of linked list
Type of Linked List are
One way linked List
Two Way linked List (Doubly Linked List)
14
Tree Data Structure

Non Linear Data Structure
Each element of Treerepresented through a node
which have two , three or more parts depends on types
of tree
Types of Tree are
General Tree
Binary Tree
B+ Tree
Balance and Unbalance Tree
15
Graph Data Structure

Non Linear Data Structure
Each element of Graph represented through a node
Type of Graph are
Connected Graph
Weighted Graph
16
Summary
Data structure is way for storing and manipulation

of data
Two main categories or types of data structure
are linear and non linear data structure.
In case of memory representation, data structure
are of two types logical and physical data
structure.
Insert, Delete, Merge, Sort and search are
common operations for all types of data structure.
Array, Stack and Queue are linear and sequential
17 data structures.
What to be Next
In Next lecture, we will discuss algorithms, its

characteristics and convention.
18

Introduction To Algorithms

Uploaded by

Copyright:

Available Formats

Introduction To Algorithms

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Introduction To Algorithms

Uploaded by

Copyright:

Available Formats

Subject Name:

Design and Analysis of Algorithms

Introduction to Algorithms (Second

Data Structure (Recap)

The term data refer to collection of

Consider following C language

Type of Data Structures according to the

Type of Data Structures according to

Common operation for all Data Structure

Stack Data Structure

Queue Data Structure

Linked List Data Structure

Tree Data Structure

Graph Data Structure

Data structure is way for storing and manipulation

In Next lecture, we will discuss algorithms, its

You might also like