-Prokash Barman

qINTRODUCTION TO DATA
STRUCTURES AND ALGORITHMS

qBASIC DATA STRUCTURES

TABLE OF CONTENTS qADVANCED DATA STRUCTURES
qALGORITHMS
qREFERENCES

qAPPENDIX

26/08/24 2
Data Structure & Algorithm
Definition and Importance:

• Data Structures: A way of organizing and storing data

in a computer so that it can be accessed and modified
efficiently.
• Algorithms: A set of instructions or rules designed to
solve a problem or perform a` task.
• Importance: Efficient data structures and algorithms are
INTRODUCTION
crucial for optimizing the usage of computational TO DATA
resources (time and memory). STRUCTURES
AND
Complexity Analysis: ALGORITHMS

• Time Complexity: The amount of time an algorithm

takes to complete.
• Space Complexity: The amount of memory an algorithm
needs to complete.
• Big O Notation: A mathematical notation that describes
the limiting behavior of a function when the argument
tends towards a particular value or infinity.
Data Structure & Algorithm 26/08/24 3
 BASIC DATA STRUCTURES - ARRAYS
Definition and Usage:

• An array is a collection of elements stored at

contiguous memory locations.
• Arrays can be static or dynamic.

Operations:

• Accessing Elements: array[index]

• Insertion: Adding an element at a specific position.
• Deletion: Removing an element from a specific
position.

Time Complexity Analysis:

• Access: O(1)
• Insertion/Deletion
Data Structure & Algorithm at the end: O(1) 26/08/24 4
• Insertion/Deletion at arbitrary positions: O(n)
 array = [1, 2, 3, 4, 5]

Python code print(array[2]) # accessing an element

array.append(6) # insertion at the end
for Array
array.pop(3) # deletion at a specific position
representation

Data Structure & Algorithm 26/08/24 5

 Types:

• Singly Linked List: Each node has a single pointer to the next node.
• Doubly Linked List: Each node has pointers to both the next and
previous nodes.

Operations:

BASIC DATA • Traversal: Visiting each node starting from the head.
• Insertion: Adding a node at the beginning, end, or a specific position.
STRUCTURES - • Deletion: Removing a node from the beginning, end, or a specific
LINKED LISTS position.
• Searching: Finding a node with a specific value.

Time Complexity Analysis:

• Access: O(n)
• Insertion/Deletion at the head: O(1)

Insertion/Deletion at arbitrary positions:

Data Structure & Algorithm 26/08/24 6
• O(n)
 PYTHON CODE: LINKED LISTS

class node: # doubly linked list

def __init__(self, data): class doublynode:
self.data = data def __init__(self, data):
self.next = none self.data = data
self.next = none
# singly linked list self.prev = none
head = node(1)
head.next = node(2) d_head = doublynode(1)
head.next.next = node(3) d_head.next = doublynode(2)
d_head.next.prev = d_head

Data Structure & Algorithm 26/08/24 7

 BASIC DATA STRUCTURES - STACKS
• Last In, First Out (LIFO) means the last
Principle of LIFO: element added to the stack is the first one
to be removed.

• Using arrays: Fixed size, easy to implement.

Implementation: • Using linked lists: Dynamic size, more flexible.

• Push: Adding an element to the top of the stack.

Operations: • Pop: Removing the top element from the stack.
• Peek: Returning the top element without removing it.

Time Complexity • Push, Pop, Peek: O(1)

Analysis:

Data Structure & Algorithm 26/08/24 8

 PYTHON CODE FOR STACK

class stack: else:

def __init__(self): raise indexerror("pop from empty
self.items = [] stack")

def is_empty(self): def peek(self):

return len(self.items) == 0 if not self.is_empty():
return self.items[-1]
def push(self, item):
self.items.append(item) stack = stack()
stack.push(1)
def pop(self): stack.push(2)
if not self.is_empty(): print(stack.peek()) # output: 2
return self.items.pop() print(stack.pop()) # output: 2

Data Structure & Algorithm 26/08/24 9

 Basic Data Structures - Queues
• Principle of FIFO:

• First in, first out (FIFO) means the first element added to the queue is
the first one to be removed.

• Implementation:

• Using arrays: fixed size, easy to implement.

• Using linked lists: dynamic size, more flexible.

• Operations:

• Enqueue: adding an element to the end of the queue.

• Dequeue: removing the front element from the queue.

• Peek: returning the front element without removing it.

• Time complexity analysis:

• Enqueue, dequeue, peek: O(1)

Data Structure & Algorithm 26/08/24 10

 PYTHON CODE FOR QUEUES
class queue: else:
def __init__(self): raise
self.items = [] indexerror("dequeue from empty
queue")
def is_empty(self):
return len(self.items) == 0
def peek(self):
def enqueue(self, item):
if not self.is_empty():
self.items.append(item)
return self.items[0]
def dequeue(self):
queue = queue()
if not self.is_empty():
queue.enqueue(1)
return self.items.pop(0)
queue.enqueue(2)
print(queue.peek()) # output: 1
Data Structure & Algorithm print(queue.dequeue()) # output: 1

26/08/24 11
 Basic data structures - Trees
Binary Trees and Binary Search Trees:

• Binary Tree: A tree where each node has at most two children.
• Binary Search Tree: A binary tree where every node satisfies the BST
property (left child < parent < right child).

Tree Traversal:

• In-order: Left subtree -> root -> right subtree.

• Pre-order: Root -> left subtree -> right subtree.
• Post-order: Left subtree -> right subtree -> root.

Balanced Trees:

• AVL Trees: Self-balancing binary search trees.

• Red-Black Trees: Self-balancing binary search trees.

Time Complexity Analysis:

• Search, Insert, Delete: O(log n) for balanced trees, O(n) for

unbalanced trees.
26/08/24 12
Data Structure & Algorithm
 PYTHON CODE-TREE
class treenode: root.left.left = treenode(4)
def __init__(self, value): root.left.right = treenode(5)
self.value = value
self.left = none # binary search tree
self.right = none bst_root = treenode(4)
def inorder_traversal(node): bst_root.left = treenode(2)
if node: bst_root.right = treenode(6)
inorder_traversal(node.left) bst_root.left.left = treenode(1)
print(node.value) bst_root.left.right = treenode(3)
inorder_traversal(node.right) bst_root.right.left = treenode(5)
# binary tree bst_root.right.right = treenode(7)
root = treenode(1)
root.left = treenode(2) inorder_traversal(root) # output: 4 2 5 1 3
root.right = treenode(3) inorder_traversal(bst_root) # output: 1 2 3 4 5 6 7

Data Structure & Algorithm 26/08/24 13

 Basic Data Structures - Graphs

• Representation:

o Adjacency list: A list where each element represents a node and its neighbors.

o Adjacency matrix: a matrix where matrix[i][j] represents the edge between nodes i and j.

• Graph traversal:

o Breadth-first search (BFS): visits all nodes at the current depth before moving on to nodes at the next depth.

o Depth-first search (dfs): explores as far as possible along each branch before backtracking.

• Applications:

o Shortest path algorithms: dijkstra's, bellman-ford, floyd-warshall.

• Time complexity analysis:

o BFS, DFS: O(V + E), where V is the number of vertices and E is the number of edges.

Data Structure & Algorithm 26/08/24 14

 PYTHON CODE FOR GRAPH
from collections import defaultdict queue.extend(self.graph[vertex])
def dfs(self, start, visited=none):
class graph:
if visited is none:
def __init__(self):
visited = set()
self.graph = defaultdict(list) if start not in visited:
def add_edge(self, u, v): print(start)
visited.add(start)
self.graph[u].append(v)
for neighbor in self.graph[start]:
def bfs(self, start):
self.dfs(neighbor, visited)
visited = set() # example graph

queue = [start] g = graph()

g.add_edge(0, 1)
while queue:
g.add_edge(0, 2)
vertex = queue.pop(0)
g.add_edge(1, 2)
if vertex not in visited: g.add_edge(2, 0)

visited.add(vertex) g.add_edge(2, 3)
g.add_edge(3, 3)
print(vertex)

Data Structure & Algorithm 26/08/24 15

 ADVANCED DATA STRUCTURES - HEAPS
• BINARY HEAPS:

o Definition: A complete binary tree where each node is greater than or

equal to its children (max heap) or less than or equal to its children (min
heap).
o Operations:
§ Insertion: adding an element to the heap.
§ Deletion: removing the root element from the heap.
o Heap sort: an in-place sorting algorithm that uses a binary heap to sort
elements.
o Time complexity analysis:
§ Insertion, deletion: o(log n)
§ Heap sort: o(n log n)

Data Structure & Algorithm 26/08/24 16

 PYTHON CODE FOR BINARY HEAP
def _percolate_down(self, index):
class binaryheap: left_child = 2 * index + 1
def __init__(self): right_child = 2 * index + 2
self.heap = []
smallest = index
def insert(self, value):
if left_child < len(self.heap) and
self.heap.append(value) self.heap[left_child] < self.heap[smallest]:
self._percolate_up(len(self.heap) - 1)
smallest = left_child
def delete(self):
if right_child < len(self.heap) and
if not self.heap: self.heap[right_child] < self.heap[smallest]:
return none
smallest = right_child
if len(self.heap) == 1:
if smallest != index:
return self.heap.pop()
root_value = self.heap[0] self.heap[index], self.heap[smallest]
= self.heap[smallest], self.heap[index]
self.heap[0] = self.heap.pop()
self._percolate_down(smallest)
self._percolate_down(0)
return root_value
def _percolate_up(self, index): heap = binaryheap()
parent = (index - 1) // 2 heap.insert(5)
if index > 0 and self.heap[index] < heap.insert(3)
self.heap[parent]:
heap.insert(10)
self.heap[index], self.heap[parent] =
self.heap[parent], self.heap[index] heap.insert(1)
self._percolate_up(parent) print(heap.delete()) # output: 3
print(heap.heap) # output: [5, 10, 1]

Data Structure & Algorithm 26/08/24 17

 ADVANCED DATA
STRUCTURES - TRIES
• Prefix trees:

o Definition: A tree structure used to

store strings efficiently.

o Applications:

§ Auto-complete features:
suggesting words as you type.

§ Spell checkers: checking the

spelling of words.

Data Structure & Algorithm 26/08/24 18

 PYTHON CODE FOR TRIE
class trienode: def search(self, word):
def __init__(self): node = self.root
self.children = {} for char in word:
self.is_end_of_word = false if char not in node.children:
return false
class trie: node = node.children[char]
def __init__(self): return node.is_end_of_word
self.root = trienode()
trie = trie()
def insert(self, word): trie.insert("hello")
node = self.root trie.insert("world")
for char in word: print(trie.search("hello")) # output: true
if char not in node.children: print(trie.search("world")) # output: true
node.children[char] = trienode() print(trie.search("hel")) # output: false
node = node.children[char]
node.is_end_of_word = true

Data Structure & Algorithm 26/08/24 19

 ADVANCED DATA STRUCTURES - BLOOM FILTERS

• Probabilistic data structures:

o Definition: A space-efficient
probabilistic data structure used to
test whether an element is a member
of a set.

o Applications:

§ Cache systems: checking if an

element is in the cache before
fetching it from memory.

§ Databases: checking if a key is

present before performing a
more expensive operation.

26/08/24 Data Structure & Algorithm 20

 PYTHON CODE FOR BLOOM FILTERS
import mmh3
import bitarray def contains(self, item):
hashes = self._hash(item)
class bloomfilter: for hash_value in hashes:
def __init__(self, size, hash_count): if not self.bit_array[hash_value]:
self.size = size return false
self.hash_count = hash_count return true
self.bit_array = bitarray.bitarray(size)
self.bit_array.setall(0) bloom = bloomfilter(100, 5)
bloom.add("hello")
def _hash(self, item): print(bloom.contains("hello")) # output: true
hashes = [] print(bloom.contains("world")) # output: false
for i in range(self.hash_count): (probabilistic)
hash_value = mmh3.hash(item, i) %
self.size
hashes.append(hash_value)
return hashes

def add(self, item):

hashes = self._hash(item)
for hash_value in hashes:
self.bit_array[hash_value] = true

Data Structure & Algorithm 26/08/24 21

 • Comparison-based sorting:

o Bubble sort:

§ Description: repeatedly steps through the list, compares adjacent

elements, and swaps them if they are in the wrong order.

§ Time complexity: o(n^2) in the worst and average cases, o(n) in the
best case (already sorted).

o Selection sort:

§ Description: divides the input list into two parts: a sorted sublist of

ALGORITHMS elements at the beginning and a sublist of remaining elements.

Time complexity: o(n^2) in all cases.

- SORTING
§

o Insertion sort:

ALGORITHMS § Description: builds the final sorted array one item at a time.

§ Time complexity: o(n^2) in the worst and average cases, o(n) in the
best case (already sorted).

o Merge sort:

§ Description: A divide-and-conquer algorithm that divides the array

into halves, recursively sorts each half, and then merges the sorted
halves.

§ Time complexity: o(n log n) in all cases.

26/08/24 Data Structure & Algorithm 22

 • Quick sort:

o Description: A divide-and-conquer algorithm that selects a 'pivot' element and partitions the
array around the pivot.

o Time complexity: o(n log n) in the average case, o(n^2) in the worst case (poor pivot selection).

• Heap sort:

o Description: uses a binary heap to sort elements.

ALGORITHMS - o Time complexity: o(n log n) in all cases.

SORTING ALGORITHMS • Non-comparison-based sorting:

(CONTD……) o Counting sort:

§ Description: exploits the fact that the input elements are integers in a certain range.

§ Time complexity: o(n + k), where k is the range of input.

o Radix sort:

§ Description: sorts the elements by processing them in a digit-by-digit manner.

§ Time complexity: o(d(n + k)), where d is the number of digits and k is the range of input.

o Bucket sort:

§ Description: works by distributing the elements into a number of buckets.

§ Time complexity: o(n + k) in the average case, o(n^2) in the worst case.

26/08/24 Data Structure & Algorithm 23

 SORTING
TYPES

Data Structure & Algorithm 8/26/24 24

 SORTING COMPARISON

26/08/24 Data Structure & Algorithm 25

 PYTHON CODE FOR DIFFERENT SHORT ALGORITHM
def bubble_sort(arr): arr[j+1] = arr[j]
n = len(arr) j -= 1
for i in range(n): arr[j+1] = key
for j in range(0, n-i-1):
if arr[j] > arr[j+1]: def merge_sort(arr):
arr[j], arr[j+1] = arr[j+1], arr[j] if len(arr) > 1:
mid = len(arr) // 2
def selection_sort(arr): l = arr[:mid]
for i in range(len(arr)): r = arr[mid:]
min_idx = i merge_sort(l)
for j in range(i+1, len(arr)): merge_sort(r)
if arr[j] < arr[min_idx]: i = j = k = 0
min_idx = j while i < len(l) and j < len(r):
arr[i], arr[min_idx] = arr[min_idx], arr[i] if l[i] < r[j]:
arr[k] = l[i]
def insertion_sort(arr): i += 1
for i in range(1, len(arr)): else:
key = arr[i] arr[k] = r[j]
j = i-1 j += 1
while j >= 0 and key < arr[j]: k += 1

26/08/24 Data Structure & Algorithm 26

 PYTHON CODE FOR DIFFERENT SHORT ALGORITHM
while i < len(l): # example usage
arr[k] = l[i] arr = [3, 6, 2, 7, 1]
i += 1 bubble_sort(arr)
k += 1 print("bubble sort:", arr)
while j < len(r):
arr[k] = r[j] arr = [3, 6, 2, 7, 1]
j += 1 selection_sort(arr)
k += 1 print("selection sort:", arr)
def quick_sort(arr):
if len(arr) <= 1: arr = [3, 6, 2, 7, 1]
return arr insertion_sort(arr)
pivot = arr[len(arr) // 2] print("insertion sort:", arr)
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot] arr = [3, 6, 2, 7, 1]
right = [x for x in arr if x > pivot] merge_sort(arr)
return quick_sort(left) + middle + print("merge sort:", arr)
quick_sort(right)
arr = [3, 6, 2, 7, 1]
def heap_sort(arr): print("quick sort:", quick_sort(arr))
import heapq
heap = [] arr = [3, 6, 2, 7, 1]
for element in arr: print("heap sort:", heap_sort(arr))
heapq.heappush(heap, element)
ordered = []
while heap:
ordered.append(heapq.heappop(heap))
return ordered

26/08/24 Data Structure & Algorithm 27

 Linear Search:
• Description: Sequentially checks each element of the list until it finds the
desired element.
ALGORITHMS • Time Complexity: O(n).

- SEARCHING Binary Search:

ALGORITHMS • Description: Searches a sorted array by repeatedly dividing the search
interval in half.
• Time Complexity: O(log n).

Searching in Trees and Graphs:

• BFS:
• Description: Used to search for nodes in a graph by exploring all nodes at
the current depth before moving on to nodes at the next depth.
• Time Complexity: O(V + E).
• DFS:
• Description: Used to search for nodes in a graph by exploring as far as
possible along each branch before backtracking.
• Time Complexity: O(V + E).

26/08/24 Data Structure & Algorithm 28

 SEARCHING ALGORITHM

26/08/24 Data Structure & Algorithm 29

 PYTHON CODE FOR SEARCHING
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# example usage
arr = [1, 3, 5, 7, 9]
print("linear search:", linear_search(arr, 7))
arr = [1, 3, 5, 7, 9]
print("binary search:", binary_search(arr, 7))

26/08/24 Data Structure & Algorithm 30

 ALGORITHMS - GRAPH ALGORITHMS
• Description: starts at the root node and explores all nodes at the current depth before moving on
Breadth-first to nodes at the next depth.
search (BFS): • Time complexity: o(v + e).

• Description: starts at the root node and explores as far as possible along each branch before
Depth-first backtracking.
search (dfs): • Time complexity: o(v + e).

• Dijkstra's algorithm:
• Description: finds the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights.
• Time complexity: o((v + e) log v).
Shortest path • Bellman-ford algorithm:
• Description: finds the shortest paths from a single source vertex to all other vertices in a graph and can handle negative edge weights.
algorithms: • Time complexity: o(ve).
• Floyd-warshall algorithm:
• Description: finds the shortest paths between all pairs of vertices in a graph.
• Time complexity: o(v^3).
• Kruskal's algorithm:
• Description: finds the minimum spanning tree by adding edges in ascending order of their weights.
Minimum • Time complexity: o(e log e).
spanning tree • Prim's algorithm:
• Description: finds the minimum spanning tree by starting with an arbitrary vertex and adding the minimum weight edge that
algorithms: connects a vertex inside the tree with a vertex outside the tree.
• Time complexity: o((v + e) log v).
Data Structure & Algorithm 26/08/24 31
 TIME & SPACE COMPLEXITY FOR GRAPH ALGORITHMS

26/08/24 Data Structure & Algorithm 32

 PYTHON CODE FOR GRAPH ALGORITHM (1)
import heapq

def dijkstra(graph, start):

distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
queue = [(0, start)]
while queue:
current_distance, current_vertex = heapq.heappop(queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances

33
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR GRAPH ALGORITHM (2)
def bellman_ford(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
for _ in range(len(graph) - 1):
for u in graph:
for v, w in graph[u].items():
if distances[u] + w < distances[v]:
distances[v] = distances[u] + w
return distances

def floyd_warshall(graph):
vertices = len(graph)
distances = [[float('infinity') for _ in range(vertices)]
for _ in range(vertices)]
for u in range(vertices):
for v in range(vertices):
if u == v:
distances[u][v] = 0
34
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR GRAPH ALGORITHM (3)

elif graph[u][v] is not none:

distances[u][v] = graph[u][v]
for k in range(vertices):
for i in range(vertices):
for j in range(vertices):
if distances[i][j] > distances[i][k] +
distances[k][j]:
distances[i][j] = distances[i][k] +
distances[k][j]
return distances

def kruskal(graph):
def find_parent(parent, i):
if parent[i] == i:
return i
return find_parent(parent, parent[i])

35
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR GRAPH ALGORITHM (4)
def union(parent, rank, x, y):
xroot = find_parent(parent, x)
yroot = find_parent(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1

result = []
i = 0
e = 0
graph = sorted(graph, key=lambda item: item[2])
parent = {}
rank = {}

36
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR GRAPH ALGORITHM (4)
for node in graph:
parent[node[0]] = node[0]
rank[node[0]] = 0
for node in graph:
parent[node[1]] = node[1]
rank[node[1]] = 0
while e < len(graph) - 1:
u, v, w = graph[i]
i += 1
x = find_parent(parent, u)
y = find_parent(parent, v)
if x != y:
e += 1
result.append([u, v, w])
union(parent, rank, x, y)
return result

37
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR GRAPH ALGORITHM (5)
def prim(graph, start):
mst = []
visited = set()
edges = [(0, start)]
while edges:
weight, u = heapq.heappop(edges)
if u in visited:
continue
visited.add(u)
mst.append((u, weight))
for v, w in graph[u].items():
if v not in visited:
heapq.heappush(edges, (w, v))
return mst

38
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR GRAPH ALGORITHM (6)
# example usage
graph = {
'a': {'b': 1, 'c': 4},
'b': {'a': 1, 'c': 2, 'd': 5},
'c': {'a': 4, 'b': 2, 'd': 1},
'd': {'b': 5, 'c': 1}
}
print("dijkstra's algorithm:", dijkstra(graph, 'a'))
print("bellman-ford algorithm:", bellman_ford(graph, 'a'))
print("floyd-warshall algorithm:", floyd_warshall(graph))

graph = [
('a', 'b', 1),
('a', 'c', 4),
('b', 'c', 2),
('b', 'd', 5),
('c', 'd', 1)
]
39
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR GRAPH ALGORITHM (7)

print("kruskal's algorithm:", kruskal(graph))

graph = {
'a': {'b': 1, 'c': 4},
'b': {'a': 1, 'c': 2, 'd': 5},
'c': {'a': 4, 'b': 2, 'd': 1},
'd': {'b': 5, 'c': 1}
}
print("prim's algorithm:", prim(graph, 'a'))

40
26/08/24 Data Structure & Algorithm
 ALGORITHMS - DYNAMIC PROGRAMMING
Memoization vs. Tabulation: Key Problems: Coin Change Problem: Fibonacci Sequence:

• Memoization: Top-down • Knapsack Problem: • Description: Given a set of • Description: A sequence

approach where you store the • Description: Given a set of coin denominations and a total where each number is the sum
results of subproblems as you items, each with a weight amount of money, find the of the two preceding ones,
compute them. and a value, determine the minimum number of coins usually starting with 0 and 1.
number of each item to needed to make up that
• Tabulation: Bottom-up include in a collection so that amount. • Time Complexity: O(n) for the
approach where you fill a the total weight is less than iterative approach, O(n^2) for
table with the results of or equal to a given limit and • Time Complexity: O(n * the recursive approach without
subproblems. the total value is as large as amount), where n is the number memoization.
possible. of coin denominations.
• Time Complexity: O(nW),
where n is the number of
items and W is the capacity
of the knapsack.
• Longest Common
Subsequence:
• Description: Given two
sequences, find the length of
the longest subsequence
common to both sequences.
• Time Complexity: O(n^2).

26/08/24 Data Structure & Algorithm 41

26/08/24 Data Structure & Algorithm 42
26/08/24 Data Structure & Algorithm 43
Data Structure & Algorithm 8/26/24 44
 PYTHON CODE FOR DYNAMIC PROGRAMMING

def knapsack(values, weights, capacity):

n = len(values)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i - 1] <= w:
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i -
1]], dp[i - 1][w])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][capacity]

45
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR DYNAMIC PROGRAMMING

def longest_common_subsequence(s1, s2):

m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]

46
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR DYNAMIC PROGRAMMING
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1

def fibonacci(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
47
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR DYNAMIC PROGRAMMING
# example usage
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print("knapsack problem:", knapsack(values, weights, capacity))
s1 = "abcb"
s2 = "bdcab"
print("longest common subsequence:", longest_common_subsequence(s1, s2))

coins = [1, 2, 5]
amount = 11
print("coin change problem:", coin_change(coins, amount))
n = 10
print("fibonacci sequence:", fibonacci(n))
48
26/08/24 Data Structure & Algorithm
 ALGORITHMS - GREEDY ALGORITHMS

• Principle:

o Description: make the locally optimal choice at

each stage, with the hope of finding a global
optimum.

o Applications:

§ Huffman coding: compression algorithm that

assigns variable-length codes to input
characters based on their frequencies.

• Fractional knapsack problem: similar to the knapsack

problem but allows for items to be broken into smaller
pieces

26/08/24 Data Structure & Algorithm 49

 GREEDY ALGORITHM
8/26/24 Data Structure & Algorithm
50
 PYTHON CODE FOR GREEDY ALGORITHM
def fractional_knapsack(values, weights, capacity):
items = list(zip(values, weights))
items.sort(key=lambda x: x[0] / x[1], reverse=true)
total_value = 0
for value, weight in items:
if capacity == 0:
break
if weight <= capacity:
total_value += value
capacity -= weight
else:
total_value += value * (capacity / weight)
capacity = 0
return total_value
51
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR GREEDY ALGORITHM
def huffman_coding(freqs):
import heapq
heap = [[freq, [char, ""]] for char, freq in freqs.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

52
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR GREEDY ALGORITHM

# example usage
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print("fractional knapsack problem:", fractional_knapsack(values, weights,
capacity))

freqs = {'a': 5, 'b': 7, 'c': 10, 'd': 15, 'e': 20}

print("huffman coding:", huffman_coding(freqs))

53
26/08/24 Data Structure & Algorithm
Data Structure & Algorithm 26/08/24 54
 ALGORITHMS - BACKTRACKING
• Principle:
o Description: incrementally builds candidates to
the solutions, and abandons a candidate
("backtracks") as soon as it is determined that the
candidate cannot possibly lead to a valid solution.
o Applications:
§ N-queens problem: placing N queens on an
N×N chessboard such that no two queens
attack each other.
§ Sudoku solver: filling a 9×9 grid with digits so
that each column, each row, and each of the
nine 3×3 subgrids that compose the grid
contain all of the digits from 1 to 9.

Data Structure & Algorithm 26/08/24 55

 PYTHON CODE FOR BACKTRACKING ALGORITHM

def is_safe(board, row, col):

for i in range(col):
if board[row][i] == 1:
return false
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return false
for i, j in zip(range(row, len(board), 1), range(col, -1, -1)):
if board[i][j] == 1:
return false
return true

56
26/08/24 Data Structure & Algorithm
 PYTHON CODE FOR BACKTRACKING ALGORITHM
def solve_n_queens(board, col):
if col >= len(board):
return true
for i in range(len(board)):
if is_safe(board, i, col):
board[i][col] = 1
if solve_n_queens(board, col + 1):
return true
board[i][col] = 0
return false

def print_solution(board):
for row in board:
print(" ".join(str(col) for col in row))

# example usage
n = 4
board = [[0] * n for _ in range(n)]
if solve_n_queens(board, 0) == false:
print("solution does not exist")
else:
print_solution(board)

57
26/08/24 Data Structure & Algorithm
 ALGORITHMS - DIVIDE AND CONQUER

• Principle:

o Description: breaks down a problem

into two or more sub-problems of the
same or related type, until these
become simple enough to be solved
directly.

o Applications:

§ Merge sort: A sorting algorithm that

divides the array into halves,
recursively sorts each half, and then
merges the sorted halves.

§ Quick sort: a sorting algorithm that

selects a 'pivot' element and
partitions the array around the
pivot.

Data Structure & Algorithm 26/08/24 58

Data Structure & Algorithm 26/08/24 59
 PYTHON CODE-DIVIDE AND CONQUER
def merge_sort(arr): i += 1
if len(arr) > 1: k += 1
mid = len(arr) // 2 while j < len(r):
l = arr[:mid] arr[k] = r[j]
r = arr[mid:] j += 1
merge_sort(l) k += 1
merge_sort(r)
i = j = k = 0 def quick_sort(arr):
while i < len(l) and j < len(r): if len(arr) <= 1:
if l[i] < r[j]: return arr
arr[k] = l[i] pivot = arr[len(arr) // 2]
i += 1 left = [x for x in arr if x < pivot]
else: middle = [x for x in arr if x ==
arr[k] = r[j] pivot]
j += 1 right = [x for x in arr if x >
pivot]
k += 1 return quick_sort(left) + middle +
while i < len(l): quick_sort(right)
arr[k] = l[i]
Data Structure & Algorithm 26/08/24 60
 PYTHON CODE-DIVIDE AND CONQUER

# example usage
arr = [3, 6, 2, 7, 1]
merge_sort(arr)
print("merge sort:", arr)

arr = [3, 6, 2, 7, 1]
print("quick sort:", quick_sort(arr))

Data Structure & Algorithm 26/08/24 61

 IMPLEMENTATION - PSEUDOCODE AND EXAMPLES

• PSEUDOCODE:
o Description: A high-level
description of an algorithm
that uses a combination of
natural language and
programming language-
like constructs.

Data Structure & Algorithm 26/08/24 62

 PSEUDOCODE

ALGORITHM Binarysearch(arr, target)

BEGIN
left <- 0
right <- length(arr) - 1
WHILE left <= right
mid <- (left + right) / 2
IF arr[mid] == target
RETURN mid
ELSE IF arr[mid] < target
left <- mid + 1
ELSE
right <- mid - 1
END WHILE
RETURN -1
END

Data Structure & Algorithm 26/08/24 63

 PSEUDOCODE-EXAMPLES

def binary_search(arr, target):

left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

# example usage
arr = [1, 3, 5, 7, 9]
print("binary search:", binary_search(arr, 7))

Data Structure & Algorithm 26/08/24 64

 GLOSSARY OF TERMS
• Array: a collection of elements, each identified by an array index.

• Linked list: a linear collection of data elements whose order is not given by their physical
placement in memory.

• Stack: a linear data structure that follows the last in, first out (lifo) principle.

• Queue: a linear data structure that follows the first in, first out (fifo) principle.

• Hash table: a data structure that implements an associative array abstract data type, a
structure that can map keys to values.

• Tree: a hierarchical data structure that consists of nodes connected by edges.

• Graph: a data structure that consists of a set of vertices (or nodes) and a set of edges that
connect pairs of nodes.

• Heap: a specialized tree-based data structure that satisfies the heap property.

Data Structure & Algorithm 26/08/24 65

 GLOSSARY OF TERMS
• Trie: a tree-like data structure that stores a dynamic set or associative array where the keys are
usually strings.

• Bloom filter: a space-efficient probabilistic data structure used to test whether an element is a
member of a set.

• Sorting algorithms: algorithms that put elements of a list in a certain order.

• Searching algorithms: algorithms that find an item in a collection.

• Dynamic programming: a method for solving complex problems by breaking them down into
simpler subproblems.

• Greedy algorithms: algorithms that make the locally optimal choice at each stage with the
hope of finding a global optimum.

• Backtracking: a general algorithm for finding all solutions to some computational problems.

• Divide and conquer: an algorithm design paradigm based on multi-branched recursion.

26/08/24 66
Data Structure & Algorithm
 Additional Resources
• Online courses:
o Coursera
o Edx
o Udemy
• Youtube channels:
o MIT opencourseware
o Computerphile
o Algorythmics
• Interactive platforms:
o Leetcode
o Hackerrank
o Codeforces

• BOOKS:

o "Introduction To Algorithms" By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, And Clifford Stein.
o "Algorithms" By Robert Sedgewick And Kevin Wayne.

Data Structure & Algorithm 26/08/24 67

 THANK YOU

MOBILE: +91 7980208030

EMAIL: pbcse_rs@caluniv.ac.in

Data Structure & Algorithm 8/26/24 68