Introduction to Data

Structures
Mansi A. Radke

1
Introduction of the course coordinator
Dr. Mansi A. Radke
• B.E. (CSE), Cummins college of Engineering for Women, Pune, India - 2004
• M.S. (CS), University of Maryland, Baltimore County (UMBC), USA – 2008
• Ph.D. (CSE), Visvesvarya National Institute of Technology, Nagpur, India – 2018
• 13+ years of experience together in industry and academics

• 5+ years of Industry Experience:

• Cummins India limited, Pune, India (2004-2006)
• SAP Washington, DC, USA (2007-2008)
• Persistent systems, Nagpur, India (2009-2011)

• 8+ years of Teaching experience:

• UMBC, Maryland, USA – Teaching Assistant (2006-2008)
• Huston-Tillotson University, Austin, USA (2009)
• Ramdeobaba College of Engineering, Nagpur, India (2011-2012)
• Visvesvaraya National Institute of Technology, Nagpur, India (2012- till date)

2
Research Interests over the years

• Information retrieval
• Geographical Information Retrieval
• Natural Language Processing
• Applications of Machine learning to NLP And IR problems

3
Contact Details
• [email protected] – for quick response
• [email protected] – for any official communication
• Phone: 9823335046
(Route your problems through the CR as far as possible)
• WhatApp Number : same as above
(WhatsApp me for a time before calling but do not hesitate to ask
your doubts)

4
Class timings - B Slot
• Tuesday 9 am to 10 am
• Wednesday 2 pm to 3 pm
• Thursday 10 am to 11 am
• Saturday 11 am to 12 pm

• Exams will be in B slot

• Open course and difficult to manage timings of people from all
branches to stick to the slots
5
Text Books Required
• 1. Data Structures & Program Design in C : Robert Kruse, G. L. Tondo
and B. Leung PHI-EEE.
• 2. How to solve it by computer : R G Dromey
• 3. The C programming language: Kernighan Ritchie

6
Marks Distribution
• 25% Midterm exam
• 35% End Sem Exam
• 40% Programming assignments

7
Syllabus for Data Structures Open course
• Review of functions, writing modular programs, pointers, file handling, recursion in detail
• Searching and Sorting Techniques: Merge sort, Heap sort, Quicksort, Binary Search and its applications
• Linked lists, Representation of linked lists in Memory, various operations on linked lists, doubly linked lists,
circular linked lists  
• Stacks and Queues, Array Representation of Stack, Linked List Representation of stack, Applications of stack,
Queue, Array Representation of Queue, Linked List Representation of Queue, applications of queue
• Binary Trees, Binary search trees, various operations on binary search trees, binary tree traversals inorder,
preorder, postorder, applications of binary search trees
• Graphs, directed and undirected graphs, adjacency Matrix Representation of Graphs, Adjacency list
representation of graphs, Breadth First Search, Depth First Search, shortest path algorithms, Minimum
Spanning Tree algorithms – Prims Kruskal’s, topological sorting,  
• Introduction to some advanced data structures, and their applications (Examples of advanced Data structures
are Red Black trees, Skip Lists, Tries, Suffix Trees, B Trees, B+ Trees etc)

8
Some Basic Things to follow:
• Give your programs meaningful names
• Give your functions and variables meaningful names/abbreviations
• Do NOT hard code values in your program
• Save your programs as .c files and not as .cpp files
• You can use any editor, I use Dev C++.

9
Class Participation
• Classes will be on WebEx
• Class link will be sent before the class
• If you want to speak, raise your hand indicating that you want to speak
• You can type in the chat box at any time during the lecture
• You can interrupt me anytime during the lecture for doubts or unclear
things
• Feedback about the pace (slow /fast /okay) should be given from time
to time
• If you want me to repeat something, do not hesitate to say
10
Recap of what has been covered in C
programming 1s year course
• Basic C Constructs • Functions
• Variables • Declaration, definition, call, parameters, actual
parameters, formal parameters,
• Data Types
• Inter function communication, parameter
• Identifiers and keywords passing mechanisms
• E.g. int amount
• Recursion
• Operators
• Arithmetic , relational, conditional, logical • Arrays
• 1 Dimensional, 2 Dimensional
• Expressions
• Precedence and associativity • Sorting techniques bubble, insertion,
• Type conversion selection
• Loops while, for, do while and switch case, • Linear search , binary search
range case • Strings
• Nested Loops • Structures and typedef

11
Recap of some programs that were covered in
C programming 1st year course
1. Area of a circle 14. Sine series
2. Roots of a quadratic equation 15. General series
3. Max of two numbers 16. Mode of an array
4. Exchange (Swap) 17. Removal of duplicates
5. Addition of n numbers 18. Search for an element linear / binary
6. Max/Min of n numbers 19. Sort – Selection, bubble, insertion
7. Second max of n numbers 20. Quicksort
8. GCD of two numbers 21. Mergesort
9. LCM of two numbers 22. Structs – student database standard queries
10. Check if a number is prime 23. Pointers – pass by reference
11. Factorial 24. Prime number generation
12. Fibonacci series 25. Strings – strlen, strcpy, substring, strcmp, reverse a string
13. All of above using recursion 26. Files – char and binary operations

12
Lecture Plan for week 1
• Lecture 1: Recap of C programming course done in 1st year
• Lecture 2: functions and writing modular programs
• Lecture 3: Recursive functions
• Lecture 4: Iteration Versus Recursion

13
Find the second largest number in an array

14
• Finding the second largest
number in an array of size 10

15
Rotate an array by k positions to the right

16
Rotate an array of size 10 by k
positions to the right

17
Functions
Mansi A. Radke

18
Important points about functions
1. Function has a name, a parameter list, a return type, and a body or definition.
2. Function prototype must be declared in the function which is calling it.
3. Printf scanf are functions already provided to us
4. We can also write our own functions
5. Function may have return type may not have return type. If nothing to return then write void as return type.
6. A function may have parameters may not have parameters. I f no parameter list then nothing inside the bracket after
function name e.g. void func1 ()
7. Main is also a function
8. Main returns to the calling environment whether the program was successful or not.
9. Parameter written in the function definition are formal parameters.
10. Parameters written in a function call are actual parameters.

19
Notes
• Functions are there to make the code modular

• Secondly functions provide the concept of reusability

• Thirdly functions provide encapsulation of some computation

• Function can also be called as a method or subroutine or a procedure.

20
Program
• Write a program to check if a given number has three different prime
divisors or not.

21
22
23
24
25
Find the most frequently occurring character
in an input string

26
• Find the most frequently
occurring character in a given
input string containing only
lower case English letters. In
case of multiple characters
having same frequency, print any
of them.

27
Recursion
Mansi A. Radke

28
Activation Record

29
30
31
Key things to note while writing recursive
programs
• Base case
• Making sure you are dealing with progressively smaller or simpler sub
problems is good rule of thumb
• If you do not write a base case or you do not progressively call
simpler/smaller sub-problems then your program may result in stack
overflow due to infinite recursion
• How to parameterize the function is an important aspect
• Recursive solutions are elegant, intuitive and natural in some
situations

32
33
34
35
Problem
Spherical objects, such as cannonballs, can be stacked to form a pyramid with one cannonball at the top, sitting
on top of a square composed of four cannonballs, sitting on top of a square composed of nine cannonballs, and
so forth. Write a recursive function that takes as its argument the height of the pyramid and returns the number
of cannonballs it contains. Your function must operate recursively and must not use any iterative constructs,
such as while or for.

36
Write a recursive function to calculate the
sum of the elements of an array of size n

37
Write a function to calculate the maximum
element of an array using recursion

38
Check whether given string is palindrome

39
• Write a recursive function to
check whether a given string is
palindrome using recursion

40
Recursion Versus Iteration
Mansi A. Radke

41
42
Tail Recursion

43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
The Tower of Hanoi
• The Tower of Hanoi is a puzzle. It consists of three rods and a number of disks of
different sizes, which can slide onto any rod. The puzzle starts with the disks in a
neat stack in ascending order of size on one rod, the smallest at the top, thus
making a conical shape.
• The objective of the puzzle is to move the entire stack to another rod, obeying the
following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of
another stack or on an empty rod.
3. No larger disk may be placed on top of a smaller disk.
• With 3 disks, the puzzle can be solved in 7 moves.

59
The Tower of Hanoi

60
#include <stdio.h>
#define max 3
void towerOfHanoi(int n, char from_peg, char to_peg, char aux_peg)
{
if (n == 1)
{
printf("\n Move disk 1 from peg %c to peg %c", from_peg, to_peg);
return;
}
towerOfHanoi(n-1, from_peg, aux_peg, to_peg);
printf("\n Move disk %d from peg %c to peg %c", n, from_peg, to_peg);
towerOfHanoi(n-1, aux_peg, to_peg, from_peg);
}

int main()
{
int n = max; // Number of disks
towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of pegs
return 0;
}

61
62
Lecture Plan for Week 2
• Iteration versus Recursion
• Linear and Binary Search along with variations of binary search
• Bubble sort, Insertion sort, selection sort Recap along with recursive
version of bubble sort and selection sort
• Quick sort
• Merge sort
• Heap Sort
(Note : This is just the sequence, it may spill over to the next week)

63
Binary Search and its
variations
Mansi A. Radke

64
65
66
Iterative Binary Search

Note: Binary search works only on a sorted array

Assumption: Array is sorted in ascending order

67
Binary Search Recursive

68
Search in an array which is almost or nearly
sorted
• Given an array which is sorted, but after sorting some elements are
moved to either of the adjacent positions, i.e., arr[i] may be present at
arr[i+1] or arr[i-1]. Write an efficient function to search an element in
this array. Basically the element arr[i] can only be swapped with either
arr[i+1] or arr[i-1].
• For example consider the array {2, 3, 10, 4, 40}, 4 is moved to next
position and 10 is moved to previous position.

69
 Example Input and output

Input: arr[] = {10, 3, 40, 20, 50, 80, 70},

key = 40
Output: 2

Input: arr[] = {10, 3, 40, 20, 50, 80, 70},

key = 90
Output: -1

70
71
 Search a target element in a sorted and
rotated array. (All elements are distinct)
Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 3
Output : Found at index 8

Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};

key = 30
Output : Not found

Input : arr[] = {30, 40, 50, 10, 20}

key = 10
Output : Found at index 3

72
73
Find the number of occurrences of a given element in a
sorted array having duplicate entries in an efficient way

E.g. A = { 2,5,5,5,6,6,8,9,9,9}
Element to be searched : 5
Expected output: 5 occurs 3 times

Element to be searched: 6
Expected output: 6 occurs 2 times

74
75
Sorting Techniques
Mansi A. Radke

76
77
78
79
80
• Program for bubble sort

• Note: There is a flag used which

avoids unnecessary comparisons
when the elements are in order

81
82
Bubble Sort with one loop

83
84
Bubble sort without loop!

85
86
Selection sort

87
88
Recursive selection sort

89
90
• Insertion sort

91
92
Lecture Plan for Week 3
• Quick sort
• The two way merge operation
• Merge sort
• Counting array inversions as an application of merge sort
• Heap Sort

• (This is the sequence, it may spill over to the next week)

93
Quicksort
Mansi A. Radke

94
95
Consider the array {1,7,4,3,8,2,6,9,0,5}

96
Quick sort works on recursive partitioning !

97
Quicksort • Quicksort

98
99
100
101
102
Revision of Quicksort
Mansi A. Radke

103
104
105
106
107
108
109
Quick sort corrected
code

In partition function,
i should be initialized to
first + 1!

Please ignore the

previous code.

110
The two way merge
operation
Mansi A. Radke

111
112
113
114
115
Merge Sort
Mansi A. Radke

116
117
Merge sort works on the principle of
recursive merging!

118
119
120
121
122
123
124
125
126
127
128
129
130
131
Heapsort
Mansi A. Radke

132
133
134
135
136
137
138
139
140
141
142
 Suppose this is the heap

MAX-HEAPIFY

143
 Suppose this is the heap

MAX-HEAPIFY

144
 Suppose this is the heap

MAX-HEAPIFY

145
 Suppose this is the heap

MAX-HEAPIFY

146
 Suppose this is the heap

MAX-HEAPIFY

147
148
Build max heap function

149
4 1 3 2 16 9 10 14 8 7

150
4 1 3 2 16 9 10 14 8 7

151
4 1 3 2 16 9 10 14 8 7

152
4 1 3 2 16 9 10 14 8 7

153
4 1 3 2 16 9 10 14 8 7

154
4 1 3 2 16 9 10 14 8 7

155
4 1 3 2 16 9 10 14 8 7

156
4 1 3 2 16 9 10 14 8 7

157
4 1 3 2 16 9 10 14 8 7

158
4 1 3 2 16 9 10 14 8 7

159
4 1 3 2 16 9 10 14 8 7

160
161
Heapsort function

162
Example of Heapsort

163
Example of Heapsort

164
165
166
167
168
Lecture Plan for Week 4
• Pointers basics
• Swap function with and without pointers…… pass by value in C
• Practice programs on pointers, Pointers to structures and typedef

169
170
Basics of Pointers
Manis A. Radke

171
172
Program to understand the basics of Pointers

173
Pointers
1. Pointer is a variable which contains the address of another variable.
2. A pointer has a type (Int pointer, char pointer, float pointer, struct pointer etc.)
3. You can declare a pointer as int *p. This can be read in two ways:
a. p is a pointer to an integer b. *p is an integer

4. * is called the dereferencing operator.

5. All pointers require the same amount of memory whether it is a char pointer or int pointer or
float pointer or struct pointer. Ultimately its an address.

6. & is the referencing operator and gives the address of a variable. It can only be applied to
objects in memory i.e. pointers and arrays. It cannot be applied to expressions, constants or
register variables.

174
Swap by Value and By Pointer

175
Parameter passing mechanism in C

• This is pass by value in both cases!

• An integer is passed by value in swapv.
• A pointer is passed by value here in swapp.

• (The parameter passing mechanism is C language is pass by value

except for arrays. Arrays are passed by reference).

176
Pointers and Arrays

177
Pointer Arithmetic

178
Valid Pointer Operations
a. Assignment of pointers of the same type
b. Adding or subtracting a pointer and an integer
c. Assigning and comparing to zero.
d. subtracting two pointers
e. comparing two pointers

179
Invalid Pointer Operations
a. Adding two pointers
b. Multiply
c. Divide
d. Shift
e. Mask
f. Add a float or double to a pointer
g. Assign one pointer to another type without a cast

180
Pointer to a pointer
• Can you have a pointer to a pointer?

• If yes why? If no why?

181
Practice programs on
pointers
Mansi A. Radke

182
• Calculate the average of the elements in an integer array of size 10

183
184
Find the largest element in an array using pointers

185
Add the elements of 2 matrices using pointers
and functions

186
Matrix multiplication using functions and pointers

187
188
Pointers and character arrays
Mansi A. Radke

189
190
191
Pointers to Pointers and
Array of Pointers
Mansi A. Radke

192
Sort an array of strings using pointers

193
Thank you !
Any questions?

194
Stack
Mansi A. Radke

195
196
197
Revision of Stack
Mansi A. Radke

198
199
Stack Implementation using an
array. Driver code can be written
as a menu driven program using
switch case.

200
201
202
203
Queue Data Structure (Array
Implementation)
Mansi A. Radke

204
205
206
207
208
Need for count variable
• Same configuration is reached front = rear + 1 when the queue is
empty and when the queue is full. So, we cannot differentiate
between them.

• Solution is to use a flag variable or count variable in the queue

structure.

209
210
211
212
213
214
215
Demo of Queue Code

216
Assignment no 2
• You have to implement Stack.
• You have to implement Queue.
• You have to simulate a queue using stack as the backend.
• Stack functions
• Empty , full, push, pop.

Simulate a Queue (You have to make it work as a queue.)

Hint: You need 2 stacks.
Deadline: 21st February 2021 11.59 pm
217