Data Structures & Algorithms
Lecture 01
Manish Aryal
Data Structures and Algorithms
Introduction to Course
Review
Concept of Data Structure
Introduction to Data Structure and its types
Introduction to Algorithm
Introduction to Course
Evaluation Scheme
SN Chapters Hour Marks Distribution*
1 Ch. 1 Concept of Data Structures 2 4
2 Ch. 2 The Stack and Queue 6 10
3 Ch. 3 List 3 6
4 Ch. 4 Linked List 5 10
5 Ch. 5 Recursion 4 8
6 Ch. 6 Trees 7 12
7 Ch. 7 Sorting 5 8
8 Ch. 8 Searching 5 8
9 Ch. 9 Growth Functions 2 4
10 Ch. 10 Graphs 6 10
Total 45 80
Introduction to Course {Contd..}
Objectives
After this course students will be able to:
define and explain various types of data structures
Implement these data structures
gain fundamental knowledge of various
algorithms
analyze these algorithm and explain their
significance
Introduction to Course {Contd..}
Books and References
1. Data Structures using C and C++
- Y. Langsam, M.J. Augenstein A.M. Tenembaum
2. Data Structures and Algorithms in C
- Brijendra Kumar Joshi
3. Data Structures -
Seymour Lipschutz
4. Introduction to Algorithms
- T.H. Cormen et. al.
5. Lecture Notes and Slides
- Manish Aryal
Review
Input Data and Output Data
scanf(), printf(), getchar(), e.t.c.
File Input and Output
FILE *fp;
fp=fopen(“test.txt”,”w”);
fscanf(file ptr, “data type”, &variables);
fprintf(file ptr, “constants+data type”, variables);
fwrite(ptr, size,n, file ptr);
fread(fwrite(ptr, size,n, file ptr);
Review {Contd..}
Conditions Control Statements:
if statements, nested if statements, and switch
statements
Looping Statements:
while loop, do … while loop and for loop
for loop
Functions:
Function Prototype, function Call, function
definition
Review {Contd..}
Operator Precedence (highest to lowest)
Operator Associativity
() Left to right
++ - - Right to left
++ - - ! Unary + Unary – Right to left
(cast) sizeof Right to left
* / % Left to right
+ - Left to right
< <= > >= Left to right
= = != Left to right
&& Left to right
|| Left to right
?: Right to left
= + = -= *= /= Right to left
Review {Contd..}
Arrays
One-dimensional array
DataType ArrayName[ConstIntExpression] ;
Two-dimensional array
DataType ArrayName[ConstIntExpression][ ConstIntExpression] ;
↑ ↑
Rows Columns
Three-dimensional array
DataType ArrayName[ConstIntExpression][ConstIntExpression][ConstIntExpression] ;
↑ ↑ ↑
Pages Rows Columns
Review {Contd..}
Pointers
Variable that stores address
Data type *ptr var
Examples:
short np, *p, **pp, ***ppp; //np is non-pointer vairable
p = &np; //p is pointer variable which has address of np
pp = &p; //pp is pointer variable which has address of p
ppp = &pp; //ppp is pointer variable which has address of pp
↑ ↑ ↑ ↑
ppp pp p np
Review {Contd..}
Structures
Struct Declaration:
struct Str_Name //Define structure name and members
{
DataType MemberName; //Define structure member
DataType MemberName; //Define structure member
StructType MemberName; //Define structure member
.
.
};
Review {Contd..}
Structure Declaration and Access Data Method
Structure Type Structure Delcare Access Method
Variable
Single Structure Variable student record record.Last
Structure Array student record [n] record [i].Last
Structure Pointer student * record record – > Last
Declare Structure typedef struct student * (record + i) – > Last
Pointer Type student_ptr; *(record + i ).Last
student_ptr record;
Review {Contd..}
Pseudocodes
Pseudocode = English + Code
relaxed syntax that extended version of the
is easy to read basic control structures
(sequential, conditional, iterative)
13
Review {Contd..}
Pseudocodes
Algorithm Header
Algorithm Body
14
Review {Contd..}
Pseudocodes
Algorithm Header:
Name
Parameters and their types
Purpose
▪ what the algorithm does
Precondition
▪ precursor requirements for the parameters
Postcondition
▪ taken action and status of the parameters
Return condition
▪ returned value 15
Review {Contd..}
Pseudocodes
Algorithm Body:
Statements
Statement numbers
▪ decimal notation to express levels
Variables
▪ important data
Algorithm analysis
▪ comments to explain salient points
Statement constructs
▪ sequence, selection, iteration 16
Review {Contd..}
Pseudocode Example
Algorithm average
Pre nothing
Post numbers read and their average printed
1 i=0
2 loop (all data not read)
1 i=i+1
2 read number
3 sum = sum + number
3 average = sum / i
4 print average
5 return
End average
17
Data Structure
Definition
Data may be organized in many different ways
The logical or mathematical model of particular organization of
data is called as a Data Structure
In other words, a Data Structure may be defined as a way of
organizing a collection of Data
Some of the types of data structure are:
Array
List/Linked List
Stack/Queue
Tree
HashMap
The same collection of data may be represented by several data
structures so there is a choice
Data Structure {Contd..}
Definition
Different names are used for representing the
elements of a data structure
Some commonly used terms are:
data elements, data item, item aggregate, record,
node, data object
We will be using record when discussing files and
the term node when discussing linked lists, trees
and graphs
Data Structure {Contd..}
Different Representations
t y p e s
t y p e s
t
p y
e s
Data: types
Data Structure {Contd..}
Operations
Data appearing in our data structures are
processed by means of certain operations
The particular data structure that one chooses for
a given situation depends largely on the
frequency with which specific operations are
performed
Data Structure {Contd..}
Operations
Following four operations play major role
Traversing: accessing each record exactly once so that
certain items in the data structure is processed
Searching: finding the location of the record with a
given key value, or finding the location of all records
which satisfy one or more condition
Inserting: adding a new record to the data structure
Deleting: removing a record from the data structure
Data Structure {Contd..}
Operations
Some times two or more operations may be used in
given situation
Example: we may want to delete the record which
may mean we first need to search the location of
the record
Following two operations, which are used in special
situations, will also be considered:
Sorting: arranging records in some logical order
Merging: combining the records in two different data
structures
Algorithm
Necessity
Recipe
Flat pack furniture
Music score
Knitting pattern
What are the common features of these?
Algorithm {Contd..}
Definition
Solution to a problem
Systematic instructions on a task
Step-wise form
Makes use of sequence, selection,
iteration, recursion
Language and details agent specific
Algorithm {Contd..}
Definition
Step-by-step procedure used to solve a
problem
These steps should be capable of being
performed by a machine
Must eventually stop and so produce an
answer
Algorithm {Contd..}
Different Algorithms for Same Problem
Devise an algorithm to find the solution to a number raised
to a positive power
eg 45 or 10 3 ie number power
1 set answer to 1
Notice the
2 Loop 1 to power times
layout and
2.1 answer becomes answer * number numbering
3 report answer
Algorithm {Contd..}
Different Algorithms for Same Problem
25 34
1 Set answer to 1
1 Set answer to 1
2 Loop for 1 to 5 times 2 Loop for 1 to 4 times
2.1 answer becomes answer * 2 2.1 answer becomes answer * 3
3 Report answer 3 Report answer
Answer Loop
Answer Loop
1 1
1 1
2 2
3 2
4 3
8 4
9 3
16 5 27 4
32 ? 81 ?
Algorithm {Contd..}
Different Algorithms for Same Problem
Devise an algorithm to find the solution to a number raised
to a positive power
eg 45 or 10 3 ie number power
45 = 4 2 * 4 2 * 4 1
= 16 * 16 * 4
= 1024
Algorithm {Contd..}
Different Algorithms for Same Problem
1 Set answer to 1, num to number, value to power
2 Loop while value is positive
2.1 if value is odd then multiply answer by num
2.2 divide value by 2 ignore remainder, multiply num by itself
3 Report answer
25 34
answer num value answer num value
1 2 5 1 3 4
2 4 2 1 9 2
2 16 1 1 81 1
32 0 81 0
Algorithm {Contd..}
Searching algorithms
Linear search: unsorted array
Linear search: sorted array
Binary search: sorted array
Reading Assignment
Aaron M. Tenenbaum: Chapter 1 and 2
Next Lecture:
Chapter 2: Stack and Queues
Thank You.
