COURSE TITLE

CS-201 DATA STRUCTURE &

ALGORITHM

Course Teacher: Muhammad Awais Khan

Class Room Rules
 Put your mobile phones on silent mode
Evaluation Criteria

Assignments = 15%
Quizzes = 10%
Mid Term = 25%
Final Term = 50%
Evaluation Criteria

 Assignments = 4, 2 before mid

term, 2 after mid terms
 Quizzes = 6
Recommended Text Book
 Data structure and Algorithm Analysis in C++ by
Mark Allen Weiss (available in Pdf).
 Data Structure and Algorithms in C++ by Adam
Drozdek (available in Pdf).
Reference Books
1. A.M Tenenbaum, Data Structures using C and C+
+, Prentice-Hall
2. Nell Dale, C++ Plus Data Structures, Jones and
Bartlet, Inc.
3. Frank M. Carrano, Data Abstraction and Problem
Solving with C++, Addison Wesley.
Goals of this Course
 Learn the commonly used data structures.
 These form a programmer’s basic data structure
“toolkit”.
 Reinforce the concept that costs and benefits
exist for every data structure.
 Understand how to measure the cost of a data
structure or program.
 These techniques also allow you to judge the merits
of new data structures that you or others might
invent.
Course Contents
 Abstract Data Types
 Stacks(Linked Lists and Array implementations)
 Recursion and Analysis of Recursive Algorithms.
 Divide and Conquer Algorithms
 Sorting Algorithm (Selection, insertion, merge,
quick, bubble, heap, shell, radix, bucket).
 Queue
 Dequeuer
 Priority queues
Course Contents (Contd.)
 Linked List and its various types
 Searching
 Tree and its various types
 Graphs
Data Structure and
Algorithm
Definitions:
 Data: Collection of raw facts.
 Data Structure: is representation of the logical
relationship existing between individual elements
of data.
 Data Structure: is a specialized format for
organizing and storing data in memory that
considers not only the elements stored but also
their relationship to each other.
Data Structure
 Definition: A data structure is a specialized format
for organizing, processing, retrieving and storing
data.
 In some cases, the algorithm's basic operations
are tightly coupled to the data structure's design.
 Each data structure contains information about
the data values, relationships between the data
and -- in some cases -- functions that can be
applied to the data.
Data Structure
 In an object-oriented programming language, the
data structure and its associated methods are
bound together as part of a class definition.

 In non-object-oriented languages, there may be

functions defined to work with the data structure,
but they are not technically part of the data
structure.
Data Structure (Contd.)
 Data structure affects the design of both
structural & functional aspects of a program.
Program = algorithm + Data
Structure
 As we known that algorithm is a step by step

procedure to solve a particular function.

Classification of Data Structure
 Data structure are normally divided into two
broad categories:
 Primitive Data Structure
 Non-Primitive Data Structure
Classification of Data Structure
(Contd.)
Primitive Data Structure:
 These are basic structures and directly operated

upon by the machine instructions.

 Data Structures that are directly operated upon

the machine-level instructions are known as

primitive data structures.
 Integer, float, char, constants, string constants,

pointer includes in this category.

 Most commonly used operation on primitive data

structure includes: Create, Selection, Updating,

Destroy or Delete.
Classification of Data Structure
(Contd.)
Non-Primitive Data Structure:
 There are more sophisticated data structures.

 The Data structures that are derived from the

primitive data structures are called Non-primitive

data structure.
 The non-primitive data structures emphasize on

structuring of a group of homogeneous (same

type) or heterogeneous (different type) data
items.
Classification of Data Structure
(Contd.)
Non-Primitive Data Structure:
 Linear Data Structure:

 Linear data structures are kind of data structure that has

homogenous elements.
 The data structure in which elements are in a sequence
and form a linear series.
 Linear data structures are very easy to implement, since
the memory of the computer is also organized in a linear
fashion.
 Some commonly used linear data structures are Stack,
Queue, and Linked Lists.
Classification of Data Structure
(Contd.)
Non-Primitive Data Structure:
 A non-Linear primitive data structures is a data

structure in which data item is connected to

several other data items.
 Non-linear data structure may exhibit either a

hierarchical relationship or parent child

relationship.
 The data elements are not arranged in a

sequential structure.
 The different non-linear data structures are tree,

and graphs.
Need for Data Structures
 Data Structures organize data =>more efficient programs.
 More powerful computers => more complex applications.
 More complex applications demand more calculations.

 Data structures make it easy for users to access and work

with the data they need in appropriate ways.
 Data structures frame the organization of information so
that machines and humans can better understand it.
 These data structures are used with various algorithms
according to need.
Organizing Data
 Any organization for a collection of records that
can be searched, processed in any order, or
modified.
 Example:
 You want to perform standard deviation, average,
mean, median, mode or other such kind of operations
on set of numbers.
 Searching name from the list of names.
 The choice of data structure and algorithm can
make difference between a program running in a
few seconds or many days.
Difference b/w Data Structure and Algorithm

Data structures and algorithms are two interrelated

concepts in computer science.
 Data structures refer to the organization, storage,

and retrieval of data.

 Algorithms refer to the set of instructions used to

solve a particular problem or perform a specific

task.
Difference b/w Data Structure and Algorithm

Aspect Data structure Algorithm

Definitio The way data is organized, A set of instructions used to solve a
n stored, and retrieved specific problem or perform a specific
task
Purpose Provides an efficient way to Provides a systematic approach to
organize and store data for solving problems by breaking them
easy retrieval and down into smaller, more manageable
modification. steps
Operatio Insertion, Deletion, Search, Sorting, Searching, Optimization,
ns Update, Traverse, etc. Pathfinding, etc.
Importan Essential for efficient data Crucial for developing efficient
ce storage and retrieval software solutions
Relations Data structures provide a Algorithms often operate on data
hip framework for storing and structures to process or manipulate
accessing data that algorithms data
can operate on
Example Array, Linked List, Stack, Sorting, Searching, Graph Traversal,
Data Structure Requires
A data structures requires a certain amount of:
 Space for each data item it stores.

 Time to perform a single basic operation.

 Programming effort.
Efficiency
 A solution is said to be efficient if it solves the
problem within its resource constraints.
 Space
 Time
 The cost of a solution is the amount of resources
that the solution consumes.
Selecting a Data Structure
Select a data structure as follow:
 Analyze the problem to determine the resource

constraints a solution must meet.

 Determine the basic operations that must be

supported. Quantify the resource constraints for
each operations.

 Select the data structure that best meets these

requirements.
Some Questions to Ask
 Are all data inserted into the data structure at the
beginning, or are insertions interspersed with
other operations?

 Can data be deleted?

 Are all data processed in some well-defined order,

or is random access allowed?
Data Structure Philosophy
 Each data structure has costs and benefits.
 Rarely is one data structure better than another
in all situations.
 A data structure requires:
 Space for each data item it stores.
 Time to perform each basic operation.
 Programming efforts.
 Abstract Data Types (ADTs)
 An abstract data type (ADT) is a set of
objects together with a set of operations.
Abstract data types are mathematical
abstractions; nowhere in an ADT’s
definition is there any mention of how the
set of operations is implemented.
 Objects such as lists, sets, and graphs,
along with their operations, can be viewed
as ADTs, just as integers, reals, and
booleans are data types.
 Integers, reals, and booleans have
operations associated with them, and so
do ADTs.
Abstract Data Types (ADTs)
 On the set ADT, we might have such operations
as add, remove, size, and contains.
 The C++ class allows for the implementation of
ADTs, with appropriate hiding of implementation
details. Thus, any other part of the program that
needs to perform an operation on the ADT can do
so by calling the appropriate method.
 Implementation details of ADT operations are
easily changeable.
Abstract Data Types (ADTs)
 There is no rule telling us which operations must
be supported for each ADT; this is a design
decision.
 Error handling and tie breaking (where
appropriate) are also generally up to the program
designer.
 Common examples include list, stack, sets,
queue, etc.
Arrays
 Elementary data structure that exists as built-in
in most programming languages.
 Array declaration: int x[6];
 An array is collection of cell of the same type.
 The collection has the name ‘x’.
 The cells are numbered with consecutive
integers.
Array Layout
 Array cells are
contiguous in
computer memory. X [0]

X [1]
 The memory can be
thought of as an array. X [2]

X [3]

X [4]

X [5]
array
What is Array Name?
 ‘x’ is an array name but there is no variable x.
 ‘x’ is not an lvalue.
 For example, if we have the code
 int a, b;
 Then we can write
 b= 2;
 a = b;
 a = 5;

 But we can not write 2 = a;

Array Name
 ‘x’ is not an lvalue.
 int x[6];
 int n;
 x[0] = 5;
 x[1] = 2;

 x = 3; // not allowed
 x = a + b; // not allowed
 x = &n; // not allowed
Dynamic Arrays
 You would like to use an array data structure but
you do not know the size of the array at compile
time.
 You find out when the program executes that you
need an integer array of size n=20.
 Allocate an array using the new operator:
 Int* y =new int[20]; //or int* y=new int[n];
 y[0] = 10;
 y[1] = 15; //use is the same
Dynamic Arrays
 ‘y’ is a lvalue; it is a pointer that holds the
address of 20 consecutive cell in memory.
 It can be assigned a value. The new operator
returns as address that is store in y.
 We can write:
 y = &x[0];
 y = x; //x can appear on the right
//y get the address of the first cell of
the x array
Dynamic Arrays
 We must free the memory we got using the new
operator once we are done with the y array.

delete[]y;

 We would not do this to the x array because we

did not use new to create it.
Material Reference
 Data Structures and Algorithm Analysis in C++
by Mark Allen Weiss
 http://www.amazon.com/Data-Structures-
Algorithm-Analysis-2nd/dp/0201361221