EC 102

“Data Structure & Algorithms”

Lecture-1
[CO1, CO2, CO3]
Introduction to C programming with Array, Queue, Linked List
Introduction to Algorithmic complexity-time & space

Course Instructor
Dr. Chhavi Dhiman
Assistant Professor, ECE
DTU Contact at:
[email protected]

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 1

 Course Objectives & Outcomes
Course Objective

To familiarize students with the basic data structures and

their usage in fundamental algorithms

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 2

Course Outcomes

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 3

Inroduction

• Data structure→ how to program efficiently

• Program
1. must run correctly and efficiently
“ run in accordance with the specifications”
“minimum time , memory use”
2. Be easy to read and understand
3. Be easy to debug
4. Be easy to modify

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 4

Inroduction

Efficient Program can be written by using

appropriate data structure, algorithms rather than
hit and trials/hacks run in accordance with the
specifications

Data: basic entity/fact that is used for

calculation/manipulation.
1. Numerical-integers, float
2. Alphanumerical Data-char

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 5

Inroduction

Data structure:
Data may be a single value/ set of values.

It must be organised in a particular fashion. →

structuring of data

Program→ Data structure+ Algorithm

Algorithm: steps of operation to be performed:

procedural way of solving any problem.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 6

Linked List

The firm wants the list of customers for a given salesperson

Method 1

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 7

Linked List
The firm wants the list of customers for a given salesperson

Problem Method 1: need to access all the customers

Method 2

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 8

Stack and Queue [Linear Lists]

𝐋𝐚𝐬𝐭 𝐈𝐧 𝐅𝐢𝐫𝐬𝐭 𝐎𝐮𝐭 (𝐋𝐈𝐅𝐎) F𝐢𝐫𝐬𝐭 𝐢𝐧 𝐅𝐢𝐫𝐬𝐭 𝐎𝐮𝐭 ( 𝐅𝐈𝐅𝐎)

𝐈𝐦𝐩𝐥𝐞𝐦𝐞𝐧𝐭𝐞𝐝 𝐮𝐬𝐢𝐧𝐠 𝐀𝐫𝐫𝐚𝐲 𝐚𝐧𝐝 𝐏𝐨𝐢𝐧𝐭𝐞𝐫𝐬

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 9

Tree
𝐇𝐢𝐞𝐫𝐚𝐫𝐢𝐜𝐡𝐚𝐥 𝐑𝐞𝐥𝐚𝐭𝐢𝐨𝐧𝐬𝐡𝐢𝐩𝐬 𝐛𝐞𝐭𝐰𝐞𝐞𝐧 𝐞𝐥𝐞𝐦𝐞𝐧𝐭𝐬

(2𝑥 + 𝑦)(𝑎 − 7𝑏)3

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 10

Trees vs Graphs

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 11

Memory allocation in C

• Compile time/static memory allocation

• Run time/ Dynamic allocation (using pointers)

• C also provides memory allocation and deallocation

functions:
Malloc() Calloc() Free() Realloc()

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 12

Memory allocation in C

• Malloc() [stdlib.h /alloc.h]

Malloc (no. of elements* size of each elements)

Ex: int *ptr
ptr=malloc (10*sizeof(int));
[returns void pointer/ NULL]
Or
ptr=(int *)malloc(10*sizeof(int)); // typecasting

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 13

Memory allocation in C

• Calloc() [stdlib.h /alloc.h]

Calloc (no. of elements, size of each elements)

Ex: int *ptr
ptr=(int *)calloc(10, 2); // typecasting

Free() Realloc
Free(ptr); ptr= Realloc(ptr, new_size);

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 14

Abstract Data Types

• Abstract data types refers to set of data values and

associated operations that are specified accurately,
independent of any particular implementation.
• ADT consists of set of definitions that allows us to
use the functions while hiding the implementation

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 15

Abstract Data Types

• The interface can only access the public functions.

• For each ADT operation there is an algorithm that
performs the specified task. The operation name
and parameters are available to the application.
• To implement ADT list : array and linked list [basic
structures]

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 16

Abstract Data Types

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 17

Analysing Algorithms

• What is a good algorithm?

❑Efficient: small running time and lesser space used
❑Efficiency as a function of input size
the number of bits in an input size
number of data elements

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 18

Analysing Algorithms

• Measuring running time

❑Write a program
❑Run the program with data sets of varying size and
composition
❑Use the method like System.currentTimeMillis() to
get accurate measure of actual running time
Limitations:
Writing the program→ time consuming
Observations for only specific/ limited number of datasets
For comparing two algos same h/w and s/w environment should be used

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 19

Analysing Algorithms

• Measuring running time

Limitations:
Writing the program→ time consuming
Observations for only specific/ limited number of datasets
For comparing two algos same h/w and s/w environment should be used

Solution: General Methodology

Use high-level description of algorithm instead of testing one of its
implementations
Takes into account of all possible inputs
Efficiency evaluation independent of h/w and s/w env.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 20

Analysing Algorithms

• Pseudo-Code
A mixture of natural language and high-level programming concepts that
describes the main ideas behind generic implementation of data structure of
algorithm.
Algorithm arrayMax(A,n):
Input: An array a storing n integers.
Output: Maximum element of A

currentMAx A[0]
for i1 to n-1 do
if currentMax< A[i] then currentMax A[i]
return currentMax

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 21

Analysing Algorithms

❑Primitive Operation: Low level operations

independent of programming language.
✓Data movement (assigning)
✓Control (branching, subroutine call, return)
✓Arithmetic and logical operations (addition,
comparison)
❑ by inspecting pseudo code, we can count the
number of primitive operations executed by an
algorithm.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 22

Analysing Algorithms

❑ Example: Sorting
INPUT OUTPUT
𝒂𝟏 , 𝒂𝟐 , 𝒂𝟑 … . . 𝒂 𝒏 𝒃𝟏 , 𝒃𝟐 , 𝒃𝟑 … . . 𝒃𝒏
SORTING
Sequence of numbers Permutation of sequence of
numbers
2, 5, 4, 10, 7
2, 4, 5, 7, 10
Correctness
𝒃𝟏 < 𝒃𝟐 < 𝒃𝟑 … . . < 𝒃𝒏

Running time:
✓ Number of elementa (n)
✓ How (partially) sorted they are
✓ algorithm

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 23

 Analysing Algorithms
❑ Insertion sort
INPUT OUTPUT
𝒂 𝟏 , 𝒂𝟐 , 𝒂𝟑 … . . 𝒂𝒏 𝒃𝟏 , 𝒃𝟐 , 𝒃𝟑 … . . 𝒃𝒏

Sorting a hand of cards using

INSERTION-SORT(A) insertion sort.
Input: A[1….n]
Output: increasing order sequence
1 for j  2 to n do Strategy:
2 key  A[j] ✓ Start empty handed
✓ Insert a card in right position of already sorted
3 //Insert A[j] into the sorted sequenceA[1….j-1] hand
4 ij-1 ✓ Continue unotill all cards are inserted/ sorted
5 while i > 0 and A[i] > key
6 do A[i+1]A[i]
7 ii-1
8 A[i+1] key

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 24

 Analysing Algorithms
❑ Insertion sort
INSERTION-SORT(A)
Input: A[1….n]
Output: increasing order sequence
1 for j  2 to n do i j
2 key  A[j] [key=2]
3 //Insert A[j] into the sorted sequenceA[1….j-1]
4 ij-1 [i=1]
5 while i > 0 and A[i] > key [5>2]
6 do A[i+1]A[i]
7 ii-1 [i=0]
8 A[i+1] key [A[1]=2]

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 25

 Analysing Algorithms
❑ Insertion sort
INSERTION-SORT(A)
Input: A[1….n]
Output: increasing order sequence
1 for j  2 to n do i j
2 key  A[j] [key=4]
3 //Insert A[j] into the sorted sequenceA[1….j-1]
4 ij-1 [i=2]
5 while i > 0 and A[i] > key [5>4]
6 do A[i+1]A[i]
7 ii-1 [i=1]
8 A[i+1] key [A[2]=4]

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 26

 Analysing Algorithms
❑ Insertion sort
INSERTION-SORT(A)
Input: A[1….n]
Output: increasing order sequence
1 for j  2 to n do i j
2 key  A[j] [key=6]
3 //Insert A[j] into the sorted sequenceA[1….j-1]
4 ij-1 [i=3]
5 while i > 0 and A[i] > key [5>6]
6 do A[i+1]A[i]
7 ii-1 [i=1]
8 A[i+1] key [A[4]=6]

Practice: Rewrite the INSERTION-SORT procedure to sort into nonincreasing

instead of nondecreasing
order.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 27

 Analysing Algorithms
❑ Insertion sort
INSERTION-SORT(A)
Input: A[1….n]
Output: increasing order sequence
1 for j  2 to n do
2 key  A[j] [key=6]
3 //Insert A[j] into the sorted sequenceA[1….j-1]
4 ij-1 [i=3]
5 while i > 0 and A[i] > key [5>6]
6 do A[i+1]A[i]
7 ii-1 [i=1]
8 A[i+1] key [A[4]=6]

we let tj denote the number of times the while loop test in line 5 is executed for that value of j.
*When a for or while loop exits in the usual way (i.e., due to the test in the loop header), the test is
executed one time more than the loop body

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 28

Analysing Algorithms

• The running time of the algorithm is the sum of running times for each statement
executed;
• a statement that takes 𝑐𝑖 steps to execute and executes 𝑛 times will contribute 𝑛𝑐𝑖
to the total running time.
• To compute T(n) the running time of INSERTION-SORT on an input of n
values, we sum the products of the cost and times columns, obtaining

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 29

Analysing Algorithms

• Even for inputs of a given size, an algorithm’s running time may depend on
which input of that size is given.
For example: INSERTION-SORT, the best case occurs
“if the array is already sorted” .
For each j=2 to 𝑛, we then find that A[i] < key in line 5
Thus 𝑡𝑗 = 1 for, j=2,3,….n, and the best-case running time is

𝑇 𝑛 = 𝑎𝑛 + 𝑏; 𝑎& 𝑏 are constants

𝑇(𝑛) is linear function of 𝑛.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 30

Analysing Algorithms

• If the array is in decreasing order—the worst case results.

• We must compare each element 𝐴[𝑗] with each element in the entire sorted
subarray 𝐴[1 … … . 𝑗 − 1], and so 𝑡𝑗 = j for j=2,3, …..n.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 31

Analysing Algorithms

• If the array is in decreasing order—the worst case results.

We can express this worst-case running time as

𝑇(𝑛) = 𝑎𝑛2 + 𝑏𝑛 + 𝑐, for constants a, b, and c it is thus a
𝑇(𝑛)= quadratic function of n.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 32

Analysing Algorithms

worst-case running time,

• the longest running time for any input of size n.
• gives us an upper bound on the running time for any input.
• Knowing it provides a guarantee that the algorithm will never take any longer.
• The “average case” is often roughly as bad as the worst case. Suppose that we
randomly choose n numbers and apply insertion sort. How long does it take to
determine where in subarray A[1…. J-1] to insert element A[j] ?
On average, half the elements in A[1….. J-1] are less than A[j] , and half the
elements are greater.
On average, therefore, we check half of the subarray A[1…..j-1], and so 𝒕𝒋 = j/2.
The resulting average-case running time turns out to be a quadratic function of
the input size, just like the worst-case running time. T(n)=f(𝒏𝟐 )

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 33

Analysing Algorithms

running time best case/worst case/ average case:

• Best case: T(n)= f(𝒏 ): linear
• Worst case: T(n)=f(𝒏𝟐 )
• Average case: T(n)=f(𝒏𝟐 )

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 34

Analysing Algorithms

Order of growth:
constants 𝑐𝑖 to represent cost of each statement
• these constants give us more detail : we expressed the worst-case running time
as 𝑎𝑛2 + 𝑏𝑛 + 𝑐 for some constants a, b, and c that depend on the statement
costs 𝑐𝑖 .
✓ Asymptotic Analysis: Captures the essence how running time of algorithm
increases with the size of input in the limit.
Assumption for determining computational efficiency for large inputs.:
• We consider only the leading term of a formula (e.g., 𝒂𝒏𝟐 ), since the
lower-order terms are relatively insignificant for large values of n.
• We also ignore the leading term’s constant coefficient, since constant
factors are less significant than the rate of growth in determining
computational efficiency for large inputs.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 35

Analysing Algorithms

Asymptotic Analysis:

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 36

Analysing Algorithms

Asymptotic Analysis:
(a) ⊝ notation bounds a function to within constant factors.
f(n)=T(n) = ⊝(g(n))
// if there exist positive constants n0, c1, and c2 such that at and to the right
of n0, the value of f (n) always lies between c1g(n) and c2g(n) inclusive.

average case
analysis

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 37

Analysing Algorithms

Asymptotic Analysis:
(b) O-notation gives an upper bound for a function to within a constant factor. We
write
F(n)=O(g(n))
// if there are positive constants n0 and c such that at and to the right of n0, the
value of f(n) always lies on or below cg(n)

Worst case
analysis

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 38

Analysing Algorithms

Asymptotic Analysis:
(c) Ω -notation gives a lower bound for a function to within a constant factor.
F(n)=T(n)=Ω(g(n))
// if there are positive constants n0 and c such that at and to the right of
n0, the value of f(n) always lies on or above cg(n)

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 39

Analysing Algorithms

Assumption for determining computational efficiency for large inputs.:

• We consider only the leading term of a formula (e.g., 𝒂𝒏𝟐 ), since the lower-
order terms are relatively insignificant for large values of n.
• We also ignore the leading term’s constant coefficient, since constant factors are
less significant than the rate of growth in determining computational efficiency
for large inputs.

𝑰𝒏𝒔𝒆𝒓𝒕𝒊𝒐𝒏 𝒔𝒐𝒓𝒕: 𝒘𝒐𝒓𝒔𝒕 𝒄𝒂𝒔𝒆 𝒕𝒊𝒎𝒆

𝑻 𝒏 = 𝑶(𝒏𝟐 )

We usually consider one algorithm to be more efficient than another

if worstcase running time has a lower order of growth.
Order of growth ∶ [𝑻_𝑨𝟏 (𝒏) ] < [𝑻_𝑨𝟐 (𝒏) ]
O(n)<O(n2)

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 40

Analysing Algorithms

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 41

Analysing Algorithms
Commonly used Logarithms and Summations

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 42

Analysing Algorithms
Commonly used Logarithms and Summations

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 43

Designing Algorithms

For insertion sort, we used an incremental approach:

The divide-and-conquer approach:
• Help to design a sorting algorithm whose worst-case running time is much less
than that of insertion sort.

• Recursive algorithm: to solve a given problem, an algorithm calls themselves

recursively one or more times to deal with closely related subproblems.
• Divide-and-conquer approach:
1. Divide
➢ Theythebreak
problem into a number
the problem of subproblems
into several thatthat
subproblems areare
smaller instances
similar to the of
original problem
the same but smaller in size,
problem.
2. Conquer the subproblems
➢ solve the subproblems recursively,
by solving them
and recursively.
3. Combine the solutions to the subproblems into the solution for the original
➢ Then combine these solutions to create a solution to the original problem
problem.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 44

Designing Algorithms

• The merge sort algorithm closely follows the divide-and-conquer paradigm.

Intuitively, it operates as follows.

1. Divide: Divide the n-element sequence to be sorted into two subsequences of

n/2 elements each.
2. Conquer: Sort the two subsequences recursively using merge sort.
3. Combine: Merge the two sorted subsequences to produce the sorted answer.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 45

Designing Algorithms

1. Divide: Divide the n-element sequence to be sorted into two subsequences of

This function performs the merging of two sorted sub-arrays that are A[beg…mid] and A[mid+1…end], to build one sorted
n/2So,elements
array A[beg…end]. the inputs of each.
the MERGE function are A[], beg, mid, and end.
2. Conquer: Sort the two subsequences recursively using merge sort.
3. Combine: Merge the two sorted subsequences to produce the sorted answer.

MERGE_SORT(arr, beg, end)

This function performs the merging of
if beg < end two sorted sub-arrays that
set mid = (beg + end)/2 A[beg…mid] and A[mid+1…end],
MERGE_SORT(arr, beg, mid) one sorted array A[beg…end].
MERGE_SORT(arr, mid + 1, end)
MERGE (arr, beg, mid, end) inputs of the MERGE function →
end of if A[], beg, mid, and end.

END MERGE_SORT

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 46

Designing Algorithms

1. Divide: Divide the n-element sequence to be sorted into two subsequences of

This function performs the merging of two sorted sub-arrays that are A[beg…mid] and A[mid+1…end], to build one sorted
n/2So,elements
array A[beg…end]. the inputs of each.
the MERGE function are A[], beg, mid, and end.
2. Conquer: Sort the two subsequences recursively using merge sort.
3. Combine: Merge the two sorted subsequences to produce the sorted answer.

MERGE_SORT(arr, p, r)

if p < r
set mid = (p + r)/2
MERGE_SORT(arr, p, r)
MERGE_SORT(arr, mid + 1, r)
MERGE (arr, p, mid, r)
end of if

END MERGE_SORT

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 47

 Designing Algorithms

MERGE_SORT(arr, p, r)

if p < r
set mid = (p + r)/2
MERGE_SORT(arr, p, mid)
MERGE_SORT(arr, mid + 1, r)
MERGE (arr, p, mid, r)
end of if

END MERGE_SORT

Space complexity
O(n)

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 48

Designing Algorithms

At the start of each iteration of the for loop of

lines 12–17, the subarray
❑ A[p:k-1] contains the k-p smallest elements
of L[1:n1+1] and R[1: n2+1], in sorted order.
❑ Moreover, L[i] and R[j] are the smallest
elements of their arrays that have not been
copied back into A.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 49

Designing Algorithms

Initialization:
Line 12: k = p → A[p….k-1] = empty
→ k-p = 0 smallest elements of L and R
Line 10-11: i = j = 1 → L[i], and R[j] are smallest
elements of L and R.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 50

Designing Algorithms

p q r

n1 n2

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 51

Designing Algorithms
p q r

2<=2? n2
n1

4<=2?
Maintenance:

4<=3?

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 52

Designing Algorithms

4<=6?

5<=6?
Maintenance:

7<=6?

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 53

Designing Algorithms
7<=6?

7<=∞?

Maintenance:
Termination:

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 54

Designing Algorithms
A recurrence for the running time of a divide-and-conquer algorithm falls out
from the three steps of the basic paradigm

✓ let T (n) be the running time on a problem of size n.

✓ If the problem size is small enough, say n <=c ; c=constant
➔ T (n)=Θ(1)
✓ Suppose that our division of the problem yields a subproblems, each of
which is 1/b the size of the original.
➢ For merge sort, both a and b are 2
➢ Some divide-and-conquer algorithms in which a≠b.
➔It takes time T(n/b) to solve one subproblem of size n=b
➔it takes time aT(n/b) to solve a of them.

✓ D(n) time to divide the problem into subproblems

✓ C(n) time to combine the solutions to the subproblems into the solution to
the original problem

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 55

Designing Algorithms

worst-case running time T(n) of merge sort

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 56

Designing Algorithms
Master Theorem : T(n) = Θ 𝑛𝑙𝑔 𝑛 , lg 𝑛 = 𝑙𝑜𝑔2 𝑛
logarithm function grows slower than linear function for large
inputs….
Θ 𝑛𝑙𝑔 𝑛 𝑏𝑒𝑡𝑡𝑒𝑟 𝑡ℎ𝑎𝑛 Θ 𝑛2
[merge sort worst case ] [𝑖𝑛𝑠𝑒𝑟𝑡𝑖𝑜𝑛 𝑠𝑜𝑟𝑡 𝑤𝑜𝑟𝑠𝑡 𝑐𝑎𝑠𝑒]

where the constant c represents the time required to solve problems of size 1
time per array element of the divide and combine steps

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 57

Designing Algorithms
T(n)= 2T(n/2)+ cn

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 58

Designing Algorithms

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 59

Designing Algorithms

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 60

Designing Algorithms

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 61

Designing Algorithms

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 62

Designing Algorithms

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 63

Designing Algorithms
The master method for solving recurrences

The master method provides a “cookbook” method for solving

recurrences of the form

where a >=1 and b > 1 are constants and f (n) is an asymptotically positive
function.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 64

Designing Algorithms
The master method for solving recurrences

If a=7, b=2, and f (n)=Θ(𝑛2 )

✓ n/b might not be an integer

✓ Replacing each of the a terms T(n/b) with

✓ It will not affect the asymptotic behavior of the recurrence,

✓ We normally find it convenient, therefore, to omit the floor and ceiling

functions when writing divide-and-conquer recurrences of this form.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 65

Think?

What are recurrences and their uses?

A recurrence can describe any sequence of elements in an
array in terms of themselves.
Recurrences are used in various branches of mathematics
in addition to Computer Science (in time complexity analysis) their
application in finding the bound for the number of trivial
operations by an algorithm, such as Number Theory (Fibonacci
sequence), Calculus (Euler's Theorem), etc.
An example of a recurrence,

T(N) = T(N/2) + 1, (n > 1)

T(1) = 1

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 66

 Methods to solve recurrence:
1. Substitution method
2. Master’s Theorm Method

Depending on the requirement, they can also help us finding complexity of

algorithm (depending on if we need a tight bound or just an upper bound), and
there are recurrences where you may not apply specific methods.

For example, Master’s Theorem →solve recurrences

if in the recurrence T(n) = a * T(n / b) + f(n), f(n) is a polynomial.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 67

Arrays
• Insertion in an array
• Deletion in an array
• Merging two arrays
• Pointers & arrays
• Array of pointers
• Array of structures
• Array within structures

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 68

 Arrays-Insert at the end
#include <stdio.h>
// Driver Code
int main()
{
int arr[20] = { 12, 16, 20, 40, 50, 70 };
int capacity = sizeof(arr) / sizeof(arr[0]);
int n = 6;
int i, key = 26;

printf("\n Before Insertion: ");

int insertSorted(int arr[], int n, int key, int capacity) for (i = 0; i < n; i++)
{ printf("%d ", arr[i]);

// Cannot insert more elements if n is // Inserting key

// already more than or equal to capacity n = insertSorted(arr, n, key, capacity);
if (n >= capacity)
return n;
arr[n] = key; printf("\n After Insertion: ");
for (i = 0; i < n; i++)
return (n + 1); printf("%d ", arr[i]);
}
return 0;
}
Code Link

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 69

 Arrays-Insert at at any position

#include <stdio.h>
// Driver's code
int main()
{
int arr[15] = { 2, 4, 1, 8, 5 };
int n = 5;
printf("Before insertion : ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
void insertElement(int arr[], int n, int x, int pos) printf("\n");
{
// shift elements to the right int x = 10, pos = 2;
// which are on the right side of pos // Function call
for (int i = n - 1; i >= pos; i--) insertElement(arr, n, x, pos);
arr[i + 1] = arr[i]; n++;
printf("After insertion : ");
arr[pos] = x;
for (int i = 0; i < n; i++)
}
printf("%d ", arr[i]);

return 0;
}

Code Link

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 70

 Arrays-Deletion

#include <stdio.h>
// Driver's code
int main()
/ Function to delete an element
{
int deleteElement(int arr[], int n, int
int i;
key) int arr[] = { 10, 50, 30, 40, 20 };
{
// Function to implement // Find position of element to be
deleted int n = sizeof(arr) / sizeof(arr[0]);
search operation int key = 30;
int pos = findElement(arr, n, key);
int findElement(int arr[],
int n, int key)
cout << "Array before deletion\n";
{ if (pos == -1) {
for (i = 0; i < n; i++)
int i; cout << "Element not found";
cout << arr[i] << " ";
for (i = 0; i < n; i++) return n;
if (arr[i] == key) }
return i; // Function call
// Deleting element n = deleteElement(arr, n, key);
return -1; int i;
} for (i = pos; i < n - 1; i++) cout << "\n\nArray after deletion\n";
arr[i] = arr[i + 1]; for (i = 0; i < n; i++)
cout << arr[i] << " ";

return n - 1;
} return 0;
}

Code Link
26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 71
Arrays-Merge
Method 1: O((m+n) log(m+n)) Time and O(m+n) space
✓ Take all the elements of arr1[] and arr2[] in arr3[].
✓ Then simply sort the arr3[].

Method 2 : (O(n1 * n2) Time and O(n1+n2) Extra Space)

✓ Create an array arr3[] of size n1 + n2.

✓ Copy all n1 elements of arr1[] to arr3[]
✓ Traverse arr2[] and one by one insert elements (like insertion sort) of
arr2[] to arr3[]. This step take O(n1 * n2) time.

Method 3: (O(n1 + n2) Time and O(n1 + n2) Extra Space)

✓ Create an array arr3[] of size n1 + n2.

✓ Simultaneously traverse arr1[] and arr2[].
▪ Pick smaller of current elements in arr1[] and arr2[], copy this smaller
element to next position in arr3[] and move ahead in arr3[] and the array
whose element is picked.
✓ If there are remaining elements in arr1[] or arr2[], copy them also in arr3[].

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 72

Arrays-Merge

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 73

 Arrays-Merge

Time Complexity : O(n1 + n2)

Auxiliary Space : O(n1 + n2)

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 74

 Pointers and Arrays

%p is a format specifier which is used if we want to print data of type (void *) i.e, in
simple words address of pointer or any other variable displayed in hexadecimal value.
1.int a=10;
2.int* ptr =&a;
3.printf("%p\n",ptr);
4.printf("%lu\n" ptr);

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 75

Practice Problem?

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 76

How Are Pointers Related to Arrays

The name of an array➔ pointer to the first element of the array.

int myNumbers[4] = {25, 50, 75, 100};

// Get the memory address of the myNumbers array

printf("%p\n", myNumbers);

// Get the memory address of the first array element

printf("%p\n", &myNumbers[0]);

Result: This basically means that we can

0x7ffe70f9d8f0 work with arrays through
0x7ffe70f9d8f0 pointers!

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 77

How Are Pointers Related to Arrays

The name of an array➔ pointer to the first element of the array.

Since myNumbers is a pointer to the first element in myNumbers,
you can use the * operator to access it:

int myNumbers[4] = {25, 50, 75, 100};

// Get the value of the first element in myNumbers

printf("%d", *myNumbers);

Output: 25
This basically means that we can
work with arrays through
pointers!

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 78

How Are Pointers Related to Arrays

int myNumbers[4] = {25, 50, 75, 100};

// Get the value of the second element in myNumbers

printf("%d\n", *(myNumbers + 1));

// Get the value of the third element in myNumbers

printf("%d", *(myNumbers + 2));
Output:
50
75

int *ptr = myNumbers; Output:

int i; 25
50
for (i = 0; i < 4; i++) { 75
printf("%d\n", *(ptr + i)); 100

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 79

How Are Pointers Related to Arrays

It is also possible to change the value of

array elements with pointers

int myNumbers[4] = {25, 50, 75, 100};

// Change the value of the first

element to 13
*myNumbers = 13;

// Change the value of the second

element to 17
*(myNumbers +1) = 17;

// Get the value of the first element

printf("%d\n", *myNumbers);
Output:
// Get the value of the second element 13
printf("%d\n", *(myNumbers + 1)); 17

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 80

Pointers and Arrays

It is also possible to change the value of

array elements with pointers

Output:
13
17

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 81

Array of pointers

• A pointer array is a homogeneous collection of

indexed pointer variables that are references to a
memory location.
• It is generally used in C Programming when we want
to point at multiple memory locations of a similar
data type in our C program.
• We can access the data by dereferencing the pointer
pointing to it.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 82

Array of pointers

The sports array is stored in the memory as follows:

char sports[5][15] = {
• The total size of the sports array is 75 bytes but
"golf",
only 34 bytes is used, 41 bytes is wasted.
"hockey",
• 41 bytes may not appear much but in a large
"football",
program,
"cricket",
• a considerable amount of bytes would be
"shooting"
wasted.
};

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 83

 Array of pointers

Here sports is an array of pointers to strings.

char *sports[5] = {
"golf",
"hockey",
"football",
"cricket",
"shooting"
};

• In this case, all string literals occupy 34 bytes and 20 bytes are occupied by the array of
pointers i.e sports.
• So, just by creating an array of pointers to string instead of array 2-D array of
characters
• we are saving 21 bytes (75-54=21) of memory.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 84

 Array of pointers

Here sports is an array of pointers to strings.

char *sports[5] = {
"golf",
"hockey",
"football",
"cricket",
"shooting"
};

It is important to emphasize that in an array of pointers to strings, it is not

guaranteed that the all the strings will be stored in contiguous memory
locations. Although the characters of a particular string literal are always stored
in contiguous memory location.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 85

 Array of Pointers

int arr[5] = {10, 20, 30, 40, 50};

int (*ptr)[5];
ptr = &arr;

here, ptr points the entire array.

✓ Since ptr is an array pointer,

✓ *ptr will be again an address which is the address of the first element in the
array.
✓ **ptr will be the value stored at the address.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 86

Array of Pointers

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 87

Array of structures

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 88

Array of structures

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 89

 Array of structures

#include<stdio.h>
#include <string.h>
struct student{ Enter Records of 5 students
int rollno; Enter Rollno:1
char name[10]; Enter Name:Sonoo
}; Enter Rollno:2
int main(){ Enter Name:Ratan
int i; Enter Rollno:3
struct student st[5]; Enter Name:Vimal
printf("Enter Records of 5 students"); Enter Rollno:4
for(i=0;i<5;i++){ Enter Name:James
printf("\nEnter Rollno:"); Enter Rollno:5
scanf("%d",&st[i].rollno); Enter Name:Sarfraz
printf("\nEnter Name:");
scanf("%s",&st[i].name); Student Information List:
} Rollno:1, Name:Sonoo
printf("\nStudent Information List:"); Rollno:2, Name:Ratan
for(i=0;i<5;i++){ Rollno:3, Name:Vimal
printf("\nRollno:%d, Name:%s",st[i].rollno,st[i].name); Rollno:4, Name:James
} Rollno:5, Name:Sarfraz
return 0;
}

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 90

 Array of structures

#include<stdio.h>
struct student
{
char name[20];
int id;
float marks;
};
void main()
{ Enter the name, id, and marks of student 1 James 90 90
struct student s1,s2,s3; Enter the name, id, and marks of student 2 Adoms 90 90
int dummy; Enter the name, id, and marks of student 3 Nick 90 90
printf("Enter the name, id, and marks of student 1 ");
Printing the details....
scanf("%s %d %f",s1.name,&s1.id,&s1.marks);
scanf("%c",&dummy); James 90 90.000000
printf("Enter the name, id, and marks of student 2 "); Adoms 90 90.000000
scanf("%s %d %f",s2.name,&s2.id,&s2.marks); Nick 90 90.000000
scanf("%c",&dummy);
printf("Enter the name, id, and marks of student 3 ");
scanf("%s %d %f",s3.name,&s3.id,&s3.marks);
scanf("%c",&dummy);
printf("Printing the details....\n");
printf("%s %d %f\n",s1.name,s1.id,s1.marks);
printf("%s %d %f\n",s2.name,s2.id,s2.marks);
printf("%s %d %f\n",s3.name,s3.id,s3.marks);
}

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 91

Array of structures

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 92

 Stacks

A stack is a linear data structure where elements are stored in the LIFO (Last
In First Out) principle where the last element inserted would be the first
element to be deleted.

A stack is an Abstract Data Type (ADT), that is popularly used in most

programming languages.

It is named stack because it has the similar operations as the real-world stacks,
for example − a pack of cards or a pile of plates, etc.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 93

Stacks

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 94

Stacks-Insertion

1. Checks if the stack is full.

2. If the stack is full, produces an error and exit.

3. If the stack is not full, increments top to point

next empty space

4. Adds data element to the stack location, where top

is pointing.

5. Returns success.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 95

 Stacks-Insertion

/* Function to insert into the stack */

#include <stdio.h> int push(int data)
{
int MAXSIZE = 8;
if(!isfull())
int stack[8]; { top = top + 1;
int top = -1; stack[top] = data;
}
Main function else
*/ int main() {
printf("Could not insert data, Stack is
{ int i; full.\n");
push(44); push(10); }
push(62); push(123); }
push(15); int isfull()
printf("Stack Elements: \n"); {
// print stack data if(top == MAXSIZE)
for(i = 0; i < 8; i++) return 1;
else
{ printf("%d ", stack[i]); } return 0;
return 0; }
}
Stack Elements: 44 10 62 123 15 0 0 0
26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 96
Stacks-Deletion

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 97

Stacks-Deletion

Stack Elements: 44 10 62 123 15 0 0 0

Elements popped: 15 123 62 10 44

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 98

Stack- Expression Parsing

Parsing expression means analyzing the expression for its

words or symbols depending on a particular criterion.

Expression parsing is a term used in a programming

language to evaluate arithmetic and logical expressions.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 99

Stack- Expression Parsing

Infix Notation

a - b + c,

where operators are used in-between operands.

It is easy for us humans to read, write, and speak in infix notation

but the same does not go well with computing devices.

An algorithm to process infix notation could be difficult and costly

in terms of time and space consumption.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 100

Stack- Expression Parsing

Prefix Notation

+ab

where operators are written ahead of operands.

This is equivalent to its infix notation a + b.

Prefix notation is also known as Polish Notation.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 101

Stack- Expression Parsing

Postfix Notation

This notation style is known as Reversed Polish Notation.

In this notation style, the operator is postfixed to the operands

i.e., the operator is written after the operands.

ab+

This is equivalent to its infix notation a + b.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 102

Stack- Expression Parsing

Rules

a + b − c,
1. both + and − have the same precedence,
2. Then which part of the expression will be evaluated first, is determined by
associativity of those operators.
3. Here, both + and − are left associative, so the expression will be evaluated as
(a + b) − c.

26 February 2024 DELHI TECHNOLOGICAL UNIVERSITY 103