CS301 – Data Structure final term short lectures

Lecture 19: Abstract Data Types (ADT)

Abstract Data Types (ADT) An ADT is like a contract or blueprint that specifies what a data structure does, not how it does it. It defines the operations (like add, remove, search) and the rules for using them, but leaves the implementation details hidden. For example, a “List ADT” tells you that you can insert and delete items, but doesn’t specify whether it uses arrays or linked lists internally. This separation allows you to change the implementation without affecting code that uses the ADT.

Review of Linear Data Structures Linear data structures organize elements in a sequential order where each element has exactly one predecessor and one successor (except the first and last). Think of them as a single lane of traffic – you can only move forward or backward. Examples include arrays (indexed sequence), lists (ordered collection), stacks (restricted access at one end), and queues (restricted access at both ends).

Introduction to Lists A list is an ordered collection of elements where position matters. Unlike sets (where order doesn’t matter), lists maintain the sequence in which elements are stored. The first element is at position 0, the second at position 1, and so on. Lists can contain duplicates and allow random access to any element by its position.

List Operations

• Insert: Add a new element at a specific position
• Delete: Remove an element from a specific position
• Search: Find an element by value and return its position
• Update: Change the value at a specific position
• Access: Retrieve the element at a given position

Applications of Lists Lists are everywhere in computing:

• Student records in a class (maintaining enrollment order)
• Music playlists (songs in specific order)
• Browser history (pages visited in sequence)
• To-do lists (tasks in priority order)
• Shopping carts in e-commerce

Lecture 20: Array-based List Implementation

Array-based List Implementation This implementation uses a regular array as the underlying storage. You maintain a variable to track how many elements are currently in the list. For example, if your array has size 100 but only 25 elements are stored, you keep track that the “logical size” is 25 while the “physical size” is 100.

Basic List Operations

• Adding: Place new element at the end (if space available) or shift elements to make room
• Removing: Delete element and shift remaining elements to fill the gap
• Accessing: Direct access using index (very fast – O(1))
• Searching: Check each element sequentially until found (O(n))

Advantages and Limitations of Arrays Advantages:

• Lightning-fast access to any element using its index
• Memory efficient (no extra pointers needed)
• Cache-friendly (elements stored contiguously in memory)

Limitations:

• Fixed size (must know maximum size in advance, or resize which is expensive)
• Insertion/deletion in middle is costly (must shift all subsequent elements)
• Wasted memory if array is much larger than needed

Static vs Dynamic Lists

• Static Lists: Size fixed at creation time. Simple but inflexible. If you create an array of 100 elements, it stays 100 forever.
• Dynamic Lists: Can grow/shrink during program execution. When the array fills up, allocate a larger array (typically double the size), copy all elements over, and delete the old array. Languages like Python and Java do this automatically with their list/ArrayList classes.

Lecture 21: Linked List Concept

Linked List Concept Instead of storing elements in contiguous memory like arrays, linked lists store each element in a separate “node” that contains the data and a reference (pointer) to the next node. It’s like a scavenger hunt where each clue tells you where to find the next clue. The list only needs to remember where the first node (head) is located.

Singly Linked List Each node has two parts: the data field and a single “next” pointer. The chain only goes one direction – forward. The last node’s “next” pointer is NULL, indicating the end of the list.

Node Structure

Node:
  - data: stores the actual value (could be int, string, object, etc.)
  - next: pointer/reference to the next node in the sequence

For example, a node storing the number 42 might look like:

[data: 42 | next: →] → [data: 17 | next: →] → [data: 99 | next: NULL]

Traversal and Basic Operations

• Traversal: Start at the head, follow the “next” pointers until you reach NULL. You must visit nodes sequentially – no random access.
• Insert: Create a new node, adjust pointers to include it in the chain
• Delete: Adjust pointers to bypass the node being removed, then deallocate its memory

Lecture 22: Insertion in Linked Lists

Insertion in Linked Lists

1. Insert at Beginning:
   • Create new node
   • Set its “next” to point to current head
   • Update head to point to new node
   • Time: O(1) – very fast!
2. Insert at End:
   • Traverse to the last node
   • Create new node
   • Set last node’s “next” to point to new node
   • Time: O(n) – must traverse entire list
3. Insert in Middle:
   • Traverse to the node before desired position
   • Create new node
   • Set new node’s “next” to point to the next node
   • Set previous node’s “next” to point to new node
   • Time: O(n) – must traverse to position

Deletion in Linked Lists

• Delete from Beginning: Update head to point to second node, deallocate first node. O(1)
• Delete from End: Traverse to second-to-last node, set its “next” to NULL, deallocate last node. O(n)
• Delete from Middle: Traverse to node before target, update its “next” to skip the target node, deallocate target. O(n)

Searching in Linked Lists Start at head and compare each node’s data with the search value. If found, return the node or its position. If you reach NULL, the element doesn’t exist. Always O(n) time – no shortcuts available.

Comparison with Array Lists

Aspect	Array List	Linked List
Access time	O(1)	O(n)
Insert/Delete at beginning	O(n)	O(1)
Insert/Delete at end	O(1)	O(n) or O(1) with tail pointer
Memory	Contiguous, fixed size	Scattered, dynamic
Extra space	None	Pointers in each node

Lecture 23: Doubly Linked Lists

Doubly Linked Lists Each node has THREE parts: data, a “next” pointer, and a “prev” (previous) pointer. This allows traversal in both directions.

NULL ← [prev | data: 5 | next] ↔ [prev | data: 10 | next] ↔ [prev | data: 15 | next] → NULL

Benefits:

• Can traverse backward easily
• Deletion is easier (can access previous node directly)
• More flexible for certain operations

Drawback: Extra memory for the additional pointer

Circular Linked Lists The last node’s “next” pointer points back to the first node instead of NULL, forming a circle. There’s no natural “end” to the list.

[data: 1 | next] → [data: 2 | next] → [data: 3 | next] ↰
     ↑_______________________________________________|

Useful for:

• Round-robin scheduling (taking turns)
• Circular buffers
• Music playlists that loop

Operations on Linked Lists All standard operations (insert, delete, search, traverse) work similarly to singly linked lists but with adjustments for the additional pointer in doubly linked lists. For circular lists, you must be careful to detect when you’ve completed a full circle.

Applications of Linked Lists

• Music Players: Doubly linked for next/previous song navigation
• Undo/Redo: Each action is a node; undo moves backward, redo moves forward
• Memory Management: Operating systems use linked lists to track free memory blocks
• Browser History: Backward/forward buttons use doubly linked lists
• Image Viewers: Navigate through photos

Lecture 24: Stack ADT

Stack ADT A stack is a Last-In-First-Out (LIFO) data structure. Imagine a stack of plates: you can only add to the top or remove from the top. The plate you added last is the first one you’ll remove. This restricted access pattern is what makes stacks powerful.

Stack Operations

1. Push: Add an element to the top of the stack
2. Pop: Remove and return the top element
3. Peek/Top: View the top element without removing it
4. isEmpty: Check if stack is empty
5. isFull: Check if stack is full (for array implementation)

Array Implementation of Stack Use an array and a “top” variable that tracks the index of the top element.

• Start with top = -1 (empty stack)
• Push: Increment top, then add element at array[top]
• Pop: Return array[top], then decrement top
• Very efficient: all operations are O(1)

Applications of Stack

• Function Calls: When function A calls function B, A’s state is pushed onto the call stack
• Undo Operations: Each action pushed onto stack; undo pops the last action
• Expression Evaluation: Convert infix to postfix, evaluate postfix expressions
• Browser Back Button: Each visited page is pushed; back button pops
• Syntax Checking: Matching parentheses, brackets, braces in code

Lecture 25: Linked List Implementation of Stack

Linked List Implementation of Stack Instead of arrays, use a linked list where the head serves as the top of the stack.

• Push: Insert new node at head (O(1))
• Pop: Remove head node (O(1))
• Advantage: No size limit, grows dynamically
• Disadvantage: Extra memory for pointers

Stack Overflow and Underflow

• Overflow: Trying to push when stack is full (only in array implementation with fixed size)
• Underflow: Trying to pop from an empty stack Both are error conditions that must be checked before operations.

Expression Evaluation Stacks are essential for evaluating mathematical expressions programmatically. Computers don’t naturally understand operator precedence like humans do.

Infix, Prefix, and Postfix Three ways to write expressions:

1. Infix: Operator between operands (how humans write): 3 + 4
2. Prefix (Polish notation): Operator before operands: + 3 4
3. Postfix (Reverse Polish): Operator after operands: 3 4 +

Example: (3 + 4) * 5

• Infix: (3 + 4) * 5
• Prefix: * + 3 4 5
• Postfix: 3 4 + 5 *

Postfix is easiest for computers to evaluate using a stack:

• Scan left to right
• If operand, push onto stack
• If operator, pop two operands, apply operation, push result back
• Final stack value is the answer

Lecture 26: Recursion

Recursion A function that calls itself to solve a problem by breaking it into smaller, similar subproblems. Every recursive function needs:

1. Base case: The stopping condition (prevents infinite recursion)
2. Recursive case: The function calls itself with a simpler input

Example – Factorial:

factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1  ← base case

Stack Behavior in Recursion Each recursive call is pushed onto the call stack with its own set of local variables and parameters. When a base case is reached, calls start returning and popping off the stack in reverse order.

Recursive Algorithms Common recursive problems:

• Factorial: n! = n × (n-1)!
• Fibonacci: fib(n) = fib(n-1) + fib(n-2)
• Tree Traversal: Process current node, recursively process children
• Divide and Conquer: Merge sort, quick sort, binary search

Pros and Cons of Recursion

Pros:

• Code is often cleaner and more intuitive
• Natural fit for hierarchical problems (trees, graphs)
• Elegant solutions to complex problems

Cons:

• Uses more memory (stack frames for each call)
• Slower than iteration (function call overhead)
• Risk of stack overflow if recursion is too deep
• Can be harder to debug

Lecture 27: Queue ADT

Queue ADT A First-In-First-Out (FIFO) data structure. Like a line at a coffee shop: the first person to arrive is the first person served. Elements are added at one end (rear) and removed from the other end (front).

Queue Operations

1. Enqueue: Add element to the rear of the queue
2. Dequeue: Remove and return element from the front
3. Front/Peek: View front element without removing
4. isEmpty: Check if queue is empty
5. isFull: Check if queue is full (array implementation)

Linear Queue Implementation Use an array with two pointers:

• front: Index of first element
• rear: Index of last element

Problem: As you enqueue and dequeue, both pointers move forward, eventually running out of space even if the beginning of the array is empty.

Applications of Queue

• Job Scheduling: Print queue, CPU task scheduling
• Customer Service: First customer in line gets served first
• Breadth-First Search: Graph/tree traversal
• Buffering: Keyboard buffer, network packets
• Simulations: Modeling real-world waiting lines

Lecture 28: Circular Queue

Circular Queue Solves the linear queue problem by treating the array as circular – when you reach the end, wrap around to the beginning. Use modulo arithmetic:

• rear = (rear + 1) % array_size
• front = (front + 1) % array_size

This maximizes space utilization in the array.

Array Implementation of Circular Queue Maintain front and rear pointers. When rear reaches the end of the array, it wraps to index 0 if there’s space. Need to distinguish between full and empty states (both have front == rear).

Deque (Double Ended Queue) Pronounced “deck” – a generalized queue where you can insert and delete from BOTH ends.

Operations:

• insertFront()
• insertRear()
• deleteFront()
• deleteRear()

More flexible than regular queues but more complex to implement.

Priority Queue Elements have associated priorities. Higher priority elements are dequeued first, regardless of arrival order. Like an emergency room – critical patients seen before non-critical ones.

Implementation options:

• Unordered list: Easy insert O(1), hard dequeue O(n)
• Ordered list: Hard insert O(n), easy dequeue O(1)
• Heap: Both operations O(log n) – best choice

Lecture 29: Linked List Implementation of Queue

Linked List Implementation of Queue Use a linked list with two pointers:

• front: Points to first node (for dequeue)
• rear: Points to last node (for enqueue)

Advantages:

• No size limit, dynamic growth
• No wasted space
• Both enqueue and dequeue are O(1)

Comparison of Stack and Queue

Aspect	Stack (LIFO)	Queue (FIFO)
Order	Last In, First Out	First In, First Out
Insertion	Top only	Rear only
Deletion	Top only	Front only
Real-world analogy	Stack of plates	Line at store
Applications	Function calls, undo	Scheduling, BFS

Applications of Queues

• Traffic Systems: Managing vehicle flow at intersections
• CPU Scheduling: Operating systems use queues for process management
• Breadth-First Search: Level-by-level graph traversal
• Printers: Print jobs queued in order received
• Call Centers: Customers wait in queue for next available agent

Simulation Examples Queues model real-world scenarios:

• Bank Simulation: Customers arrive randomly, queue for tellers
• Supermarket: Multiple checkout lines, minimizing wait time
• Airport Security: Passengers queue for screening These simulations help optimize resource allocation.

Lecture 30: Trees Introduction

Trees Introduction A tree is a hierarchical, non-linear data structure with a root node and child nodes forming parent-child relationships. No cycles allowed – there’s exactly one path between any two nodes.

Tree Terminology

• Root: The topmost node (no parent)
• Node: An element in the tree
• Leaf: A node with no children
• Parent: Node that has children
• Child: Node descended from another node
• Siblings: Nodes with the same parent
• Height: Longest path from root to any leaf
• Depth/Level: Distance from root (root is at level 0)
• Subtree: A node and all its descendants

Binary Trees Each node has at most two children, typically called “left child” and “right child”. This restriction makes binary trees simpler to implement and analyze.

Tree Traversals Systematic ways to visit every node exactly once:

1. Preorder: Root → Left subtree → Right subtree
2. Inorder: Left subtree → Root → Right subtree
3. Postorder: Left subtree → Right subtree → Root

These are recursive definitions – you apply the same pattern to each subtree.

Lecture 31: Binary Tree Traversal Algorithms

Binary Tree Traversal Algorithms Implementations of the three main traversal strategies, typically done recursively.

Preorder Traversal Process root first, then recursively traverse left subtree, then right subtree.

Example tree:

      1
     / \
    2   3
   / \
  4   5

Preorder: 1, 2, 4, 5, 3

Use case: Creating a copy of the tree, prefix expression evaluation

Inorder Traversal Recursively traverse left subtree, process root, then traverse right subtree.

Same tree – Inorder: 4, 2, 5, 1, 3

Special property: For a Binary Search Tree, inorder traversal gives elements in sorted order!

Postorder Traversal Recursively traverse left subtree, right subtree, then process root.

Same tree – Postorder: 4, 5, 2, 3, 1

Use case: Deleting a tree (delete children before parent), postfix expression evaluation

Lecture 32: Binary Search Tree (BST)

Binary Search Tree (BST) A binary tree with a special ordering property:

• All values in left subtree < node value
• All values in right subtree > node value
• This property holds for every node in the tree

BST Properties

• Enables efficient searching (like binary search on arrays)
• Inorder traversal produces sorted sequence
• Average case operations: O(log n)
• Worst case (unbalanced): O(n)

Insertion in BST Start at root, compare new value:

• If less than current node, go left
• If greater than current node, go right
• Repeat until you find an empty spot
• Insert new node there

Always maintains BST property.

Searching in BST Similar to insertion:

• Start at root
• If target equals current node, found!
• If target < current node, search left subtree
• If target > current node, search right subtree
• If you reach NULL, element doesn’t exist

Much faster than linear search in linked lists.

Lecture 33: Deletion in Binary Search Tree

Deletion in Binary Search Tree Three cases when deleting a node:

1. Node has no children (leaf): Simply remove it
2. Node has one child: Replace node with its child
3. Node has two children:
   • Find inorder successor (smallest value in right subtree) OR inorder predecessor (largest value in left subtree)
   • Replace node’s value with successor/predecessor
   • Delete the successor/predecessor (which will have at most one child)

Must maintain BST property after deletion.

BST Traversal Same as regular binary tree traversals (preorder, inorder, postorder), but inorder traversal is particularly useful since it visits nodes in sorted order.

Advantages and Limitations of BST

Advantages:

• Fast search, insert, delete (average O(log n))
• Sorted data automatically maintained
• Efficient range queries

Limitations:

• Can become unbalanced (degenerating to a linked list)
• No guaranteed O(log n) performance
• Self-balancing trees (AVL, Red-Black) solve this but add complexity

Applications of Trees

• Databases: Index structures for fast lookups
• File Systems: Directory hierarchies
• Compilers: Syntax trees for parsing code
• Decision Making: Decision trees in AI/ML
• Autocomplete: Trie data structures
• Networking: Routing tables

Lecture 34: Heap Data Structure

Heap Data Structure A complete binary tree (all levels filled except possibly the last, which fills left to right) with a heap property.

Min Heap and Max Heap

• Min Heap: Every parent ≤ its children (smallest element at root)
• Max Heap: Every parent ≥ its children (largest element at root)

Note: Heaps are NOT the same as BSTs – siblings are not ordered relative to each other.

Heap Operations

1. Insertion:
   • Add element at next available position (maintaining complete tree)
   • “Bubble up” by swapping with parent until heap property restored
   • Time: O(log n)
2. Deletion (remove root):
   • Replace root with last element
   • “Bubble down” by swapping with smaller child (min heap) until heap property restored
   • Time: O(log n)

Heap Applications

• Priority Queues: Most efficient implementation
• Heap Sort: Sort array in O(n log n) time
• Graph Algorithms: Dijkstra’s, Prim’s algorithm
• Top-K Problems: Find K largest/smallest elements
• Event Scheduling: Next event to process

Lecture 35: Hashing Concepts

Hashing Concepts Hashing maps keys to array indices using a hash function, enabling average O(1) time for search, insert, and delete. Instead of searching through data, compute where it should be.

Hash Tables An array-based data structure that stores key-value pairs. The hash function converts the key into an array index.

Example: Phone book

• Key: Person’s name
• Value: Phone number
• Hash function: Convert name to index

Hash Functions A good hash function should:

• Be deterministic (same input always gives same output)
• Distribute keys uniformly across the array
• Be fast to compute
• Minimize collisions

Common techniques:

• Division method: hash(key) = key % table_size
• Multiplication method
• Folding method
• Mid-square method

Collision Handling A collision occurs when two different keys hash to the same index. Collisions are inevitable (by pigeonhole principle), so we need strategies to handle them.

Lecture 36: Collision Resolution Techniques

Collision Resolution Techniques Two main approaches to handle collisions:

Chaining Each array index stores a linked list of all elements that hash to that index.

• Insert: Add to linked list at computed index
• Search: Hash to index, then search the linked list
• Delete: Hash to index, find and remove from linked list

Pros: Simple, never runs out of space Cons: Extra memory for pointers, performance degrades if chains get long

Open Addressing All elements stored in the array itself. When collision occurs, probe for the next empty slot.

Linear Probing Check next slot: (hash(key) + i) % table_size where i = 0, 1, 2, 3…

Pros: Cache-friendly, simple Cons: Primary clustering (consecutive filled slots)

Quadratic Probing Check slots at quadratic intervals: (hash(key) + i²) % table_size

Reduces clustering but can still have secondary clustering.

Other methods: Double hashing, random probing

Lecture 37: Dictionaries (Map ADT)

Dictionaries (Map ADT) An abstract data type that stores key-value pairs. Each key is unique and maps to exactly one value. Like a real dictionary: words (keys) map to definitions (values).

Dictionary Operations

• Insert/Put: Add a new key-value pair (or update existing key)
• Delete/Remove: Remove a key and its associated value
• Search/Get: Retrieve value associated with a key
• Update: Change value for an existing key
• Contains: Check if a key exists

Implementation Using Hashing Hash tables provide the most efficient dictionary implementation:

• All operations average O(1) time
• Hash the key to find array index
• Store/retrieve value at that location

Alternative implementations:

• Array (unsorted): O(n) search
• Sorted array: O(log n) search, O(n) insert
• BST: O(log n) for all operations

Applications of Dictionaries

• Databases: Indexing records by ID
• Symbol Tables: Compilers map variable names to memory locations
• Caching: Store recently computed results
• Counting: Count word frequencies in text
• Spell Checkers: Dictionary of valid words
• DNS: Domain names to IP addresses

Lecture 38: Table and Dictionaries

Table and Dictionaries Tables are two-dimensional data structures organizing data in rows and columns. Each row is a record, each column is a field/attribute.

Operations on Table ADT

• Insert: Add a new record (row)
• Delete: Remove a record
• Search: Find records matching criteria
• Update: Modify field values in a record
• Sort: Arrange records by some field

Implementation of Table Can use array of records (structures/objects).

Unsorted Sequential Array Records stored in insertion order (no sorting).

• Insert: O(1) – add at end
• Search: O(n) – must check every record
• Delete: O(n) – find then remove

Simple but inefficient for searching.

Sorted Sequential Array Records maintained in sorted order by key field.

• Insert: O(n) – find position, shift elements
• Search: O(log n) – use binary search
• Delete: O(n) – find, remove, shift

Better for search-heavy workloads.

Binary Search Efficient search on sorted data:

1. Check middle element
2. If target equals middle, found!
3. If target < middle, search left half
4. If target > middle, search right half
5. Repeat until found or range exhausted

Time: O(log n) – halves search space each step

Lecture 39: Graph Introduction

Graph Introduction A graph G = (V, E) consists of:

• V: Set of vertices (nodes)
• E: Set of edges (connections between vertices)

Unlike trees, graphs can have cycles and multiple paths between nodes. Most general data structure.

Graph Terminology

• Vertex/Node: A point in the graph
• Edge: Connection between two vertices
• Adjacent: Two vertices connected by an edge
• Degree: Number of edges connected to a vertex
• Path: Sequence of vertices connected by edges
• Cycle: Path that starts and ends at same vertex
• Connected Graph: Path exists between every pair of vertices
• Directed Graph: Edges have direction (A→B ≠ B→A)
• Undirected Graph: Edges have no direction (A-B = B-A)
• Weighted Graph: Edges have associated costs/weights

Graph Representations Two main ways to store graphs in memory:

Adjacency Matrix A 2D array where matrix[i][j] = 1 if edge exists from vertex i to vertex j, otherwise 0.

For weighted graphs: matrix[i][j] = weight of edge

Pros: O(1) edge lookup, good for dense graphs Cons: O(V²) space, wasteful for sparse graphs

Lecture 40: Adjacency List Representation

Adjacency List Representation Each vertex maintains a list of its adjacent vertices.

Array of linked lists: index i stores list of vertices connected to vertex i.

Pros: O(V + E) space, efficient for sparse graphs Cons: O(degree) to check if specific edge exists

Graph Traversal Visiting all vertices of a graph systematically. Two main algorithms:

Breadth First Search (BFS) Explore graph level by level, like ripples in water.

Algorithm:

1. Start at source vertex, mark as visited
2. Add to queue
3. While queue not empty:
   • Dequeue vertex
   • For each unvisited neighbor: mark visited, enqueue

Uses a queue (FIFO). Time: O(V + E)

Applications: Shortest path in unweighted graphs, level-order traversal

Depth First Search (DFS) Explore as deep as possible before backtracking.

Algorithm:

1. Start at source, mark visited
2. For each unvisited neighbor:
   • Recursively visit that neighbor

Uses a stack (recursion or explicit). Time: O(V + E)

Applications: Detecting cycles, topological sorting, path finding

Lecture 41: Applications of BFS and DFS

Applications of BFS and DFS

BFS Applications:

• Shortest path in unweighted graphs
• Social network: Find friends within N connections
• Web crawlers: Discover pages level by level
• Network broadcasting
• GPS navigation (with modifications)

DFS Applications:

• Detecting cycles in graphs
• Topological sorting (ordering tasks with dependencies)
• Solving mazes and puzzles
• Finding connected components
• Path existence checking

Connected Components In an undirected graph, a connected component is a maximal set of vertices where each vertex is reachable from every other vertex in that set.

Finding components:

• Run DFS/BFS from unvisited vertex
• All vertices reached form one component
• Repeat for remaining unvisited vertices

Cycle Detection Undirected Graph: During DFS, if you reach an already-visited vertex (that’s not your parent), cycle exists.

Directed Graph: Use DFS with three states (unvisited, visiting, visited). If you reach a “visiting” vertex, cycle exists (back edge detected).

Graph Traversal Comparison

Aspect	BFS	DFS
Data Structure	Queue	Stack/Recursion
Order	Level by level	Deep first
Memory	More memory	Less memory
Shortest path	Yes (unweighted)	No
Applications	Level-order, shortest path	Cycles, topology

Lecture 42: Shortest Path Problem

Shortest Path Problem Find the minimum-cost path between two vertices in a weighted graph.

Applications: GPS navigation, network routing, flight routes

Dijkstra’s Algorithm Finds shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.

Algorithm:

1. Initialize distances: source = 0, all others = ∞
2. Mark all vertices unvisited
3. Select unvisited vertex with minimum distance
4. For each neighbor, calculate distance through current vertex
5. If this distance is less than known distance, update it
6. Mark current vertex as visited
7. Repeat until all visited or destination reached

Time Complexity: O(V²) with array, O((V + E) log V) with min-heap

Applications of Shortest Path

• GPS/Maps: Finding fastest route
• Network Routing: Packets take shortest path
• Social Networks: Degrees of separation
• Game AI: Pathfinding for characters
• Supply Chain: Optimal delivery routes

Limitations

• Does NOT work with negative edge weights (use Bellman-Ford instead)
• Finds shortest from one source (use Floyd-Warshall for all pairs)
• Can be slow for very large graphs

Lecture 43: Minimum Spanning Tree (MST)

Minimum Spanning Tree (MST) A spanning tree is a subgraph that includes all vertices and is a tree (no cycles). A minimum spanning tree has the minimum total edge weight among all spanning trees.

For example, imagine you need to connect 5 cities with roads. There are many ways to connect them all, but the MST finds the cheapest way to ensure every city is reachable from every other city.

Properties of MST:

• Connects all V vertices (spanning)
• Has exactly V-1 edges (tree property)
• Contains no cycles (tree property)
• Has minimum total edge weight among all possible spanning trees
• May not be unique (multiple MSTs can exist with same total weight)

Prim’s Algorithm Builds MST by expanding from a starting vertex.

Algorithm:

1. Start with any vertex, add to MST
2. Find minimum-weight edge connecting MST to a non-MST vertex
3. Add that edge and vertex to MST
4. Repeat until all vertices included

Greedy approach: Always pick the cheapest edge to expand. Time: O(V²) or O(E log V) with heap

Kruskal’s Algorithm Builds MST by selecting edges in increasing weight order.

Algorithm:

1. Sort all edges by weight
2. For each edge (in order):
   • If adding it doesn’t create a cycle, add to MST
   • Otherwise, skip it
3. Stop when V-1 edges added

Uses Union-Find data structure to detect cycles. Time: O(E log E)

Applications of MST

• Network Design: Connecting cities with minimum cable length
• Circuit Design: Connecting components on chip
• Cluster Analysis: Grouping similar data points
• Approximation Algorithms: For traveling salesman problem

Lecture 44: Sorting Algorithms Overview

Sorting Algorithms Overview Sorting arranges elements in a specific order (ascending or descending). Fundamental operation in computer science.

Bubble Sort Repeatedly compares and swaps adjacent elements if they’re in wrong order. Largest element “bubbles” to the end each pass.

Algorithm:

• Pass through array
• Compare each pair of adjacent elements
• Swap if out of order
• Repeat until no swaps needed

Time: O(n²), Space: O(1) Simple but inefficient for large datasets.

Selection Sort Repeatedly finds minimum element from unsorted portion and places it at the beginning.

Algorithm:

• Find minimum in unsorted portion
• Swap with first unsorted element
• Repeat for remaining unsorted elements

Time: O(n²), Space: O(1) Performs fewer swaps than bubble sort but still slow.

Insertion Sort Builds sorted portion one element at a time by inserting each element into its correct position.

Algorithm:

• Start with first element (considered sorted)
• Take next element
• Find its correct position in sorted portion
• Shift elements and insert
• Repeat for all elements

Time: O(n²) worst case, O(n) best case (already sorted) Efficient for small or nearly sorted datasets.

Lecture 45: Advanced Sorting Techniques

Advanced Sorting Techniques More efficient algorithms for large datasets.

Merge Sort Divide-and-conquer algorithm that splits array in half, recursively sorts each half, then merges them.

Algorithm:

1. Divide array into two halves
2. Recursively sort each half
3. Merge the sorted halves into one sorted array

Merging:

• Compare first elements of each half
• Add smaller to result
• Repeat until all elements merged

Time: O(n log n) always (consistent performance) Space: O(n) – needs extra array for merging Stable sort (preserves order of equal elements)

Quick Sort Divide-and-conquer using a pivot element.

Algorithm:

1. Choose a pivot element
2. Partition: rearrange so elements < pivot are left, > pivot are right
3. Recursively quicksort left and right partitions

Time: O(n log n) average, O(n²) worst case (poor pivot choice) Space: O(log n) for recursion stack Typically fastest in practice, but unstable.

Comparison of Sorting Algorithms

Algorithm	Time (Best)	Time (Average)	Time (Worst)	Space	Stable
Bubble	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	No

Choice depends on: data size, memory constraints, stability requirements, and data characteristics.

This comprehensive breakdown covers all 27 lectures with detailed explanations of each topic!