Data Structures with
Competitive Coding
By
Dr. Prasanta Kumar Sahoo
Professor, Dept. of CSE, AU
Course Objectives:
• To train students in algorithm analysis, recursion, and selecting
suitable data structures for problem-solving, focusing on algorithm
correctness.
• To implement dynamic data structures (linked lists, binary trees)
and sub-quadratic sorting algorithms (quick sort, merge sort, heap
sort) to solve data structure problems.
• To able to get jobs in different IT firms as a developer with core
and competitive coding skills.
Module 1: Data Structures Basics (10 hours)
• Unit-1 Content
• Definition, Importance, Algorithm, and Pseudocode
• Types of Data Structures, Abstract Data Types (ADTs)
• Complexity Analysis & Asymptotic Notations
ALGORITHM
A sequence of unambiguous instructions for
solving a problem, i.e. for obtaining the
required output for any legitimate input in a
finite amount of time.
Properties of Algorithm
• Non-ambiguity
• Finiteness
• Range of inputs
• Simple
• Effectiveness
• Several algorithms for solving the same problem
Importance of Algorithms
• Enhances problem-solving ability
• Optimizes time and memory usage
• Crucial for software performance
• Foundation for data processing and machine learning
Applications of Algorithms
• 1. Search Engines
• Ranking pages using algorithms like PageRank
• Crawling and indexing web content
• 2. Social Media
• Feed ranking (e.g., Facebook/Instagram algorithms)
• Friend suggestions (graph algorithms)
• Content recommendation (machine learning algorithms)
• 3. Navigation and Maps
• Shortest path algorithms (Dijkstra’s, A*)
• Traffic prediction and route optimization
Pseudocode
•Informal high-level description of a computer program or algorithm
•Example:
Algorithm Sum(A, n)
sum ← 0
for i ← 1 to n do
sum ← sum + A[i]
return sum
What is a Data Structure?
• Definition:
A way of organizing and storing data so that it can be accessed and
modified efficiently.
• Examples: Arrays, Linked Lists, Trees, Graphs
• Types of Data Structures
• Primitive: int, float, char, etc.
• Non-Primitive:
• Linear: Array, Stack, Queue, Linked List
• Non-linear: Tree, Graph
• Hash-based: Hash Table
Abstract Data Types (ADTs)
• ADT defines what operations are to be performed but not how.
• It is a logical description of how data is organized and what operations
are allowed. What a data type does, not how it does it.
• Common ADTs:
• List
• Stack
• Queue
• Deque
• Map
• Set
Complexity
Time complexity:
– How much time it takes to compute
– Measured by a function T(N)
Space complexity:
– How much memory it takes to compute
– Measured by a function S(N)
12
Some common Functions
Asymptotic analysis
tic
al
c
N 3 --- cubi
2N --- exponenti
adra
ear
-- qu
N
lin
- --
log
N
N² -
N
log N --- sub-linear
Examples:
14
Bubble sort (N²), Quicksort (N∙logN)
Examples
Cost
sum = 0; -> 1
sum = sum + next; -> 1 Total Cost: 2
Cost
for (int i = 1; i <= n; i++) -> 1 + n+1 + n = 2n+2
sum = sum++; -> n Total Cost: 3n + 2
Cost
k = 0 -> 1
for (int i = 0; i < n; i++) -> 2n+2
for (int j = 0; j < n; j++) -> n(2n+2) = 2n2 +2n
k++; -> n2 Total Cost: 3n2 + 4n + 3`
C Program Using Arrays
• #include <stdio.h>
int main() {
• int arr[100];
• int n, i, searchElement, found = 0;
• // Input size of array
• printf("Enter number of elements: ");
• scanf("%d", &n);
• // Input elements
• printf("Enter %d elements:\n", n);
• for (i = 0; i < n; i++) {
• scanf("%d", &arr[i]);
• // Display elements
• printf("Array elements are: ");
• for (i = 0; i < n; i++) {
• printf("%d ", arr[i]);
• }
• // Search for an element
• printf("\nEnter element to search: ");
• scanf("%d", &searchElement);
• for (i = 0; i < n; i++) {
• if (arr[i] == searchElement) {
• if (found)
• printf("Element %d found at position %d.\n", searchElement, i);
• else
• printf("Element not found in the array.\n");
• return 0;
•}
