DATA STRUCTURES

AND ALGORITHMS

Assignment No. 1 · Section A · Program: AI

Course: Data Structures and Algorithms

Instructor: Aisha Farid

Student Name : _______________________________

Roll Number : _______________________________

Submission Date : ___________________________

University of Haripur · Department of Computer Science

 ■ Table of Contents
1. Introduction to Data Structures and Algorithms ...... 3
...................
...................
2. Arrays ........ 4
...................
3. Linked Lists (Singly & Doubly) .. 5
...................
...................
4. Stacks ........ 7
...................
...................
5. Queues ........ 8
...................
6. Trees (Binary Tree & BST) ....... 9
...................
7. Graphs (BFS & DFS) ............. 11
...................
8. Searching Algorithms ............ 13
...................
9. Sorting Algorithms .............. 14
...............
...............
9.1 Bubble Sort .. 14
...............
..............
9.2 Selection Sort 15
...............
..............
9.3 Insertion Sort 16
...............
...............
9.4 Merge Sort ... 17
...............
...............
9.5 Quick Sort ... 18
...................
10. Comparison Tables .............. 19
 ...................
11. Real-World Applications ........ 20
...................
...................
12. Conclusion .. 21
...................
...................
13. References .. 21
 1. Introduction to Data Structures and Algorithms

What is a Data Structure?

A data structure is a systematic way of organising, managing, and storing data in a computer so
that it can be accessed and modified efficiently. Think of it like a filing cabinet: data can be placed in
labelled folders (arrays), chained notebooks (linked lists), or stacked trays (stacks). The choice of
data structure directly affects the speed and memory usage of a program.

What is an Algorithm?
An algorithm is a well-defined, step-by-step procedure for solving a problem or performing a
computation. Algorithms act as recipes: given the same ingredients (input), a correct algorithm
always produces the correct dish (output). Algorithms must be correct, efficient, and unambiguous.

Why Study DSA?

■ Mobile & Web Apps — Maps use graph algorithms; social feeds use queues.
■ Search Engines — Google indexes billions of pages using advanced tree structures.
■ Banking Systems — Transaction histories are maintained using linked lists and stacks.
■ Games — Pathfinding in games like Minecraft uses BFS/DFS on graphs.
■ Artificial Intelligence — Decision trees and priority queues power AI models.
■ Performance — The right data structure can reduce execution time from hours to
milliseconds.

■ Key Insight: A program without an efficient data structure is like a library without a catalogue —
everything exists, but finding or organising it becomes painfully slow.
 2. Arrays

Definition
An array is a collection of elements stored in contiguous memory locations. All elements share
the same data type and are accessed via an integer index starting at 0.

Diagram – 1D Array
Index: 0 1 2 3 4

Value: 10 20 30 40 50

Figure 1: A one-dimensional array of 5 integers.

Real-Life Example
Monthly temperatures recorded by a weather station — each month's reading is stored at a specific
index. Temperature[0] = January, Temperature[11] = December.

Time & Space Complexity

Best Average Worst Space

O(1) Access O(n) Search O(n) Insert/Delete O(n)

Advantages Disadvantages
✔ Constant-time access by index ✘ Fixed size (static arrays)
✔ Simple and easy to implement ✘ Costly insertion/deletion in middle
✔ Cache-friendly (contiguous memory) ✘ Wasted memory if not full
✔ Low memory overhead ✘ Homogeneous — one data type only

Code Example (Python)

# Declare and initialize an array
arr = [10, 20, 30, 40, 50]

# Access element
print(arr[2]) # Output: 30

# Insert at end
[Link](60) # [10, 20, 30, 40, 50, 60]

# Delete element
[Link](20) # [10, 30, 40, 50, 60]

# Linear search
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1

print(linear_search(arr, 40)) # Output: 2

 3. Linked Lists

3.1 Singly Linked List

A singly linked list is a linear data structure where each element (called a node) contains a data
field and a pointer to the next node. Unlike arrays, nodes are not stored in contiguous memory;
they are connected by pointers.

Diagram – Singly Linked List

[10 | [20 | [30 |
[HEAD] → *] → *] → NULL]

Figure 2: Singly linked list with 3 nodes. Each node stores data and a pointer.

Real-Life Example
A music playlist — each song knows the next song to play, but you cannot go back without
restarting from the head (in a singly linked list).

Time & Space Complexity

Best Average Worst Space

O(1) Insert at Head O(n) Search O(n) Delete O(n)

Advantages Disadvantages
✔ Dynamic size — grows/shrinks at runtime ✘ O(n) access — no random access by
✔ Efficient insertion/deletion at head index
✔ No memory wastage (allocates as ✘ Extra memory for storing pointers
needed) ✘ Not cache-friendly
✔ Foundation for stacks and queues ✘ Reverse traversal not possible

Code Example (Python)

 class Node:
def __init__(self, data):
[Link] = data
[Link] = None

class SinglyLinkedList:
def __init__(self):
[Link] = None

def insert_at_head(self, data):

new_node = Node(data)
new_node.next = [Link]
[Link] = new_node

def display(self):
curr = [Link]
while curr:
print([Link], end=' -> ')
curr = [Link]
print('NULL')

ll = SinglyLinkedList()
ll.insert_at_head(30)
ll.insert_at_head(20)
ll.insert_at_head(10)
[Link]() # 10 -> 20 -> 30 -> NULL

3.2 Doubly Linked List

A doubly linked list extends the singly linked list by adding a previous pointer to each node,
enabling traversal in both directions.

Diagram – Doubly Linked List

[* | [* | [* |
NULL 10 | 20 | 30 | →
← *] ■ *] ■ *] NULL

Figure 3: Doubly linked list — each node has two pointers.

Best Average Worst Space

O(1) Insert/Delete at
ends O(n) Search O(n) Worst O(n)

Advantages Disadvantages
✔ Bidirectional traversal ✘ Extra memory for prev pointer
✔ Easy deletion of a given node ✘ More complex implementation
✔ Can be used as deque ✘ Slightly slower due to extra pointer
✔ Better for certain algorithms updates
✘ Higher pointer management overhead
 4. Stacks

Definition
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle — the last
element inserted is the first to be removed. Operations are performed only from one end called the
top.

Diagram – Stack Operations

PUSH 10 PUSH 20 PUSH 30 POP

[10] [20] [30]

[10] [20] [20]

[10] [10]

■■■■■ ■■■■■ ■■■■■ ■■■■■

BASE BASE BASE BASE

Figure 4: Stack operations – PUSH adds to top, POP removes from top.

Real-Life Example
The Undo feature in text editors — every action is pushed onto a stack. Pressing Ctrl+Z pops the
last action and reverts it. Browser back-button history also uses a stack.

Time & Space Complexity

Best Average Worst Space

O(1) Push O(1) Pop O(1) Peek O(n)

Advantages Disadvantages
✔ Very fast O(1) operations ✘ Limited access — only top element
✔ Simple implementation ✘ Can cause stack overflow if unbounded
✔ Useful for recursion and backtracking ✘ Not suitable for random access
✔ Memory-efficient for LIFO scenarios ✘ Inflexible ordering

Code Example (Python)

class Stack:
def __init__(self):
[Link] = []

def push(self, item): # Add to top

[Link](item)

def pop(self): # Remove from top

if not self.is_empty():
return [Link]()
return 'Stack Underflow'

def peek(self): # View top

return [Link][-1] if [Link] else None

def is_empty(self):
return len([Link]) == 0

s = Stack()
[Link](10); [Link](20); [Link](30)
print([Link]()) # 30
print([Link]()) # 20
 5. Queues

Definition
A queue is a linear data structure that follows the FIFO (First In, First Out) principle — the first
element inserted is the first to be removed. Insertion (enqueue) occurs at the rear and removal
(dequeue) at the front.

Diagram – Queue Operations

FRONT → [10] [20] [30] ← REAR

DEQUEUE: [20] [30]

Figure 5: Queue — elements enter at rear and leave at front.

Real-Life Example
A ticket booking queue at a cinema — the first person who arrives is the first served. Similarly, print
spoolers, CPU task scheduling, and network packet handling all use queues.

Time & Space Complexity

Best Average Worst Space

O(1) Enqueue O(1) Dequeue O(1) Peek O(n)

Advantages Disadvantages
✔ FIFO ensures fairness ✘ No random access
✔ Fast O(1) operations ✘ Fixed-size queues may overflow
✔ Ideal for scheduling tasks ✘ Inefficient for priority-based ordering
✔ Foundation of BFS graph algorithm ✘ Requires extra pointers for linked
implementation

Code Example (Python)

from collections import deque

class Queue:
def __init__(self):
self.q = deque()

def enqueue(self, item): # Add to rear

[Link](item)

def dequeue(self): # Remove from front

if self.q:
return [Link]()
return 'Queue Empty'

def front(self):
return self.q[0] if self.q else None

q = Queue()
[Link](10); [Link](20); [Link](30)
print([Link]()) # 10
print([Link]()) # 20
 6. Trees (Binary Tree & BST)

6.1 Binary Tree

A binary tree is a hierarchical data structure where each node has at most two children, referred
to as the left child and right child. The topmost node is the root. Nodes with no children are called
leaves.

Diagram – Binary Tree

[50] ← Root
/ \
[30] [70] ← Internal Nodes
/ \ / \
[20] [40][60] [80] ← Leaf Nodes

Figure 6: A binary tree with height 2.

Key Terminology
Root: Topmost node of the tree.
Height: Number of edges on the longest root-to-leaf path.
Depth: Number of edges from root to a given node.
Leaf: Node with no children.
Subtree: A node and all its descendants.

6.2 Binary Search Tree (BST)

A Binary Search Tree is a binary tree with an ordering property: for every node, all values in its left
subtree are less than the node's value, and all values in its right subtree are greater. This enables
efficient search.

Diagram – BST

[50]
/ \
[30] [70] BST Property:
/ \ \ Left < Node < Right
[20] [40] [80]

Figure 7: Binary Search Tree. Search 40: 50→30→40 (found in 3 steps).

BST Operations
Best Average Worst Space

O(log n) Search* O(log n) Insert* O(log n) Delete* O(n)

*O(n) in worst case (skewed tree).
 Advantages Disadvantages
✔ Efficient O(log n) average operations ✘ Can become unbalanced (skewed)
✔ Sorted traversal via inorder ✘ O(n) worst-case for sorted input
✔ Dynamic insertion and deletion ✘ Complex deletion logic
✔ Foundation of many advanced structures ✘ Requires balancing (AVL, Red-Black) for
guarantees

Code Example – BST Search (Python)

class BSTNode:
def __init__(self, key):
[Link] = key
[Link] = None
[Link] = None

def insert(root, key):

if root is None:
return BSTNode(key)
if key < [Link]:
[Link] = insert([Link], key)
else:
[Link] = insert([Link], key)
return root

def search(root, key):

if root is None or [Link] == key:
return root
if key < [Link]:
return search([Link], key)
return search([Link], key)

root = None
for v in [50, 30, 70, 20, 40, 80]:
root = insert(root, v)
result = search(root, 40)
print([Link]) # 40
 7. Graphs (BFS & DFS)

Definition
A graph is a non-linear data structure consisting of a set of vertices (nodes) connected by edges.
Graphs can be directed (edges have direction) or undirected. They can be weighted (edges have
costs) or unweighted.

Diagram – Undirected Graph

A ■■■■ B ■■■■ C
| |
D ■■■■ E

Vertices: {A, B, C, D, E}
Edges: {A-B, B-C, A-D, D-E, B-E}

Figure 8: An undirected graph with 5 vertices and 5 edges.

7.1 Breadth-First Search (BFS)

BFS explores a graph level by level, starting from a source vertex and visiting all neighbours before
moving to their neighbours. It uses a queue. Starting from A in Figure 8: A → B → D → C → E.

7.2 Depth-First Search (DFS)

DFS explores a graph by going as deep as possible along each branch before backtracking. It
uses a stack (or recursion). Starting from A in Figure 8: A → B → C → E → D.

BFS vs DFS Comparison

Feature BFS DFS

Data Structure Used Queue Stack / Recursion

Traversal Order Level by level Deep branch first

Shortest Path Yes (unweighted) No

Memory Usage More (stores all neighbours) Less (one path at a time)

Time Complexity O(V + E) O(V + E)

Best For Shortest path, Level order Cycle detection, Topological sort

Code Example – BFS & DFS (Python)

 from collections import deque

graph = {
'A': ['B', 'D'],
'B': ['A', 'C', 'E'],
'C': ['B'],
'D': ['A', 'E'],
'E': ['B', 'D']
}

# BFS – uses a queue

def bfs(graph, start):
visited, queue = set(), deque([start])
[Link](start)
while queue:
node = [Link]()
print(node, end=' ')
for nb in graph[node]:
if nb not in visited:
[Link](nb); [Link](nb)

# DFS – uses recursion

def dfs(graph, node, visited=None):
if visited is None: visited = set()
[Link](node); print(node, end=' ')
for nb in graph[node]:
if nb not in visited:
dfs(graph, nb, visited)

print('BFS:', end=' '); bfs(graph, 'A') # A B D C E

print('\nDFS:', end=' '); dfs(graph, 'A') # A B C E D

Real-Life Example
BFS: Finding the shortest route between two cities on Google Maps. DFS: Solving a maze or puzzle
by exploring each path fully before backtracking.

Best Average Worst Space

O(V2) Adjacency
O(V+E) BFS O(V+E) DFS Matrix O(V+E)
 8. Searching Algorithms

8.1 Linear Search

Linear search checks each element one by one from the beginning until the target is found or the
list is exhausted. It works on both sorted and unsorted data.

Best Average Worst Space

O(1) O(n) O(n) O(1)

8.2 Binary Search

Binary search works on a sorted array by repeatedly dividing the search interval in half. If the target
is less than the middle, search the left half; otherwise search the right half.

Diagram – Binary Search

Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] Target: 23

Step 1: low=0, high=9, mid=4 → arr[4]=16 < 23 → search RIGHT

Step 2: low=5, high=9, mid=7 → arr[7]=56 > 23 → search LEFT
Step 3: low=5, high=6, mid=5 → arr[5]=23 = 23 → FOUND at index 5!

Figure 9: Binary search reduces the search space by half each step.

Best Average Worst Space

O(1) iterative / O(log

O(1) O(log n) O(log n) n) recursive

Feature Linear Search Binary Search

Input Requirement Unsorted or sorted Must be sorted

Time Complexity O(n) O(log n)

Space Complexity O(1) O(1) iterative

Best For Small or unsorted data Large sorted datasets

Code Example (Python)

# Binary Search – Iterative
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

print(binary_search(arr, 23)) # Output: 5
print(binary_search(arr, 99)) # Output: -1
 9. Sorting Algorithms

9.1 Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong
order. Each pass 'bubbles up' the largest unsorted element to its correct position.

Trace – Bubble Sort on [64, 34, 25, 12, 22]

Pass 1: [34, 25, 12, 22, 64] (64 bubbled to end)

Pass 2: [25, 12, 22, 34, 64] (34 bubbled)
Pass 3: [12, 22, 25, 34, 64] (25 bubbled)
Pass 4: [12, 22, 25, 34, 64] (no swaps → sorted!)

Best Average Worst Space

O(n) O(n2) O(n2) O(1)

Advantages Disadvantages
✔ Simple to understand and implement ✘ Very slow for large datasets O(n²)
✔ In-place (no extra memory) ✘ Too many comparisons
✔ Stable sort ✘ Not used in practice

def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # Early exit if already sorted
break
return arr

print(bubble_sort([64, 34, 25, 12, 22])) # [12, 22, 25, 34, 64]

9.2 Selection Sort

Selection sort divides the array into sorted and unsorted regions. It repeatedly finds the minimum
element in the unsorted region and swaps it to the beginning of the unsorted region.

Array: [29, 10, 14, 37, 13]

Pass 1: find min=10, swap with 29 → [10, 29, 14, 37, 13]
Pass 2: find min=13, swap with 29 → [10, 13, 14, 37, 29]
Pass 3: find min=14, already in place → [10, 13, 14, 37, 29]
Pass 4: find min=29, swap with 37 → [10, 13, 14, 29, 37]

Best Average Worst Space

O(n2) O(n2) O(n2) O(1)

Advantages Disadvantages
✔ In-place — O(1) extra space ✘ Always O(n²) — no early exit
✔ Fewer swaps than bubble sort ✘ Not stable (can disrupt equal elements)
✔ Simple logic ✘ Slow on large inputs
✔ Works on small datasets ✘ Not adaptive

def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr

9.3 Insertion Sort

Insertion sort builds a sorted array one element at a time by inserting each new element into its
correct position within the already-sorted portion. Similar to sorting playing cards in hand.

Best Average Worst Space

O(n) O(n2) O(n2) O(1)

Advantages Disadvantages
✔ O(n) on nearly sorted data ✘ O(n²) on reverse-sorted data
✔ Stable and in-place ✘ Not suitable for large datasets
✔ Simple to implement ✘ More shifts than comparisons
✔ Online — can sort a stream of data ✘ Slower than merge/quick for large n

def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr

print(insertion_sort([5, 3, 8, 1, 2])) # [1, 2, 3, 5, 8]

9.4 Merge Sort
Merge sort uses the divide-and-conquer technique: it recursively splits the array into halves, sorts
each half, and then merges the two sorted halves into a single sorted array.

[38, 27, 43, 3, 9, 82, 10]

/ \
[38, 27, 43] [3, 9, 82, 10]
/ \ / \
[38] [27, 43] [3, 9] [82, 10]
/ \ / \ / \
[27] [43] [3] [9] [82] [10]
\ / \ / \ /
[27, 43] [3, 9] [10, 82]
\ / /
[27, 38, 43] [3, 9, 10, 82]
\ /
[3, 9, 10, 27, 38, 43, 82]

Figure 10: Merge sort splits and merges recursively.

Best Average Worst Space

O(n log n) O(n log n) O(n log n) O(n)

Advantages Disadvantages
✔ Guaranteed O(n log n) ✘ O(n) extra space needed
✔ Stable sort ✘ Slower for small arrays than insertion sort
✔ Excellent for linked lists ✘ Recursive overhead
✔ Parallelisable — divide independently ✘ Not in-place

def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)

def merge(left, right):

result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
[Link](left[i]); i += 1
else:
[Link](right[j]); j += 1
[Link](left[i:]); [Link](right[j:])
return result

print(merge_sort([38, 27, 43, 3])) # [3, 27, 38, 43]

9.5 Quick Sort

Quick sort selects a pivot element and partitions the array into two subarrays: elements smaller
than the pivot (left) and elements greater (right). It then recursively sorts both subarrays.

Array: [10, 80, 30, 90, 40, 50, 70] Pivot = 70 (last element)

Partition: [10, 30, 40, 50] | 70 | [80, 90]

Recurse LEFT: [10, 30, 40, 50] Pivot=50 → [10,30,40]|50|[]
Recurse RIGHT: [80, 90] Pivot=90 → [80]|90|[]
Result: [10, 30, 40, 50, 70, 80, 90]

Best Average Worst Space

O(n log n) O(n log n) O(n2) bad pivot O(log n)

Advantages Disadvantages
✔ Very fast in practice O(n log n) ✘ O(n²) worst case (sorted input, bad pivot)
✔ In-place — minimal extra memory ✘ Not stable
✔ Cache-friendly ✘ Recursive — risk of stack overflow
✔ Widely used in system libraries (e.g., C++ ✘ Performance depends on pivot selection
std::sort)

def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1]
left = [x for x in arr[:-1] if x <= pivot]
right = [x for x in arr[:-1] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)

print(quick_sort([10, 80, 30, 90, 40, 50, 70]))

# [10, 30, 40, 50, 70, 80, 90]
 10. Comparison Tables

10.1 Sorting Algorithms Comparison

Algorithm Best Average Worst Space Stable?

Bubble Sort O(n) O(n²) O(n²) O(1) Yes

Selection Sort O(n²) O(n²) O(n²) O(1) No

Insertion Sort O(n) O(n²) O(n²) O(1) Yes

Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes

Quick Sort O(n log n) O(n log n) O(n²) O(log n) No

10.2 Data Structures Comparison

Structure Access Search Insertion Deletion Space

Array O(1) O(n) O(n) O(n) O(n)

Linked List O(n) O(n) O(1)* O(1)* O(n)

Stack O(n) O(n) O(1) O(1) O(n)

Queue O(n) O(n) O(1) O(1) O(n)

BST (avg) O(log n) O(log n) O(log n) O(log n) O(n)

Graph (adj list) O(V+E) O(V+E) O(1) O(E) O(V+E)

* At head/tail with pointer; O(n) for arbitrary position.

10.3 Stack vs Queue

Feature Stack Queue

Principle LIFO FIFO

Insert End Top Rear

Remove End Top Front

Use Case Undo, Recursion Scheduling, BFS

Real Example Browser Back Printer Queue

11. Real-World Applications of DSA

■■ Navigation (Maps) Google Maps models roads as a weighted graph. Dijkstra's

Tech: Graphs + algorithm finds the shortest path between two locations by
Dijkstra/BFS exploring vertices with minimum cumulative cost first.

Search engines use Trie data structures (a prefix tree) for

■ Search Engines
auto-complete suggestions and inverted index hash maps to
Tech: Trees + Hashing
retrieve pages containing search terms in milliseconds.

Facebook's friend-of-friend recommendations use BFS on a

■ Social Networks
graph where users are vertices and friendships are edges.
Tech: Graphs + BFS
LinkedIn uses similar techniques for '2nd-degree connections'.

ATM transaction processing uses queues (FIFO) to serve

■ Banking Systems
customers fairly. Undo features in banking apps use stacks to
Tech: Queues + Stacks
roll back recent transactions.

■ Databases Relational databases (MySQL, PostgreSQL) use B-Tree

Tech: B-Trees + indexes to support fast range queries in O(log n) time. Hash
Hashing indexes are used for exact-match lookups in O(1).

■ Artificial Intelligence A* search algorithm — used in robot navigation and game AI —

Tech: Graphs + Priority is a graph traversal algorithm that uses a priority queue
Queues (min-heap) to always explore the most promising path.

■ Bioinformatics DNA sequence alignment uses dynamic programming (similar

Tech: Dynamic to merge sort's divide approach) to find the best match between
Programming + Arrays genetic sequences efficiently.

■ Operating Systems CPU schedulers use priority queues to determine which

Tech: Queues + Linked process runs next. Memory management uses linked lists to
Lists track free and allocated memory blocks.
 12. Conclusion
Data Structures and Algorithms form the intellectual backbone of all software engineering. The
choice of an appropriate data structure and algorithm can be the difference between an application
that scales to millions of users and one that crawls to a halt.

Key Takeaways
✔ Arrays give fast random access but are inflexible in size — best for fixed-size, indexed data.
✔ Linked Lists offer dynamic sizing and fast insertion/deletion at the cost of random access.
✔ Stacks and Queues are specialised structures that enforce access order — LIFO and FIFO
respectively.
✔ Trees, particularly BSTs, provide efficient ordered storage and O(log n) operations on
average.
✔ Graphs model relationships in the real world; BFS and DFS are fundamental traversal
strategies.
✔ Searching: Binary search is exponentially faster than linear search on sorted data.
✔ Sorting: For large datasets, always prefer O(n log n) algorithms (Merge Sort, Quick Sort).
✔ No single data structure or algorithm is universally best — the right choice depends on the
problem constraints.

■ Final Thought: Mastering DSA is not about memorising code — it is about developing the
ability to analyse a problem, identify its computational constraints, and select the most efficient
tool from your algorithmic toolkit.
13. References

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to
Algorithms (4th ed.). MIT Press.

[2] Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.

[3] Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and
Algorithms in Python. Wiley.

[4] GeeksforGeeks. (2024). Data Structures and Algorithms. Retrieved from

[Link]

[5] Khan Academy. (2024). Algorithms. Retrieved from

[Link]

[6] Skiena, S. S. (2020). The Algorithm Design Manual (3rd ed.). Springer.

This assignment was prepared for the Data Structures and Algorithms course — University of Haripur. All code
examples are for educational purposes. Submission Date: _______________