Data Structures (CS 21001)

KALINGA INSTITUTE OF INDUSTRIAL

TECHNOLOGY

School of Computer Engineering

Strictly for internal circulation (within KIIT) and reference only. Not for outside circulation without permission

4 Credit Lecture Note

Importance of the Course
2

 Data Structures is the foundation of computer programming.

 Almost every computer program, even a simple one, uses data structures
and algorithms. Example -
 Program – To print student list
 Data Structure – Array
Algorithm - Loop

 Algorithm thinking, problem solving and data structures are the vital for
the software engineers. How ?
 Solve the problem more efficiently
 Use right tool to solve the problem
 Run program more efficiently
 The interviewer test and evaluate the candidates performance using
data structures and algorithm.

School of Computer Engineering

Course Description
3

 Provide solid foundations in basic concepts of problem solving – both data

structures and algorithms
 Select and design data structures & algorithms that are appropriate for the
given problems
 Demonstrate the correctness of the algorithm and analyzing their
computational complexities
How?

Blend of Theory and Practical

Prerequisites

 Programming in C
 Mathematics for Computer Science

School of Computer Engineering

Course Contents
4

Sr # Major and Detailed Coverage Area Hrs

1 Introduction 12
Development of Algorithms, Notations and analysis, Storage structures for arrays, Sparse matrices, Stacks and Queues:
Representations and applications.
2 Linked List, Stacks, and Queues 20
Linked Lists, Linked stacks and queues, Operations on polynomials, Doubly linked lists, Circularly linked lists, Dynamic
storage management, Garbage collection and compaction.

Mid Semester
3 Trees 10
Tree representation, Binary Trees, Binary search trees, Tree traversal, Expression manipulation, Symbol table
construction, Height balanced trees, AVL trees.
4 Graph 5
Graphs, Representation of graphs, BFS, DFS, Topological sort, String representation and manipulations, Pattern
matching.
5 Sorting and Searching 8
Sorting Techniques: Selection, Bubble, Insertion, Merge, Heap, Quick, Radix sort, Linear search, Binary search, Hash table
methods.

End Semester

School of Computer Engineering

Course Contents continue…
5

Textbook
 Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed, "Fundamentals of Data
Structures in C", Second Edition, University Press.
Reference Books
 J. P. Tremblay, P. G. Sorenson, “An Introduction to Data Structures with Applications”,
Second Edition, Tata McGraw Hill, 1981.
 M. Tenenbaum, Augestien, “Data Structures using C”, Third Edition, Pearson
Education, 2007.
 Mark Allen Weiss, “Data Structures and Algorithm Analysis in C”, Second Edition,
Addison-Wesley Educational Publishers, 2006.

School of Computer Engineering

Course Outcome
6

By the end of this course, you will be able to

 Remember the concept of data structure and choose appropriate data
structures to represent data items for real world problems.
 Understand the time and space complexity, string representation and
manipulations, and pattern matching.
 Understand the data structures such as arrays, linked lists, stacks and
queues, dynamic storage management, garbage collection and compaction
to develop solution for real-world scenarios.
 Understand non-linear data structures such as trees and graph to develop
solution for real world scenarios.
 Apply algorithms for solving problems like sorting, searching, hashing and
symbol table.
 Analyze the data structure that efficiently models the solution to a
problem.

School of Computer Engineering

Evaluation
7

Grading:

 Internal assessment – 30 marks

 1 class note = 5 marks

 2 quizzes & each worth 5 marks = 10 marks

 2 group assignments and each worth 5 marks = 10 marks

 1 class participation = 5 marks

 Midterm exam - 20 marks

 Endterm exam - 50 marks

?
School of Computer Engineering
Abstract Data Type
8

 Abstract Data Type, abbreviated ADT, is a logical description of how to view the data
and the operations that are allowed without regard to how they will be implemented or
how it does the job. This means it is like a black box where users can only see the
syntax and semantics of operation and hides the inner structure and design of the data
type.
 The definition of ADT only mentions what operations are to be performed but not how
these operations will be implemented. It does not specify how data will be organized in
memory and what algorithms will be used for implementing the operations. It is called
“abstract” because it gives an implementation independent view.
 An ADT consists of 2 parts: (1) declaration of data, (2) declaration of operations
 Commonly used ADTs: Arrays, List, Stack, Queues, Trees, Graphs etc along with their
operations.

School of Computer Engineering

Stack ADT
9

A stack contains elements of same type arranged in sequential order. All

operations takes place at a single end that is top of the stack.
Declaration:
#define size 10
int stack[size]
int top = -1
Operations :
 push() – Insert an element at one end of the stack called top.
 pop() – Remove and return the element at the top of the stack, if it is not
empty.
 peek() – Return the element at the top of the stack without removing it, if
the stack is not empty.
 size() – Return the number of elements in the stack.
 isEmpty() – Return true if the stack is empty, otherwise return false.
 isFull() – Return true if the stack is full, otherwise return false.

School of Computer Engineering

Data Structure
10

It is basically a group of data elements that are put together under one name and
defines a particular way of storing and organizing data in a computer so that it
can be used efficiently.

The implementation of ADT, often referred to as a data structure.

For example, cricket player's name "Virat" & age 28. "Virat" is of string data type
and 28 is of integer data type. This data can be organized as a record like Player
record. Now players record can be collected and store in a file or database as a
data structure. For example: "Dhoni" 30, "Gambhir" 31, "Sehwag" 33.

School of Computer Engineering

Data Structure Classification
11

Characteristics Description
Linear The data items are assessed in a linear sequence, but it is not compulsory
to store all elements sequentially. Example: Array
Non-Linear The data items are stored/accessed in a non-linear order. Example: Tree,
Graph
Homogeneous All the elements are of same type. Example: Array
Heterogeneous The elements are variety or dissimilar type of data Example: Structures
Static Are those whose sizes and structures associated memory locations are
fixed, at compile time. Example: Array
Dynamic Are those which expands or shrinks depending upon the program need
and its execution. Also, their associated memory locations changes.
Example: Linked List created using pointers

School of Computer Engineering

Need of Data Structure
12

As applications are getting complexed and amount of data is increasing day by

day, there may arise the following problems:
 Processor speed: To handle very large amount of data, high speed
processing is required, but as the data is growing day by day to the billions
of files per entity, processor may fail to deal with that much amount of data.
 Data Search: Consider an inventory size of 1L items in a store, If our
application needs to search for a particular item, it needs to traverse 1L
items every time, results in slowing down the search process.
 Multiple requests: If thousands of users are searching the data
simultaneously on a web server, then there are the chances that a very large
server can be failed during that process
In order to solve the above problems, data structures are used. Data is organized
to form a data structure in such a way that all items are not required to be
searched and required data can be searched instantly.

School of Computer Engineering

Algorithm
13

Let us consider the problem of preparing an omelette. To prepare an omelette,

we follow the steps given below:

1) Get the frying pan.

2) Get the oil.
a. Do we have oil?
i. If yes, put it in the pan.
ii. If no, do we want to buy oil?
1. If yes, then go out and buy.
2. If no, we can terminate.
3) Turn on the stove, etc...
4) …

What we are doing is, for a given problem (preparing an omelette), we are
providing a step-by step procedure for solving it.

School of Computer Engineering

Algorithm
14

It is a self-contained step-by-step set of operations to be performed for

calculation, data processing and/or automated reasoning tasks etc. Algorithm is
not the complete code or program, it is just the core logic(solution) of a problem,
which can be expressed either as an informal high level description as pseudo
code or using a flowchart.

Data
ADT + Structure + Algorithm

Need?

To become a computer scientist and stopping yourself

from monkey coder.
School of Computer Engineering
Algorithm Specification
15

An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In

addition, all algorithms must satisfy the following criteria:

1. Input. There are zero or more quantities that are externally supplied.
2. Output. At least one quantity is produced.
3. Definiteness. Each instruction is clear and unambiguous.
4. Finiteness. If we trace out the instructions of an algorithm, then for all cases, the algorithm
terminates after a finite number of steps.
5. Effectiveness. Every instruction must be basic enough to be carried out, in principle, by a
person using only pencil and paper. It is not enough that each operation be definite as in (3); it
also must be feasible.
Difference between an algorithm & program – program does not have to satisfy the 4th condition.

Describing Algorithm
1. Natural Language – e.g. English, Chinese - Instructions must be definite and effectiveness.
2. Graphics representation – e.g. Flowchart - work well only if the algorithm is small and simple.
3. Pseudo Language -
• Readable
• Instructions must be definite and effectiveness
4. Combining English and C

School of Computer Engineering

Algorithm Specification cont…
16

Describing Algorithm – Natural Language

Problem - Design an algorithm to add two Problem - Design an algorithm to find the
numbers and display result. largest data value of a set of given positive
data values.
Step 1 − START
Step 2 − declare three integers a, b & c Step 1 − START
Step 3 − define values of a & b Step 2 − input NUM
Step 4 − add values of a & b Step 3 – LARGE = NUM
Step 5 − store output of step 4 to c Step 4 − While (NUM >=0)
Step 6 − print c if (NUM > LARGE) then
Step 7 − STOP LARGE = NUM
input NUM
Step 5 – display “Largest Value is:”, LARGE
Step 6 − STOP
Note - Writing step numbers, is optional.

School of Computer Engineering

Algorithm Specification cont…
17

Describing Algorithm – Flowchart

Problem – Write an algorithm to determine a student’s final grade and indicate whether it is passing of failing.
The final grade is calculated as the average of five marks.

Start

Input
M1 to M5

Score = (M1 + M2 + M3 + M4 + M5) / 5

Is Score < 4.0

Print “Fail” Print “Pass”

Stop
School of Computer Engineering
Pseudo Language
18

The Pseudo language is neither an algorithm nor a program. It is an abstract form of a program. It consists of
English like statements which perform the specific operations. It employs programming-like statements to
depict the algorithm and no standard format (language independent) is followed. The statements are carried out
in a order & followings are the commonly used statements.

Statement Purpose General Format

Input Get Information INPUT: Name of variable

e.g. INPUT: user_name
Process Perform an atomic activity Variable  arithmetic expression
e.g. x  2 or x  x + 1 or a  b * c
Decision Choose between different alternatives IF (condition is met) THEN
IF (condition is met) then statement(s)
statement(s) ELSE
ENDIF statements(s)
ENDIF

e.g.
e.g. IF (amount < 100) THEN
IF (amount < 100) THEN interestRate  .06
interestRate  .06 ELSE
ENDIF interest Rate  .10
ENDIF

School of Computer Engineering

Pseudo Language cont…
19

Statement Purpose General Format

Repetition Perform a step multiple times REPEAT WHILE (condition is met)

statement(s) statement(s)
UNTIL (condition is met) ENDWHILE

e.g. e.g.
count  0 count  0
REPEAT WHILE (count < 10)
ADD 1 to count ADD 1 to count
OUTPUT: count OUTPUT: count
UNTIL (count < 10) ENDWHILE
OUTPUT: “The End” OUTPUT: “The End”

Output Display information OUTPUT: Name of variable OUTPUT: message

e.g. OUTPUT: user_name OUTPUT: ‘Credit Limit’ limit

School of Computer Engineering

Pseudo Language Guidelines
20
Guidelines Explanation

Write only one statement per line Each statement in pseudo code should express just one action for the computer. If the task list is properly
drawn, then in most cases each task will correspond to one line of pseudo code.
Task List Pseudo code
Read name, hours worked, rate of pay INPUT: name, hoursWorked, payRate
gross = hours worked * rate of pay gross  hoursWorked * payRate
Write name, hours worked, gross OUTPUT: name, hoursWorked, gross
Capitalize initial keyword In the example above note the words: INPUT and OUTPUT. These are just a few of the keywords to use,
others include: IF, ELSE, REPEAT, WHILE, UNTIL, ENDIF
Indent to show hierarchy Each design structure uses a particular indentation pattern.
 Sequence - Keep statements in sequence all starting in the same column
 Selection - Indent statements that fall inside selection structure, but not the keywords that form the
selection
 Loop - Indent statements that fall inside the loop but not keywords that form the loop
INPUT: name, grossPay, taxes
IF (taxes > 0)
net  grossPay – taxes
ELSE
net  grossPay
ENDIF
OUTPUT: name, net

School of Computer Engineering

Pseudo code Guidelines cont…
21

Guidelines Explanation

End multiline structures INPUT: name, grossPay, taxes

IF (taxes > 0)
net  grossPay – taxes
ELSE
net  grossPay
ENDIF
OUTPUT: name, net

Watch the IF/ELSE/ENDIF as constructed above, the ENDIF is in line with the IF. The same applies for
WHILE/ENDWHILE etc…
Keep statements language Resist the urge to write in whatever language you are most comfortable with, in the long run you will save
independent time. Remember you are describing a logic plan to develop a program, you are not programming!

School of Computer Engineering

Pseudo Language Example
22

1. Problem - Design the pseudo code to add two numbers and display the average.
INPUT: x, y
sum  x + y
average  sum / 2
OUTPUT: ‘Average is:’ average
2. Problem - Design the pseudo code to calculate & display the area of a circle
INPUT: radius
area 3.14 * radius * radius
OUTPUT: ‘Area of the circle is ‘ area
2. Problem - Design the pseudo code to calculate & display the largest among 2 numbers
INPUT: num1, num2
max  num1
IF (num2 > num 1) THEN
max  num2
ENDIF
OUTPUT: ‘Largest among 2 numbers is’ max

School of Computer Engineering

Algorithm Specification cont…
23

Example - Translating a Problem into an Algorithm – Combining English and C

 Problem - Devise a program that sorts a set of n>= 1 integers
 Step I – Concept – looks good but not an algorithm
 From those integers that are currently unsorted, find the smallest and place it next in the sorted list – selection sort
 Step II – An algorithm, written in C and English
for (i= 0; i< n; i++)
{
Examine list[i] to list[n-1] and suppose that the smallest integer is list[min];
Interchange list[i] and list[min];
}
 Optional Step III – Coding – translating the algorithm to C program
void sort(int *a, int n) {
for (i= 0; i< n; i++) {
int j= i;
for (int k= i+1; k< n; k++) {
if (a[k]< a[j]) {
j = k; int temp=a[i]; a[i]=a[j]; a[j]=temp;
}
}
}
}

School of Computer Engineering

Algorithm Specification cont…
24

Translating a Problem into an Algorithm cont… Correctness Proof

 Theorem
 Function sort(a, n) correctly sorts a set of n>= 1 integers. The result
remains in a[0], ..., a[n-1] such that a[0]<= a[1]<=...<=a[n-1].
 Proof
For i= q, following the execution of lines, we have a[q]<= a[r], q< r< =n-1.
For i> q, observing, a[0], ..., a[q] are unchanged.
Hence, increasing i, for i= n-2, we have a[0]<= a[1]<= ...<=a[n-1]

School of Computer Engineering

Recursive Algorithm
25
A recursive algorithm is an algorithm which calls itself. In general, recursive computer
programs require more memory and computation compared with iterative algorithms, but
they are simpler and for many cases a natural way of thinking about the problem. There
are 2 types of recursive functions.
Direct recursion Function Indirect recursion Function
Functions call themselves e.g. function α Functions call other functions that invoke the calling
calls α function again e.g. a function α calls a function β that in
turn calls the original function α.
Example – Example –
int func (int n) int func1(int n)
{ {
if (n <= 1) if (n<=1)
return 1; return 1;
else else
return (func(n-1)+func(n-2)); return func2(n);
} }

int func2(int n)
{
return func1(n);
}

School of Computer Engineering

Recursive Algorithm cont…
26
 When is recursion an appropriate mechanism?
 The problem itself is defined recursively
 Statements: if-else and while can be written recursively
 Art of programming
 Why recursive algorithms ?
 Powerful, express an complex process very clearly
 Properties - A recursive function can go infinite like a loop. To avoid infinite running of
recursive function, there are two properties that a recursive function must have −
 Base criteria − There must be at least one base criteria or condition, such that,
when this condition is met the function stops calling itself recursively.
 Progressive criteria− The recursive calls should progress in such a way that each
time a recursive call is made it comes closer to the base criteria.
 Implementation - Many programming languages implement recursion by means of
stack.

School of Computer Engineering

Recursive Implementation of Fibonacci
27

#include<stdio.h>
void Fibonacci(int); //continuation of program
int main() void Fibonacci(int n)
{ {
int k,n; static long int first=0,second=1,sum;
long int i=0,j=1,f;
if(n>0) Base Criteria
printf("Enter the range of the Fibonacci series: "); {
scanf("%d",&n); sum = first + second;
first = second;
printf("Fibonacci Series: "); second = sum;
printf("%d %d ",0,1); printf("%ld ",sum);
Fibonacci(n); Fibonacci(n-1); Progressive Criteria
return 0; }
} }

School of Computer Engineering

Algorithm Analysis
28

We design an algorithm to get solution of a given problem. A problem can be

solved in more than one ways.

Hence, many solution’s algorithms can be derived for a given problem. Next step
is to analyze those proposed solution algorithms and implement the best
suitable.

School of Computer Engineering

Why the Analysis of Algorithms?
29

To go from city “A” to city “B”, there can be many ways of

accomplishing this: by flight, by bus, by train and also by
bicycle. Depending on the availability and convenience,
we choose the one that suits us. Similarly, in computer
science, multiple algorithms are available for solving the
same problem (for example, a sorting problem has many
algorithms, like insertion sort, selection sort, quick sort
and many more). Algorithm analysis helps us to
determine which algorithm is most efficient in terms of
time and space consumed.

School of Computer Engineering

Goal of the Analysis of Algorithms
30

The goal of the analysis of algorithms is to compare algorithms (or

solutions) mainly in terms of running time but also in terms of
other factors (e.g., memory, developer effort, etc.)
What is Running Time Analysis?
It is the process of determining how processing time increases as
the size of the problem (input size) increases. Input size is the
number of elements in the input, and depending on the problem
type, the input may be of different types. The following are the
common types of inputs.
 Size of an array
 Number of elements in a matrix
 Number of bits in the binary representation of the input

School of Computer Engineering

Algorithm Comparison
31

Efficiency of an algorithm can be analyzed at two different stages, before

implementation and after implementation, as mentioned below −

 A priori analysis − This is theoretical analysis of an algorithm. Efficiency of

algorithm is measured by assuming that all other factors e.g. processor speed,
are constant and have no effect on implementation.

 A posterior analysis − This is empirical analysis (by means of direct and

indirect observation or experience) of an algorithm. The selected algorithm is
implemented using programming language. This is then executed on target
computer machine. In this analysis, actual statistics like running time and space
required and are collected.
Focus

A priori analysis
School of Computer Engineering
Algorithm Complexity
32

Suppose X is an algorithm and n is the size of input data, the time and
space used by the Algorithm X are the two main factors which decide the
efficiency of X.

 Time Factor − The time is measured by counting the number of key

operations such as comparisons in sorting algorithm

 Space Factor − The space is measured by counting the maximum

memory space required by the algorithm.

The complexity of an algorithm f(n) gives the running time and / or

storage space required by the algorithm in terms of n as the size of input
data.
School of Computer Engineering
Space Complexity
33

Space complexity of an algorithm represents the amount of memory space required by the
algorithm in its life cycle. Space required by an algorithm is equal to the sum of the following two
components −

 A fixed part that is a space required to store certain data and variables, that are independent of
the size of the problem. For example simple variables & constant used, program size etc.

 A variable part is a space required by variables, whose size depends on the size of the problem.
For example dynamic memory allocation, recursion stack space etc.

Space complexity SC(P) of any algorithm P is SC(P) = FP + VP (I) where FP is the fixed part and
VP(I) is the variable part of the algorithm which depends on instance characteristic I. Following is a
simple example that tries to explain the concept −

Algorithm: SUM(A, B) 3 variables and data type of each variable is int, So VP(3)
Step 1 - START = 3*2 = 6 bytes (No. of characteristic i.e. I = 3)
Step 2 - C ← A + B + 10 1 constant (i.e. 10) and it is int, so FP = 1*2 = 2 bytes
Step 3 - Stop So - SC(SUM) = FP + VP (3) = 2 + 6 = 8 bytes

School of Computer Engineering

Space Complexity cont…
34

Example 1 Example 2
int sum(int a[], int n)
int square(int a) {
{ int sum = 0, i;
return a*a; for(i = 0; i < n; i++) { sum = sum + a[i];}
} return sum;
In above piece of code, it requires 2 bytes of }
In above piece of code it requires -
memory to store variable 'a' and another 2
• 2*n bytes of memory to store array variable ‘a[]’
bytes of memory is used for return value. • 2 bytes of memory for integer parameter 'n‘
• 4 bytes of memory for local integer variables 'sum'
That means, totally it requires 4 bytes of and 'i' (2 bytes each)
memory to complete its execution. And this • 2 bytes of memory for return value.
4 bytes of memory is fixed for any input
value of 'a'. This space complexity is said to That means, totally it requires '2n+8' bytes of memory to
complete its execution. Here, the amount of memory depends
be Constant Space Complexity.
on the input value of 'n'. This space complexity is said to be
Linear Space Complexity.
If any algorithm requires a fixed amount of
space for all input values then that space If the amount of space required by an algorithm is increased
complexity is said to be Constant Space with the increase of input value, then that space complexity is
Complexity said to be Linear Space Complexity

School of Computer Engineering

Time Complexity
35

Time Complexity of an algorithm represents the amount of time required by the

algorithm to run to completion. Time requirements can be defined as a numerical
function T(n), where T(n) can be measured as number of steps * time taken by
each steps

For example, addition of two n-bit integers takes n steps. Consequently, the total
computational time is T(n) = c*n, where c is the time taken for addition of two bits.
Here, we observe that T(n) grows linearly as input size increases.
Asymptotic analysis
Asymptotic analysis of an algorithm, refers to defining the mathematical
foundation/framing of its run-time performance.

Asymptotic analysis are input bound i.e., if there's no input to the algorithm it is
concluded to work in a constant time. Other than the "input" all other factors are
considered constant.
School of Computer Engineering
Time Complexity cont… Asymptotic analysis
36

Asymptotic analysis refers to computing the running time of any

operation in mathematical units of computation.

For example,
- Running time of one operation is computed as f(n)
- May be for another operation it is computed as g(n2)

Usually, time required by an algorithm falls under three types –

 Worst Case (Usually done)− Upper bound on running time of an

algorithm.
 Average Case (Sometimes done)− Average time required for running
an algorithm.
 Best Case (Bogus) − Lower bound on running time of an algorithm.
School of Computer Engineering
Time Complexity cont… Best, Average and Worst
Case examples
37

Example 1: Travel from Kanyakumari to Srinagar

 Worst Case − You go to Ahemdabad and then you take a east go to
Guhwati and then again take a west and go to Srinagar.
 Average Case − You go normal route highways only to reach there.
 Best Case − Take every short cut possible leave the national
highway if you need to take state highway, district road if you need to
but you have to get to Srinagar with least possible distance
Example 2: Sequential Search for k in an array of n integers

 Best Case − The 1st item of the array equals to k

 Average Case − Match at n/2
 Worst Case − The last position of the array equals to k or
unsuccessful search
School of Computer Engineering
Time Complexity cont… Asymptotic Notations
38

Following are commonly used asymptotic notations used in calculating running

time complexity of an algorithm.
 Ο Notation – “Big Oh” - The Ο(n) is the formal way to express the upper
bound of an algorithm's running time. It measures the worst case time
complexity or longest amount of time an algorithm can possibly take to
complete.

 Ω Notation – “Omega” - The Ω(n) is the formal way to express the lower
bound of an algorithm's running time. It measures the best case time
complexity or best amount of time an algorithm can possibly take to complete.

 θ Notation – “Theta” - The θ(n) is the formal way to express both the lower
bound and upper bound of an algorithm's running time.

School of Computer Engineering

Time Complexity cont… Asymptotic Notations cont…
39

Sr # Algorithm Time Complexity

Best Average Worst
1 Bubble Sort Ω(n) Θ(n2) O(n2)
2 Insertion Sort Ω(n2) Θ(n2) O(n2)
3 Quick Sort Ω(n log n) Θ(n log n) O(n2)
4 Merge Sort Ω(n log n) Θ(n log n) O(n log n)
5 Heap Sort Ω(n log n) Θ(n log n) O(n2)

Time-Space Trade Off

The best algorithm to solve a given problem is one that requires less space in memory and takes less time
to complete its execution. But in practice it is not always possible to achieve both these objectives. As we
know there may be more than one approach to solve a particular problem. One approach may take more
space but takes less time to complete its execution while the other approach may take less space but takes
more time to complete its execution. We may have to sacrifice one at the cost of the other. If space is our
constraint, then we have to choose a program that requires less space at the cost of more execution time.
On the other hand if time is our constraint then we have to choose a program that takes less time to
complete its execution at the cost of more space.

School of Computer Engineering

Algorithm Type
40

Sr # Notation Name
1 O(1) Constant
2 O(log(n)) Logarithmic
3 O(log(n)c) Poly-logarithmic
4 O(n) Linear
5 O(n2) Quadratic
6 O(nc) Polynomial
7 O(cn) Exponential
Note: c is constant

School of Computer Engineering

Time Complexity Rules
41

 Time complexity of a function (or set of statements) is considered as O(1) if it

doesn’t contain loop, recursion and call to any other non-constant time
function. Example:
void swap(int *x, int *y)
Note -
{
Constant Time - algorithm runs in a fixed amount of time,
int temp;
it just means that it isn't proportional to the
temp=*x;
length/size/magnitude of the input. i.e., for any input, it
*x=*y;
can be computed in the same amount of time (even if that
*y=temp;
amount of time is really long).
}
Time complexity of swap function= Total number of simple statements = 4 =
constant = O(1)

School of Computer Engineering

Time Complexity Rules for Loops
42

 A loop or recursion that runs a constant number of times is also considered as

O(1). Example -
int i;
for (i = 1; i <= c; i++) // c is a constant
{
// some O(1) expressions
}
 Time complexity of a loop is considered as O(n) if the loop variables i is
incremented / decremented by a constant amount c. Example -
for (i = 1; i <= n; i = i+c)
{
// some O(1) expressions
}

School of Computer Engineering

Time Complexity Rules for Loops cont…
43

 Time Complexity of a loop is considered as O(log n) if the loop variables i is

multiplied or divided by a constant amount c. Example -
for (i = 1; i <= n; i=i*c) Let us assume that the loop is executing some k times.
At kth step ck = n, and at (k + 1)th step we come out of
{ the loop. Taking logarithm on both sides, gives
// some O(1) expressions log(ck) = log n  k log c = log n  k = log n
}
 Time Complexity of a loop is considered as O(log log n) if the loop variables i
if the loop variables is reduced / increased exponentially by a constant
amount c. Example -
Example 1 Example 2
Here c is a constant greater than 1 //Here fun is sqrt or cuberoot or any other constant root
for (i = 2; i <= n; i=pow(i ++,c)) for (i = n; i > 0; i = fun(i))
{ {
// some O(1) expressions // some O(1) expressions
} }

School of Computer Engineering

Time Complexity Rules for Loops cont…
44

 Time Complexity of a loop is considered as O(√n) if the loop variables i is

multiplied by itself. Example -
for (i = 1; i*i <= n; i++) When i2 is greater than n, the loop will terminate. So,
this means i = O(√n)
{
// some O(1) expressions
}
 Time Complexity of a loop is considered as O(1) if the loop variables i is
encountered with break statement. Example –
for (i = 1; i*i <= n; i++)
{
// some O(1) expressions
break;
}

School of Computer Engineering

Time Complexity Rules for Nested Loops
45

 Time complexity of nested loops is equal to the number of times the innermost
statement is executed that is nothing but the multiplication of outer loop complexity
into inner loop complexity.
Sr # Program Segment Time Complexity Explanation

1 int i, j, k; O(m*n) Outer for m times and inner for n

for (i = 1; i <=m; i ++) If m = n, then O(n2) times, so total m*n times
{
for (j = 1; j <=n; j ++)
{
k=k+1;
}
}
2 int i, j, k; O(n2) Outer loop approx n times and
for (i = n; i >1; i =i-2) inner approx n times, so total n2
{ times.
for (j = 1; j <=n; j=j+3)
{
k=k+1;
}
}

School of Computer Engineering

Time Complexity Rules for Loops cont…
46

Sr # Program Segment Time Complexity Explanation

3 int i, j, k; O(n log n) Outer loop approx log n times, inner

for (i = n; i >1; i =i/2) { loop n times, so total n log n times.
for (j = 1; j <=n; j++) {
k=k+1;
}
}
4 int i, j, k; O((log n)2) Outer loop approx log n times and
for (i = 1; i<=n; i=i*2) { inner loop approx log n times, so total
for (j =n; j>=1; j=j/2) { ((log n)2 times.
k = k +1;
}
}
5 int i, j; O(n log n) The inner loop executes n/i times for
for (i = 1; i<=n; i=i++) { each value of i. Its running time is n *
for (j =1; j <=n; j=j+i) { ∑i=1 to n of n/i = O(n * log n)
// some O(1) expressions
}
}

School of Computer Engineering

Time Complexity Rules for Loops cont…
47

Sr # Program Segment Time Complexity Explanation

6 for (i = 1; i<=n; i++) O(n) The outer loop executes approx. n

{ times, and the innermost 100 times.
for (j =1; j<=100; j++) Here n=O(n) and 100=O(1) constant
{ time. So total = O(n)*O(1) = O(n)
Simple-Statements;
}
}
 When there are consecutive loops, the time complexity is calculated as sum of time
complexities of individual loops and final time complexity is the higher order term in
terms of n (the one which is larger than others for larger value of n)
Sr # Program Segment Time Complexity Explanation

1 for (int i = 1; i <=m; i += c) O(m+n) First for outer i loop O(m), second for
{ If m=n, then inner i loop O(n) times, so total
// some O(1) expressions O(2n)=O(n) O(m+n) times
}
for (int i = 1; i <=n; i += c)
{
// some O(1) expressions
}

School of Computer Engineering

Time Complexity Rules for Loops cont…
48

Sr # Program Segment Time Complexity Explanation

2 for (int i = 1; i <=n; i *= 2) O(n) First for outer i log n times, second inner i it
{ is n times. Now total=log n + n = O(n) as n
// some O(1) expressions is asymptotically larger than log n.
}
for (int i = 1; i <=n; i ++)
{
// some O(1) expressions
}
3 int i, j, k,l; O(n log n) Nested for-ij loop is executed n log
for (i = 1; i <=n; i ++) n times. k loop log n times, l loop
{ n times. So total= n log n + log n + n =
for (j = 1; j <=n; j=j*2) {p=i+j;} O(n log n) as n log n > n > log n
}

for ( k = n; k >=1; k=k/3)

{ q=k+p; }

for ( l = n; l >=1; l=l-2)

{ q=k+p; }

School of Computer Engineering

Time Complexity Rules for Recursion
49

Sr # Program Segment Time Complexity Explanation

1 Factorial of a number O(n) The algorithm is linear, running in O(n) time. This is the case
int Factorial (int n) because it executes once every time it decrements the value
{ n, and it decrements the value n until it reaches 0, meaning
if n >= 1 then the function is called recursively n times Both decrementation
return n * Factorial(n – 1); and multiplication are constant operations..
else
return 1;
}
2 Fibonacci Sequence ?? ??
int Fib(int n)
{
if n == 1 then
return 1;
else
return Fib(n-1) + Fib (n – 2)
}
3 void recursiveFun(int n, int m, int o) O(2n) Each function call calls itself twice unless it has been recursed
{ n times and hence exponential in nature.
if (n <= 0)
{
printf("%d, %d\n",m, o);
}
else
{
recursiveFun(n-1, m+1, o);
recursiveFun(n-1, m, o+1);
}
}

School of Computer Engineering

Time Complexity Class Work
50

Sr # Program Segment Time Complexity Explanation

1 int j=0,i; ?? ??
for (i = 0; i<n ; i++)
{
while (j<n && arr[i] <arr[j])
{
j++;
}
}
2 int i,j; ?? ??
for (i=1;i<=m;i=i*2)
{
for (j=1;j<=i;j++)
{
printf("%d %d ",i,j);
}
}
3 int count = 0,i,j; ?? ??
for (i = n ; i>0; i /= 2)
{
for (j = 0; j<i ; j++)
count += 1;
}

School of Computer Engineering

Space Complexity Rules
51

Sr # Program Segment Space Explanation

Complexity
1 int sum(int x, int y, int z) O(1) requires 3 units of space for the parameters
{ and 1 for the local variable, and this never
int r = x + y + z; changes, so this is O(1).
return r;
}
2 int sum(int a[], int n) { O(n) requires n units for a, plus space for n, r and
int r = 0; i, so it's O(n).
for (int i = 0; i < n; ++i) {
r += a[i];
}
return r;
}
3 void matrixAdd(int a[], int b[], int c[], int n) O(n) requires n units for a, b and c plus space for
{ n, and i, so it's O(n).
for (int i = 0; i < n; ++i)
{
c[i] = a[i] + b[j]
}
}

School of Computer Engineering

Arrays
52

Data Structures are classified as either Linear or Non-Linear.

 Linear data structure: A linear data structure traverses the data elements
sequentially, in which only one data element can directly be reached. Ex: Arrays,
Linked Lists
 Non-Linear data structure: Every data item is attached to several other data items
in a way that is specific for reflecting relationships. The data items are not arranged
in a sequential structure. Ex: Trees, Graphs

Arrays
Array is a container which can hold fix number of items and these items should be of
same type. Following are important terms to understand the concepts of Array. Arrays
are of one-dimensional or multi-dimensional (i.e. 2 or more than 2)
 Element − Each item stored in an array.
 Index − Each location of an element in an array has a numerical index which is used
to identify the element.

School of Computer Engineering

One-Dimensional Array
53

One-Dimensional array is also called as linear array and stores the data in a single row or column.

 Index starts with 0

 Array length/size/range is 10 (i.e. 9 – 0 + 1) which means it can store 10 elements.
 Each element can be accessed via its index. For example, we can fetch element at
index 6 as 27.
 Address (array[6]) = 100 + 2 * (6 – 0) = 112
School of Computer Engineering
1-D Array Address Calculation
54

Array of an element of an array say “A[i]” is calculated using the following formula:
Address of A [i] = BA(A) + w * ( i – LB )
Where,
BA(A) = Base Address of array A
w = Storage Size of one element stored in the array (in byte)
i = Subscript of element whose address is to be found
LB = Lower limit / Lower Bound of subscript, if not specified assume 0 (zero)
Example
Problem: Given the base address of an array B[1300…..1900] as 1020 and size of each
element is 2 bytes in the memory. Find the address of B[1700].
Solution:
The given values are: BA(B) = 1020, LB = 1300, W = 2, i = 1700
Address of B [i] = BA(B) + w * ( i – LB )
= 1020 + 2 * (1700 – 1300)
= 1020 + 2 * 400
= 1020 + 800 = 1820

School of Computer Engineering

Two-Dimensional Array
55

C uses the so-called array-of-arrays representation to represent a multidimensional array. In this

representation, a 2-dimensinal array is represented as a one-dimensional array in which each
element is itself a one-dimensional array. In layman term, it is the collection of elements placed in
rows and columns. For 2-dimensional, 2 types of memory arrangement i.e. Row-Major arrangement
and Column-Major arrangement
Row-Major and Column-Major arrangement
2-D Array

Note : C supports row major order and Fortran supports column major order
School of Computer Engineering
Row major & Column order Address Calculation
56

 Row-Major Order: The address of a location in Row Major System is calculated as:
Address of A [i][j] = BA + w * [ n * ( i – Lr ) + ( j – Lc ) ]
 Column-Major Order: The address of a location in Column Major System is
calculated as:
Address of A [i][j] = BA + w * [( i – Lr ) + m * ( j – Lc )]
Where:
BA = Base Address
i = Row subscript of element whose address is to be found
j = Column subscript of element whose address is to be found
w = Storage Size of one element stored in the array (in byte)
Lr = Lower limit of row/start row index of matrix, if not given assume 0 (zero)
Lc = Lower limit of column/start column index of matrix, if not given assume 0 (zero)
m = Number of row of the given matrix
n = Number of column of the given matrix

School of Computer Engineering

Row major & Column order Address Calculation cont…
57

Important: Usually number of rows and columns of a matrix are given (like A[20][30] or
A[40][60] ) but if it is given as A[Lr- – – – – Ur, Lc- – – – – Uc]. In this case number of rows
and columns are calculated using the following methods:

Number of rows (m) will be calculated as = (Ur – Lr) + 1

Number of columns (n) will be calculated as = (Uc – Lc) + 1

And rest of the process will remain same as per requirement .

Example:
In figure there is 3x3 array and memory location start from 200 and
each element takes 2 address. Calculate element address at Array
[2][1] for both row and column major.

Answer: Here m=n=3, i=2, j=1, w=2, base address=200.

Row-Major = BA + w * [ n * ( i – Lr ) + ( j – Lc ) ] = 200+2(3(2-0) + (1-0)) = ?
Column-Major = BA + w * [( i – Lr ) + m * ( j – Lc )] = 200+2((2-0) + 3*(1-0)) = ?

School of Computer Engineering

Class Work
58

An array X [-15……….10, 15……………40] requires one byte of storage. If beginning location

is 1500 determine the location of X [8][20].
Answer: As you see here the number of rows and columns are not given in the question.
So they are calculated as:
Number or rows say m = (Ur – Lr) + 1 = [10 – (- 15)] +1 = 26
Number or columns say n = (Uc – Lc) + 1 = [40 – 15)] +1 = 26

Row-Major:
The given values are: B = 1500, W = 1 byte, i = 8, j = 20, Lr = -15, Lc = 15, N = 26
Address of A [ i ][ j ] = BA + w * [ n * ( i – Lr ) + ( j – Lc ) ]
= 1500 + 1* [26 * (8 – (-15))) + (20 – 15)]
= 1500 + 1 * [26 * 23 + 5] = 1500 + 1 * [598 + 5] = 1500 + 603 = 2103
Column-Major :
The given values are: BA = 1500, w = 1 byte, i = 8, j = 20, Lr = -15, Lc = 15, m = 26
Address of A [ i ][ j ] = BA + w * [( i – Lr ) + m * ( j – Lc )]
= 1500 + 1* [(8 – (-15)) + 26 * (20 – 15) ]
= 1500 + 1 * [23 + 26 * 5] = 1500 + 1 * [153] = 1653

School of Computer Engineering

Array ADT
59

An abstract data type (ADT) is a mathematical model for data types where a data
type is defined by its behavior (semantics) from the point of view of a user of the
data, specifically in terms of possible values, possible operations on data of this
type, and the behavior of these operations. When considering Array ADT we are
more concerned with the operations that can be performed on array.

Basic Operations Default Value Initialization

 Traversal − print all the array elements one by one. In C, when an array is initialized
 Insertion − add an element at given index. with size, then it assigns following
 Deletion − delete an element at given index. defaults values to its elements
 Search − search an element using given index or by value.  bool − false
 Updation − update an element at given index.  char− 0
 Sorting – arranging the elements in some type of order.  float− 0.0
 Merging – Combining two arrays into a single array  double− 0.0f
 Reversing – Reversing the elements  int− 0

School of Computer Engineering

Basic Operation cont…
60

Insertion Deletion
Insert operation is to insert one or more data elements Deletion refers to removing an existing element from
into an array. Based on the requirement, new element the array and re-organizing all elements of an array.
can be added at the beginning or end or any given
position of array. Consider LA is a linear array with N elements and K is
a positive integer such that K<=N. Below is the
Let LA is a filled linear array (unordered) with N elements algorithm to delete an element available at the Kth
and K is a positive integer such that K<=N. Below is the position of LA. Procedure - DELETE(LA, N, K)
algorithm where ITEM is inserted into the Kth position of
LA. Procedure – INSERT(LA, N, K, ITEM) 1. Start
2. Set J = K
1. Start
3. Repeat step 4 while J < N
2. Set J=N
4. Set LA[J] = LA[J+1] /* Move the element upward*/
3. Set N = N+1 /* Increase the array length by 1*/
5. Set N = N-1 /* Reduce the array length by 1 */
4. Repeat steps 5 and 6 while J >= K
6. Stop
5. Set LA[J+1] = LA[J] /* Move the element downward*/
6. Set J = J-1 /* Decrease counter*/
7. Set LA[K] = ITEM
8. Stop

School of Computer Engineering

Basic Operation cont…
61

Search Updation
You can perform a search for array element Update operation refers to updating an existing
based on its value or position. element from the array at a given position.

Consider LA is a linear array with N elements. Consider LA is a linear array with N elements
Below is the algorithm to find an element with a and K is a positive integer such that K<=N.
value of ITEM using sequential search. Below is the algorithm to update an ITEM
Procedure - SEARCH(LA, N, ITEM) available at the Kth position of LA. Procedure -
UPDATE(LA, N, K, ITEM)
1. Start
2. Set J=1 and LOC = 0 1. Start
3. Repeat steps 4 and 5 while J < N
2. Set LA[K] = ITEM
4. IF (LA[J] = ITEM) THEN LOC = J AND GOTO STEP 6
3. Stop
5. Set J = J +1
6. IF (LOC > 0) PRINT J, ITEM ELSE PRINT ‘Item not
found’
7. Stop

School of Computer Engineering

Basic Operation cont…
62

Traversal Sorting
Traversal operation refers to printing the Sorting operation refers to arranging the elements
contents of each element or to count the number either in ascending or descending way.
of elements with a given property
Consider LA is a linear array with N elements. Below
Consider LA is a linear array with N elements. is the Bubble Sort algorithm to sort the elements
in ascending order. Procedure - SORT(LA, N)
Below is the algorithm to print each element.
Procedure - TRAVERSE(LA, N)
1. Start
2. Set I = 1
1. Start 3. Set J = 1
4. Repeat steps 5 to 11 while I ≤ N
2. Set J=1
5. J = 1
3. Repeat steps 4 and 5 while J ≤ N 6. Repeat steps 7 to 10 while J ≤ N - I
4. PRINT LA[J] 7. IF LA[I] is > LA[J] THEN
8. Set TEMP = LA[I]; LA[I] = LA[J]; LA[J] = TEMP;
5. Set J = J +1
9. END IF
6. Stop 10. Set J = J+1
11. Set I = I+1
12. Stop
School of Computer Engineering
Basic Operation cont…
63

Merging – Home Assignment 1 Reversing – Home Assignment 2

Merging refers to combining two sorted arrays Reversing refers to reversing the elements in the
into one sorted array. It involves 2 steps – array by swapping the elements. Swapping should
 Sorting the arrays that are to be merged be done only half times of the array size
 Adding the sorted elements of both arrays to
a new array in sorted order Consider LA is a linear array with N elements.
Write the algorithm to reverse the elements and
print each element of LA
LA1 is a linear array with N elements, LA2 is a
liner array with M elements and LA3 is a liner
1. Start
array with M+N elements. Write the algorithm
/* Home Assignment 2 */
to sort LA1 & LA2 and merge LA1 & LA2 into 2. Stop
LA3 & sort LA3 and print each element of LA3

1. Start
/* Home Assignment1 */
2. Stop

School of Computer Engineering

Home Assignments
64

Home Assignment 3 Home Assignment 4

LA is a linear array with N elements. Write the LA is a linear array with N elements. Write the
algorithm to finds the largest number and algorithm to copy the elements from LA to a
counts the occurrence of the largest number new array LB

1. Start 1. Start
/* Home Assignment 3 steps */ /* Home Assignment 4 steps*/
2. Stop 2. Stop

Home Assignment 5 Home Assignment 6

LA is a linear array with N elements. Write the LA is a linear sorted array with N elements.
algorithm to transpose the array Write the algorithm to insert ITEM to the array

1. Start 1. Start
/* Home Assignment 5 steps */ /* Home Assignment 6 steps */
2. Stop 2. Stop

School of Computer Engineering

Polynomials
65

Polynomial is an expression constructed from one or more variables and constants, using only the
operations of addition, subtraction, multiplication, and constant positive whole number exponents.
A term is made up of coefficient and exponent.

Examples –
 Polynomial with single variable P(X) = 4X3 + 6X2+7X+9 (4,6,7 are coefficient & 3,2 are exponent)
 Polynomial with 2 variables P(X, Y) = X3 - 2XY +1 (2 is coefficient & 3 is exponent)

Definition–
 Polynomial with single variable P(X) =

A polynomial thus may be represented using arrays. Array representation assumes that the exponents of the
given expression are arranged from 0 to the highest value (degree), which is represented by the subscript of the
array beginning with 0. The coefficients of the respective exponent are placed at an appropriate index in the
array. Considering single variable polynomial expression, array representation is

School of Computer Engineering

Polynomial Addition
66

Consider LA is a linear array with N elements and LB is a linear array with M elements.
Below is the algorithm for polynomial addition
1. Start
2. Set j= maximum of M or N
3. Create a sum array LSum[] of size J
4. IF (N is Greater Than or Equal to M) Then
Copy LA[] to LSum[]
else
Copy LB[] to LSum[]
5. IF (N is Greater Than M) then
Traverse array LB[] and LSum[i] = LSum[i] + LB[i]
else
Traverse array LA[] and LSum[i] = LSum[i] + LA[i] while i < j
6. PRINT LSum
7. Stop

School of Computer Engineering

Polynomial Multiplication
67

Given two polynomials represented by two arrays, below is the illustration of the
multiplication of the given two polynomials.
Example :
Input: A[] = {5, 0, 10, 6} and B[] = {1, 2, 4}
Output: prod[] = {5, 10, 30, 26, 52, 24}
The first input array represents "5 + 0x1 + 10x2 + 6x3"
The second array represents "1 + 2x1 + 4x2"
And output is "5 + 10x1 + 30x2 + 26x3 + 52x4 + 24x5”
5 0 10 6 Coefficents 1 2 4 0 Coefficents
A B
0 1 2 3 Exponents 0 2 2 3 Exponents

AXB

5 10 30 26 52 24 Coefficents
Prod
0 2 2 3 4 5 Exponents

School of Computer Engineering

Polynomial Multiplication cont…
68

Algorithm:
prod[0.. m+n-1] Multiply (A[0..m-1], B[0..n-1])
1. Start
2. Create a product array prod[] of size m+n-1.
3. Initialize all entries in prod[] as 0.
4. Travers array A[] and do following for every element A[i]
Traverse array B[] and do following for every element B[j]
prod[i+j] = prod[i+j] + A[i] * B[j]
5. return prod[]
6. Stop
Home Assignment

Given three polynomials represented by arrays, write an algorithm to multiply

those

School of Computer Engineering

Matrix Addition
69

Suppose A and B are two matrix arrays of order m x n, and C is another

matrix array to store the addition result. i, j are counters.
Step 1: Start
Step 2: Read: m and n
Step 3: Read: Take inputs for Matrix A[1:m, 1:n] and Matrix B[1:m, 1:n]
Step 4: Repeat for i := 1 to m by 1:
Repeat for j := 1 to n by 1:
C[i, j] := A[i, j] + B[i, j]
[End of inner for loop]
[End of outer for loop]
Step 5: Print: Matrix C
Step 6: Stop

School of Computer Engineering

Matrix Multiplication
70

Suppose A and B are two matrices and their order are respectively m x n and p x q. i, j and k are counters. And C to
store result.
Step 1: Start.
Step 2: Read: m, n, p and q
Step 3: Read: Inputs for Matrices A[1:m, 1:n] and B[1:p, 1:q].
Step 4: If n ≠ p then:
Print: Multiplication is not possible.
Else:
Repeat for i := 1 to m by 1:
Repeat for j := 1 to q by 1:
C[i, j] := 0 [Initializing]
Repeat k := 1 to n by 1
C[i, j] := C[i, j] + A[i, k] x B[k, j]
[End of for loop]
[End of for loop]
[End of for loop]
[End of If structure]
Step 5: Print: C[1:m, 1:q]
Step 6: Stop

School of Computer Engineering

Sparse Matrix
71

A sparse matrix is a two-dimensional array in which

most of the elements are zero or null. It is a wastage of
memory and processing time if we store null values or 0
of the matrix in an array. For example, consider a matrix
of size 100 X 100 containing only 10 non-zero elements.
In this matrix, only 10 spaces are filled with non-zero
values and remaining spaces of matrix are filled with 0. To avoid such
circumstances
That means, totally we allocate 100 X 100 X 2 = 20000
different
bytes of space to store this integer matrix and to access techniques such
these 10 non-zero elements we have to make scanning as linked list or
for 10000 times. triplet are used
Linked List Representation will be covered later
School of Computer Engineering
Sparse Matrix Triplet Representation
72

In this representation, only non-zero values are considered along with their row and column index
values. In this representation, the 0th row stores total rows, total columns and total non-zero values
in the matrix. For example, consider a matrix of size 5 X 6 containing 6 number of non-zero values.
This matrix can be represented as shown in the image...
2 D Array Row Representation
2D array is used to represent a sparse matrix in which there are three
columns named as
• Rows: Index of row, where non-zero element is located
• Columns: Index of column, where non-zero element is located.
• Values: Value of the non zero element located at index – (row,
column)
In above example matrix, there are 6 non-zero elements ( those are 9, 8, 4, 2, 5 & 2) and matrix size is 5 X 6. We
represent this matrix as shown in the above image. The first row is filled with values 5, 6 & 6 which indicates that
it is a sparse matrix with 5 rows, 6 columns & 6 non-zero values. Second row is filled with 0, 4, & 9 which
indicates the value in the matrix at 0th row, 4th column is 9. In the same way the remaining non-zero values also
follows the similar pattern.

School of Computer Engineering

Sparse Matrix Triplet Representation
73

2 D Array Columnar Representation

Rows 5 0 1 2 2 3 4
Columns 6 4 1 0 2 5 2
Values 6 9 8 4 2 5 2

2D array is used to represent a sparse matrix in which there are three rows named as
• Rows: Index of row, where non-zero element is located
• Columns: Index of column, where non-zero element is located.
• Values: Value of the non zero element located at index – (row, column)

In above example matrix, there are 6 non-zero elements ( those are 9, 8, 4, 2, 5 & 2) and matrix size
is 5 X 6. We represent this matrix as shown in the above image. The first column is filled with
values 5, 6 & 6 which indicates that it is a sparse matrix with 5 rows, 6 columns & 6 non-zero
values. Second column is filled with 0, 4, & 9 which indicates the value in the matrix at 0th row, 4th
column is 9. In the same way the remaining non-zero values also follows the similar pattern.

School of Computer Engineering

Sparse Matrix Triplet Representation – C Code
74
// Assume 4x5 matrix //Calculating number of non-zero entries
int matrix[4][5] = int size = 0;
{ for (int i = 0; i < 4; i++)
{0 , 0 , 3 , 0 , 4 }, {0 , 0 , 5 , 7 , 0 }, {0 , 0 , 0 , 0 , 0 }, {0 , 2 , 6 , 0 , 0 } for (int j = 0; j < 5; j++)
}; if (matrix[i][j] != 0) {size++; }

2 D Array Row Representation 2 D Array Columnar Representation

// number of rows = size+1 and columns = 3 // number of rows = 3 and columns = = size+1
int sparseMatrix[size+1][3]; int sparseMatrix[3][size+1];
// Making of new matrix // Making of new matrix
int k = 1; int k = 1;
sparseMatrix[0][0] = 4; //filling no. or rows sparseMatrix[0][0] = 4; //filling no. or rows
sparseMatrix[0][1] = 5; //filling no. or columns sparseMatrix[1][0] = 5; //filling no. or columns
sparseMatrix[0][2] = size //filling no. of non-zero values sparseMatrix[2][0] = size //filling no. of non-zero values
for (i = 0; i < 4; i++) for (i = 0; i < 4; i++)
for (j = 0; j < 5; j++) for (j = 0; j < 5; j++)
if (matrix[i][j] != 0) { if (matrix[i][j] != 0) {
sparseMatrix[k][0] = i; sparseMatrix[0][k] = i;
sparseMatrix[k][1] = j; sparseMatrix[1][k] = j;
sparseMatrix[k][2] = matrix[i][j]; sparseMatrix[2][k] = sparseMatrix[i][j];
k++; k++;
} }
School of Computer Engineering
Sparse Matrix cont…
75

N-square sparse matrices is called

triangular matrix. A square matrix is
called lower triangular if all the entries
above the main diagonal are zero.
Similarly, a square matrix is called upper
triangular if all the entries below the
main diagonal are zero.
Matrix where nonzero entries can only occur on the
diagonal or on elements immediately above or below
the diagonal is called a tridiagonal matrix

School of Computer Engineering

Class Work
76

Design an efficient data structure to represent

 Lower Triangular matrix
 Upper Triangular matrix
 Tri-diagonal matrix
Solution
 1 two dimensional array
 3 one dimensional array
 1 one dimensional array of type struct

School of Computer Engineering

String Representation
77

 Strings are defined as an array of characters. The difference between a

character array and a string is the string is terminated with a null character
‘\0’. char array string
M A M M A M \0
 In C, a string can be referred to either using a character pointer or as a
character array.
 When strings are declared as character arrays, they are stored like other types
of arrays . e.g., char str[4] = “mam”;
 Pointer to string in C can be used to point to the starting address of the array,
the first character in the array. These pointers can be dereferenced using the
asterisk * operator to identify the character stored at the location.

char str[4] = “MAM”; Address 8000 100 101 102 103 Address
char *ptr = str; Value Value
100 M A M \0
ptr

School of Computer Engineering

String Manipulation
78

String manipulation basically refers to the process of handling and analyzing

strings. It involves various operations concerned with modification and parsing of
strings to use and change its data.
Concatenation of Strings: The process of combining more than one string
together is known as concatenation. String concatenation is the technique of
combining two strings. Below is the algorithm for the concatenation of two
strings:
VOID CONCATENATE (STR1, STR2, STR3)
1. LEN1 = LENGTH(STR1) 7. SET J = 0.
2. LEN2 = LENGTH(STR2) 8. Repeat Steps 9 to 11 WHILE I <
(LEN1 + LEN2 - 2):
3. SET I = 0
9. STR3[I] = STR2[J].
4. Repeat Steps 5 and 6 while I < LEN1-1: 10. J = J+1.
5. STR3[I] = STR1[I] 11. I = I+1.
6. SET I = I+1 12. EXIT
School of Computer Engineering
String Manipulation cont’d
79

INT LENGTH(STR1)
1. SET LEN = 0 AND I = 0.
2. Repeat Steps 3 to 4 while STRING[I] IS NOT NULL
3. LEN = LEN + 1
4. SET I = I + 1
5. EXIT
Home Work
 Check whether a string is binary string. A binary string is a special kind of
string made up of only two types of characters, such as 0 and 1. For example:

Input: str = "01010101010"

Output: Yes, it is a binary string

Input: str = “CS 07"

Output: No, it is not a binary string
School of Computer Engineering
String Manipulation Home Work
80

 Develop an algorithm to check whether a string is palindrome. A

string is said to be a palindrome if the reverse of the string is the
same as the string.
 Develop an algorithm to find a character in string.
 Develop an algorithm to find a substring in another string.
 Develop an algorithm to trim the string. Below is a simple solution:
Iterate through all characters of given string, do following:
If current character is a space, then move all subsequent
characters one position back and decrease length of the result
string.
 Develop an algorithm to reverse a string. The reversing of a string is
nothing but simply substituting the last element of a string to the
1st position of the string.
 Develop an algorithm to convert a string to lower and upper case.
School of Computer Engineering
Pattern Matching
81

Pattern matching is searching a given pattern in the string.

Pattern found at?

School of Computer Engineering
Pattern Matching Algorithm
82

for (c = 0; c <= text_length - pattern_length; c++)

int match(char text[], char pattern[]) {
{ position = e = c;
int c, d, e, text_length, pattern_length, position = -1;
for (d = 0; d < pattern_length; d++)
text_length = strlen(text); {
pattern_length = strlen(pattern); if (pattern[d] == text[e])
{
if (pattern_length > text_length) e++;
{ }
return -1; else
} {
break;
} }
}
if (d == pattern_length)
{
What is the drawback in the algorithm? return position;
}
}
return -1;

School of Computer Engineering

83

School of Computer Engineering

Home Assignments
84

1. Find the time complexity of the following code segment

 for (i = 1; i <= n; i = i*2)
{
for (j = n; j >= 1; j = j/2) { some statement }
}
 for (j = c; j > 0; j--) // consider c as const
{
some statement
}
 for (i = n; i >= 1; i = i/c) // consider c as const
{
// some statement
}
2. Write an recursive algorithm to print from 1 to n (where n > 1)
3. Write an recursive algorithm to find the kth smallest element of a set S
4. Write an recursive algorithm to sum the list of numbers
School of Computer Engineering
Home Assignments cont…
85

5. Find the space complexity of the following code segment

int Factorial (int n)
{
if n == 0 then
return 0;
else
return n * Factorial(n – 1);
}
6. Find the time and space complexity of the following code segment
int Fib(int n)
{
if n <= 1 then
return 1;
else
return Fib(n-1) + Fib (n – 2);
}
School of Computer Engineering
Home Assignments cont…
86

7. Find the space complexity of the following code segment

void fun()
{
int i=1, j=1;
for (; i<=n; i++)
for (; j<=log(i); j++)
printf("KIIT");
}
8. What is the time, space complexity of following code:
int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
School of Computer Engineering
Home Assignments cont…
87

9. What are the operations can be performed on various data structure?

10. What are the advantages of using ADT?
11. Explain Top-Down and Bottom-Up approach in designing the algorithm
12. Explain little o and little omega (w) notation.
13. In how many ways can you categorize data structures? Explain each of them.
14. What do you understand by time–space trade-off?
15. Explain the criteria that you will keep in mind while choosing an
appropriate algorithm to solve a particular problem.
16. Write best case, worst case and average case time complexity of following
categories of algorithm –
• Constant time
• Linear time
• Logarithmic time
• Polynomial time
• Exponential time

School of Computer Engineering

Home Assignments cont…
88

17. Discuss the significance and limitations of the Big O notation.

18. Design an algorithm whose worst case time complexity is O(m + n log n)
19. Design an algorithm whose worst case time complexity is O(m + n2 log m)
20. Design an algorithm whose worst case time complexity is O(m2+ n (log m)2)
21. Write an algorithm to find whether an array is subset of another array
22. Write an algorithm to remove repeated elements in a given array.
23. Write down the algorithm to find the k’th smallest and largest element in
unsorted array
24. Write an algorithm to find the number of occurrence of kth element in an
integer array.
25. Write an algorithm to replace every array element by multiplication of
previous and next
26. Consider the static array growing from both ends. Write the underflow and
overflow condition for insertion and deletion from the perspective of both
ends.

School of Computer Engineering

Home Assignments cont…
89

27. Write an algorithm that takes as input the size of the array and the elements
in the array and a particular index and prints the element at that index.
28. Write down the algorithm to sort elements by their frequency.
29. Write down the algorithm to add two polynomials of single variable.
30. Write down the algorithm to multiply two polynomials of two variables.
31. A program P reads in 500 random integers in the range [0..100] presenting
the scores of 500 students. It then prints the frequency of each score above
50. What would be the best way for P to store the frequencies?
32. Write down the algorithm to delete all the vowels in a character array.
33. Write down the algorithm to print all the elements below the minor diagonal
in a 2-D array.
34. Write an algorithm to find a triplet that sum to a given value
35. Given an array arr, write an algorithm to find the maximum j – i such that
arr[j] > arr[i]
36. Write an algorithm to replace every element in the array with the next
greatest element present in the same array.
School of Computer Engineering
Supplementary Reading
90

 Watch the following video

 https://www.youtube.com/watch?v=8syQKTdgdzc
 https://www.youtube.com/watch?v=AL7yO-I5kFU
 http://nptel.ac.in/courses/106102064/1
 https://www.tutorialspoint.com/data_structures_algorithms/array_data_str
ucture.htm
 http://www.geeksforgeeks.org/array-data-structure/
 https://www.hackerrank.com/domains/data-structures/arrays
 http://javarevisited.blogspot.in/2015/06/top-20-array-interview-
questions-and-answers.html#axzz4myAupUvT
 https://www.youtube.com/playlist?list=PLqM7alHXFySEQDk2MDfbwEdjd2
svVJH9p
 https://www.tutorialspoint.com/data_structures_algorithms/

School of Computer Engineering

FAQ
91

 What is Information - If we arrange some data in an appropriate sequence,

then it forms a Structure and gives us a meaning. This meaning is called
Information . The basic unit of Information in Computer Science is a bit,
Binary Digit. So, we found two things in Information: One is Data and the
other is Structure.
 What is Data Structure?
1. A data structure is a systematic way of organizing and accessing data.
2. A data structure tries to structure data!
 Usually more than one piece of data
 Should define legal operations on the data
 The data might be grouped together (e.g. in an linked list)
3. When we define a data structure we are in fact creating a new data type
of our own.
 i.e. using predefined types or previously user defined types.
 Such new types are then used to reference variables type within a
program
School of Computer Engineering
FAQ cont…
92

 Why Data Structures?

1. Data structures study how data are stored in a computer so that
operations can be implemented efficiently
2. Data structures are especially important when you have a large amount of
information
3. Conceptual and concrete ways to organize data for efficient storage and
manipulation.
 ADT
1. Abstract Data Types (ADT's) are a model used to understand the design of
a data structure
2. 'Abstract' implies that we give an implementation-independent view of the
data structure
3. ADTs specify the type of data stored and the operations that support the
data
4. Viewing a data structure as an ADT allows a programmer to focus on an
idealized model of the data and its operations
School of Computer Engineering
FAQ cont…
93

 Time Complexity of algorithm - Time complexity of an algorithm signifies

the total time required by the program to run till its completion. The time
complexity of algorithms is most commonly expressed using the big O
notation. Time Complexity is most commonly estimated by counting the
number of elementary functions performed by the algorithm. And since the
algorithm's performance may vary with different types of input data, hence
for an algorithm we usually use the worst-case Time complexity of an
algorithm because that is the maximum time taken for any input size.
 Types of Notations for Time Complexity
1. Big Oh denotes "fewer than or the same as" <expression> iterations.
2. Big Omega denotes "more than or the same as" <expression> iterations.
3. Big Theta denotes "the same as" <expression> iterations.
4. Little Oh denotes "fewer than" <expression> iterations.
5. Little Omega denotes "more than" <expression> iterations. idealized
model of the data and its operations

School of Computer Engineering

FAQ cont…
94

 What is Array?
 Array is a collection of variables of same data type that share a common
name.
 Array is an ordered set which consist of fixed number of elements.
 Array is an example of linier data structure.
 In array memory is allocated sequentially so it is also known as
sequential list.
 1-D Array address calculation
Address of A[i] = BA + w * (i) where BA is the base address, w is the word
length and i is the index
 Row-Major order: Row-Major Order is a method of representing multi
dimension array in sequential memory. In this method elements of an array
are arranged sequentially row by row. Thus elements of first row occupies
first set of memory locations reserved for the array, elements of second row
occupies the next set of memory and so on.
Address of A [ i ][ j ] = BA + w * [ n * ( i – Lr ) + ( j – Lc ) ]
School of Computer Engineering
FAQ cont…
95

 Column-Major order: Column-Major Order is a method of representing

multi dimension array in sequential memory. In this method elements of an
array are arranged sequentially column by column. Thus elements of first
column occupies first set of memory locations reserved for the array,
elements of second column occupies the next set of memory and so on.
Address of A [ i][ j ] = BA + w * [( i – Lr ) + m * ( j – Lc )]
 Array ADT: The array is a basic abstract data type that holds an ordered
collection of items accessible by an integer index. These items can be
anything from primitive types such as integers to more complex types like
instances of struct. Since it's an ADT, it doesn't specify an implementation,
but is almost always implemented by an static array or dynamic array.
 Time Complexity of 2-D array traversal = O(m*n)
 Time Complexity of 1-D array traversal = O(n)
 Time complexity of accessing an element of an 2-D array = O(m*n)
 Time complexity of accessing an element of an 1-D array = O(n)

School of Computer Engineering

FAQ cont…
96

 Ragged 2 D Arrays:
char *font[] = {
(char []) {65,8,12,1,0,0x18, 0x3C, 0x66, 0xC3, 0xC3, 0xC3, 0xC3, 0xFF, 0xFF},
(char []) {39,2,3,4,9,0xC0,0xC0, 0xC0},
(char []) {46,2,2,4,0,0xC0,0xC0}};

School of Computer Engineering