Laboratory

Design and Analysis of Algorithms

Lab Final Exam

The lab final exam is scheduled for 12 November 2026.

Practical Exam Rules and Regulations

  1. No talking or discussion. Once you are seated in the examination hall, do not communicate with other students, even to ask for a pen or pencil. Any violation will result in the immediate termination of your examination.
  2. No USB devices or internet access. Software that detects USB connections and internet access has been installed on the examination systems. Do not use either. Any violation will result in the immediate termination of your examination.
  3. Binary marking. No partial marks will be awarded.
  4. Solve two out of three questions. You must successfully solve at least two of the three questions to receive full marks.
  5. No error-correction assistance. Neither the teaching assistants (TAs) nor the instructor will correct or debug errors in your code.
Weekly lab assessment structure

Lab sheets

Lab 01

Programming Questions
  1. Write a program to reverse the digits of a number (e.g., 123 → 321).
  2. Remove duplicates from a sorted array and print the new length.
  3. Find the K-th smallest element in an unsorted array using sorting.
  4. Check if a given string is a palindrome. (e.g. NITIN; yes palindrome)
  5. Reverse a string without using built-in functions.
  6. Check if an integer is a palindrome.
  7. Find the second largest number in an array without using sorting.
  8. Given a string, capitalize the first letter of every word.
  9. Count the frequency of each character in a string.
  10. Merge two sorted arrays into a single sorted array.
Lab 02

Sorting and Searching

  1. Insertion Sort with Operation Counting

    Implement insertion sort. Count the number of element comparisons and right shifts.

    Sample Input 
    6
5 2 4 6 1 3
    Sample Output 
    Sorted array: 1 2 3 4 5 6
Comparisons: 12
Shifts: 9

  2. Stable Multi-Key Insertion Sort

    Each student record contains roll number, name, marks, and submission time. Using insertion sort, arrange the records by:

    • Higher marks first.
    • Earlier submission time first.
    • Original order for complete ties.
    Sample Input 
    4
101 Asha 85 10:05
102 Ravi 90 10:10
103 Neha 85 10:05
104 Isha 85 09:55
    Sample Output 
    102 Ravi 90 10:10
104 Isha 85 09:55
101 Asha 85 10:05
103 Neha 85 10:05

  3. Stable Binary Insertion Sort

    Implement binary insertion sort. Use binary search to insert a key after existing equal elements so that the algorithm remains stable. Compare its comparisons and shifts with ordinary insertion sort.

    Sample Input 
    4
4 2 4 1
    Sample Output 
    Sorted array: 1 2 4 4
Binary insertion sort comparisons: 4
Binary insertion sort shifts: 4
Ordinary insertion sort comparisons: 5
Ordinary insertion sort shifts: 4

  4. Find the K Smallest Elements

    Using insertion-style shifting, maintain the k smallest elements in sorted order at the beginning of the array. Do not fully sort the remaining elements, and use only O(1) additional space. When a new value enters the first k positions, place the displaced value at the current position.

    Sample Input 
    6
7 2 5 1 6 3
3
    Sample Output 
    First 3 smallest elements: 1 2 3
Final array: 1 2 3 7 6 5

  5. Bubble Sort and Inversion Count

    Implement bubble sort. Print the array after every pass and verify that the total number of adjacent swaps equals the inversion count of the original array.

    Sample Input 
    3
3 1 2
    Sample Output 
    Pass 1: 1 2 3
Pass 2: 1 2 3
Comparisons: 3
Swaps: 2
Inversions: 2

  6. Ternary Search on a Sorted Array

    Instead of dividing a sorted array into two parts as in binary search, divide it into three nearly equal parts using two middle indices, mid1 and mid2.

    In each iteration:

    • Compare the target with A[mid1].
    • Compare the target with A[mid2].
    • Continue searching in the left, middle, or right third.

    Implement iterative ternary search without using built-in searching functions. Return the target index, or -1 if it is absent. Print the number of target-to-array-element comparisons and analyse its time complexity.

  7. Compare Three Bubble-Sort Versions

    Implement and compare:

    • Standard bubble sort.
    • Bubble sort with a swapped flag.
    • Bubble sort using the last-swap position.

    Report the number of passes, comparisons, and swaps.

    Sample Input 
    5
2 1 3 4 5
    Sample Output 
    Sorted array: 1 2 3 4 5

Standard:
Passes: 4
Comparisons: 10
Swaps: 1

Swapped flag:
Passes: 2
Comparisons: 7
Swaps: 1

Last-swap optimization:
Passes: 1
Comparisons: 4
Swaps: 1

  8. Bidirectional Optimized Bubble Sort

    Implement a stable bidirectional bubble sort. Move the largest element rightward during the forward pass and the smallest element leftward during the backward pass. Reduce the active range after each directional pass.

    Sample Input 
    6
2 3 4 5 6 1
    Sample Output 
    After forward pass: 2 3 4 5 1 6
After backward pass: 1 2 3 4 5 6
Sorted array: 1 2 3 4 5 6

Bidirectional comparisons: 12
Bidirectional swaps: 5
Optimized bubble-sort comparisons: 15

  9. One-Pass Linear Search Statistics

    Using only one left-to-right traversal, find:

    • First and last occurrence of the target.
    • Frequency of the target.
    • Longest consecutive run.
    • Starting index of the longest run.
    Sample Input 
    8
2 5 5 1 5 5 5 3
5
    Sample Output 
    First occurrence: 1
Last occurrence: 6
Frequency: 5
Longest consecutive run: 3
Run starting index: 4
Comparisons: 8

  10. Simple Binary Search

    Implement iterative binary search on a sorted array. Print the target index and the number of comparisons. Return -1 when the target is absent.

    Sample Input 
    5
2 4 6 8 10
8
    Sample Output 
    Target found at index: 3
Comparisons: 2
Lab 03

Recursion

  1. Exponentiation Using Recursion

    Find the exponential xn of a number using recursion. Use the following recurrence:

    xn = { (xn/2)2,  if n is even x · (x⌊n/2⌋)2,  if n is odd

  2. Fibonacci Sequence Using Recursion

    Write a program to generate the Fibonacci sequence up to n terms using recursion.

  3. Reverse a String Using Recursion

    Write a program to reverse a string using recursion.

  4. Palindrome Check Using Recursion

    Write a program to check whether a string is a palindrome using recursion.

  5. Tower of Hanoi

    Write a program to solve the Tower of Hanoi problem using recursion for n disks.

  6. Generate All Permutations

    Write a program to generate all permutations of a given string or array using recursion.

  7. Factorial of a Large Number

    Write a program to compute the factorial of a large number using recursion and display the result.

  8. Recursive Binary Search

    Write a program to perform recursive binary search on a sorted array to find a given element.

  9. Recursive Binary-Tree Traversals

    Write a program to implement recursive tree traversal algorithms—Inorder, Preorder, and Postorder—for a binary tree.

  10. Generate All Subsets

    Write a program to generate all subsets (the power set) of a given array using recursion.

Lab 04

Sorting Algorithms

  1. Selection Sort with Swap Counting

    Write a program to sort an array of n integers using Selection Sort and print the number of swaps performed.

  2. Recursive Merge Sort

    Write a program to sort an array of n integers using recursive Merge Sort and display the sorted array.

  3. In-Place Merge Sort

    Write a program to sort an array of n integers using in-place Merge Sort, without using an additional temporary array, and display the sorted array.

  4. Linked-List Merge Sort

    Create a singly linked list of n nodes and sort it using Linked-List Merge Sort. The implementation must be stable and use O(1) auxiliary space, excluding the recursion stack.

  5. Shell Sort

    Write a program to implement Shell Sort to sort n integers.

  6. Randomized Quick Sort

    Write a program to implement Randomized Quick Sort on an array of n integers and print the pivot index at each partition step.

  7. Counting Sort

    Write a program to implement Counting Sort to sort n non-negative integers, given the maximum key k.

  8. Radix Sort

    Write a program to implement Radix Sort (base 10) to sort n non-negative integers.

  9. Bucket Sort

    Write a program to implement Bucket Sort to sort n real numbers in [0, 1), using Insertion Sort within each bucket.

  10. Hybrid Merge Sort with Insertion Sort

    Write a program to implement a hybrid Merge Sort. When the number of elements in the current subarray is less than or equal to a chosen threshold, sort that subarray using Insertion Sort instead of dividing it further. Otherwise, continue with Merge Sort.

Lab 05

Linked Lists and Stacks

  1. Reverse a Singly Linked List Using Recursion

    Write a program to reverse a singly linked list using recursion.

    Input 
    1 2 3 4 5
    Output 
    5 4 3 2 1

  2. Find the Nth Node from the End

    Write a program to find the nth node from the end of a singly linked list.

    Input 
    List: 10 20 30 40 50
n = 2
    Output 
    40

    Hint: Use two pointers separated by n nodes so that only one traversal is required.

  3. Detect a Loop in a Singly Linked List

    Write a program to detect a loop in a singly linked list.

    Input 
    1 → 2 → 3 → 4 → 5
Make node 5 point to node 3.
    Output 
    Loop detected

    Hint: Use two pointers moving at different speeds. If a loop exists, they will eventually meet.

  4. Find the Middle Element

    Write a program to find the middle element of a singly linked list.

    Input 
    10 20 30 40 50
    Output 
    30

    Hint: Use one pointer moving one node at a time and another moving two nodes at a time.

  5. Add Two Numbers Represented by Linked Lists

    Write a program to add two numbers represented by two linked lists. Each node stores one digit, with digits stored in reverse order.

    Input 
    List 1: 2 → 4 → 3
List 2: 5 → 6 → 4
    Output 
    7 → 0 → 8

    Because 342 + 465 = 807.

    Hint: Traverse both lists simultaneously and maintain a carry. If one list finishes earlier, treat the missing digit as 0.

  6. Check Whether a Singly Linked List Is a Palindrome

    Write a program to check whether a singly linked list is a palindrome. Try to solve it using O(1) extra space.

    Input 
    1 → 2 → 3 → 2 → 1
    Output 
    Palindrome

    Hint: Find the middle using slow and fast pointers, reverse the second half of the list, and compare it with the first half. Do not copy the elements into an array or stack.

  7. Balanced Parentheses Using an Array Stack

    Write a program to check if a string has balanced parentheses using a stack implemented using an array.

    Input 
    {[(a+b) * (c-d)]}
    Output 
    Balanced

    Hint: Push opening brackets onto the stack. For every closing bracket, check whether it matches the most recent opening bracket.

  8. Evaluate a Postfix Expression Using an Array Stack

    Write a program to evaluate a postfix expression using a stack implemented using an array.

    Input 
    5 6 2 + * 12 4 / -
    Output 
    37

    Because 5(6 + 2) − 12/4 = 37.

    Hint: Push operands onto the stack. When an operator appears, pop the top two operands, apply the operator in the correct order, and push the result back.

  9. Find the Intersection Node of Two Singly Linked Lists

    Write a program to find the intersection node of two singly linked lists. Construct the lists by creating a common tail and linking both lists to the same first node of the common tail. The intersection must be determined by node reference/address, not by comparing node values.

    Input 
    Unique part of List A: 1 → 2 → 3
Unique part of List B: 4 → 5
Common tail: 7 → 8 → 9
    Output 
    Intersection node: 7
    Construct 
    1 → 2 → 3 ──┐
             ↓
             7 → 8 → 9
             ↑
4 → 5 ───────┘

  10. Reverse Nodes in Groups of K

    Reverse nodes of a singly linked list in groups of k. Do not change the values stored in the nodes; modify only the links.

    Input 
    List: 1 → 2 → 3 → 4 → 5 → 6
k = 3
    Output 
    3 → 2 → 1 → 6 → 5 → 4
    Additional Input 
    List: 1 → 2 → 3 → 4 → 5
k = 2
    Additional Output 
    2 → 1 → 4 → 3 → 5
Lab 06

Advanced Linked Lists and Binary Search Trees

These problems assess in-place pointer manipulation, cycle handling, BST ordering, and non-recursive tree traversal. Do not create new nodes unless a question explicitly permits it.

  1. Rearrange a Linked List in Zig-Zag Order

    Given a singly linked list L0 → L1 → L2 → … → Ln, rearrange its existing nodes as L0 → Ln → L1 → Ln−1 → L2 → Ln−2 → ….

    • Do not create another linked list or copy node values.
    • Target complexity: O(n) time and O(1) auxiliary space.

  2. Split a Circular Linked List into Two Halves

    Divide a circular singly linked list into two independent circular lists of nearly equal size. If the list contains an odd number of nodes, place the extra node in the first half.

    Input 
    1 → 2 → 3 → 4 → 5 → back to 1
    Expected circular lists 
    First:  1 → 2 → 3 → back to 1
Second: 4 → 5 → back to 4

  3. Delete Nodes Having a Greater Value on Their Right

    Delete every node for which a node containing a greater value exists somewhere to its right. Preserve the relative order of all remaining nodes.

    Input 
    12 → 15 → 10 → 11 → 5 → 6 → 2 → 3
    Output 
    15 → 11 → 6 → 3

    Target: O(n) time.

  4. Find and Remove a Loop Without Losing Nodes

    A singly linked list may contain a cycle. Detect whether a cycle exists, identify the node at which it begins, and remove the cycle so that every original node remains reachable exactly once.

    • Report the cycle-entry node when a loop is present.
    • Required complexity: O(n) time and O(1) auxiliary space.

  5. Merge Nodes Between Special Marker Nodes

    A linked list contains integers, with 0 acting as a separator. Replace the nodes between each pair of consecutive zero markers with one node containing their sum, and remove every zero node.

    Input 
    0 → 3 → 1 → 0 → 4 → 5 → 2 → 0
    Output 
    4 → 11

  6. Find the k-th Smallest Element in a BST Without Creating an Array

    Given the root of a binary search tree and an integer k, find the k-th smallest key. You may not store the complete inorder traversal in an array or list.

    BST 
            8
      /   \
     3     10
    / \      \
   1   6      14
      / \     /
     4   7   13
    Example 
    k = 4
Answer: 6

    Challenge: Use only O(h) auxiliary space, where h is the tree height.

  7. Print a Binary Tree in Spiral-Level Order

    Print the tree level by level, alternating the traversal direction at every level. Implement the traversal without recursion and select the required stacks or queues deliberately.

    Binary tree 
            1
      /   \
     2     3
    / \   / \
   4   5 6   7
    Output 
    1
3 2
4 5 6 7

  8. Check Whether a Binary Tree Is a Valid BST

    Determine whether the BST ordering property holds for every node with respect to all of its ancestors—not only its immediate parent.

    Binary tree 
           10
      /  \
     5    15
         /  \
        6    20
    Expected result 
    Not a valid BST

6 is in the right subtree of 10,
but 6 is smaller than 10.

    Constraint: O(n) time without storing all node values.

  9. Find the Lowest Common Ancestor in a BST

    Given a BST and two keys p and q, find their lowest common ancestor. Use the BST ordering property rather than a general binary-tree LCA traversal.

    BST 
            20
       /  \
      8    22
     / \
    4   12
       /  \
      10  14
    Example 
    p = 10, q = 14
LCA = 12

  10. Convert a BST into a Sorted Doubly Linked List

    Convert the BST in place into a sorted doubly linked list. Reuse each node's left pointer as prev and its right pointer as next.

    BST 
            8
      /   \
     4     12
    / \   / \
   2   6 10  14
    Sorted doubly linked list 
    NULL ← 2 ⇄ 4 ⇄ 6 ⇄ 8 ⇄ 10 ⇄ 12 ⇄ 14 → NULL

    Constraint: Do not create new tree or list nodes.

Lab 07

Binary Trees, BSTs and Heaps
  1. Write a program to compute the size of a binary tree (total number of nodes).
  2. Write a program to find the minimum and maximum keys in a binary tree.
  3. Write a program to find the deepest (lowest-level) node in a binary tree.
  4. Given two binary trees, write a program to return true if their structures are the same, and false otherwise.
  5. Write a program to print all keys of a BST within a given range [a, b].
  6. Write a program to build a max-heap from an unsorted array of n elements.
  7. Write a program to implement Heap Sort using the max-heap property to sort n integers in descending order.
  8. Write a program to increase the value of a key in a max-heap and restore the heap property.
  9. Write a program to find the k largest elements from an unsorted array using a min-heap.
  10. Write a program to check whether a given array satisfies the max-heap property.
Lab 08

Graph Algorithms and Greedy Algorithms

  1. Breadth First Search

    Implement Breadth First Search (BFS) for a given undirected graph and print the order of traversal.

  2. Depth First Search

    Implement Depth First Search (DFS) for a given graph and print the order of traversal.

  3. Articulation Points

    Write a program to count how many articulation points exist in a given graph.

  4. Topological Sort

    Implement Topological Sort of a directed acyclic graph (DAG) using DFS.

  5. Merge Sorted Lists

    Write a program to merge ⌈log2 n⌉ sorted lists, each containing ⌊n / log2 n⌋ elements, and produce a single sorted list of all the elements, taking n = 2k for some positive integer k.

  6. Job Sequencing with Deadlines

    Write a program to solve the Job Sequencing Problem with deadlines using a greedy algorithm. The program should find the maximum profit that can be earned by scheduling jobs within their deadlines.

    Example input
    Job IDDeadlineProfit
    J126
    J218
    J315
    J4210
    Expected output

    Schedule: J2 → J4 Maximum profit: 18

  7. Fractional Knapsack

    Write a program to implement the fractional knapsack problem.

  8. Huffman Coding

    Write a program to generate the complete Huffman code for all input symbols.

  9. Cycle Detection using DFS (Directed Graphs)

    Write a program to detect whether a given directed graph contains a cycle using Depth First Search (DFS).

Lab 09

Shortest-Path and Minimum Spanning Tree Algorithms
Lab 09 participation

Choose one pathway

Each student must complete either the one-week practical assignment or attend both Lab Class 09 and Lab Class 10. Students choosing the laboratory-class pathway must attend both classes.

Option A One-Week Practical Assignment

Complete the large-scale IoV/UAV shortest-path assignment and submit it by the stated deadline.

Option B Attend Lab Classes 09 and 10

Attend both laboratory classes. Complete the three Lab 09 questions below and the seven Lab 10 questions.

Option B · Attend Lab Classes 09 and 10

Lab Class 09: In-Class Programming Questions

Students choosing the lab-class pathway must attend both Lab Class 09 and Lab Class 10. Implement all three programs below during Lab Class 09.

  1. Implement Dijkstra’s Algorithm.
  2. Implement Prim’s Algorithm for finding the Minimum Spanning Tree (MST) using a min-heap.
  3. Implement Prim’s Algorithm for finding the MST using an array.
Lab Class 10 questions are available in the Lab 10 section below.
Option A · One-Week Practical Assignment

Shortest-Path Planning in a Large-Scale IoV/UAV Mobility Network

Objective: Study the practical performance of shortest-path algorithms on a realistic large-scale mobility network. Identify a suitable publicly available dataset related to Internet of Vehicles (IoV), vehicular mobility, UAV mobility, road networks, or a similar moving-network scenario; model it as a weighted graph; and analyze shortest-path performance on graphs of different sizes.

Problem Statement

Consider a mobility network represented as a weighted graph:

G = (V, E)
  • V represents locations, intersections, waypoints, or mobility nodes.
  • E represents feasible movements between locations.
  • Each edge (u, v) has a positive weight w(u, v), representing distance, travel time, or another meaningful movement cost.

Your task is to determine the shortest path between a given source location S and destination location D.

Part A: Dataset Selection

Identify a suitable publicly available real-world or realistic dataset that can be used to formulate the shortest-path problem. It may relate to vehicular mobility/IoV, urban road networks, UAV mobility or waypoints, traffic networks, transportation networks, or another suitable mobility scenario.

The dataset must be sufficiently large to permit meaningful algorithmic performance analysis. Clearly report:

  1. dataset name;
  2. source or URL;
  3. brief description of the dataset;
  4. number of records, nodes, and edges used;
  5. how the dataset is converted into a graph;
  6. what each vertex represents;
  7. what each edge represents;
  8. what edge weight is used;
  9. why the selected dataset is suitable for this problem.

Choosing and justifying an appropriate dataset is part of the assignment. Do not use a small manually created graph as the primary dataset.

Part B: Graph Construction

Preprocess the selected dataset and construct the corresponding weighted graph using an adjacency-list representation.

After constructing the graph, report:

  • number of vertices;
  • number of edges;
  • average degree;
  • maximum degree.

If the original dataset contains additional information that is not required for shortest-path computation, extract only the relevant information needed to construct the graph.

Part C: Dijkstra's Algorithm

Implement Dijkstra's shortest-path algorithm using a min-priority queue. For a given source S and destination D, report:

  1. shortest-path cost;
  2. complete sequence of vertices in the shortest path;
  3. number of vertices explored;
  4. number of edges examined;
  5. execution time.

Built-in shortest-path implementations from graph-processing libraries are not permitted. Also state and explain the theoretical time complexity of your implementation.

Part D: A* Algorithm

Implement the A* shortest-path algorithm for the same graph. For a vertex v, evaluate:

f(v) = g(v) + h(v)

Here, g(v) is the cost from the source to v, and h(v) is a heuristic estimate of the cost from v to the destination.

If positional coordinates are available, an appropriate distance-based heuristic may be used. Justify the selected heuristic and discuss whether it is admissible. Report the same performance metrics as for Dijkstra's algorithm.

Part E: Experimental Evaluation

Perform experiments using multiple graph sizes obtained from the selected dataset. Suggested graph sizes are approximately:

1,000 · 5,000 · 10,000 · 25,000 · and, if feasible, 50,000+ vertices

For each graph size, use multiple source-destination pairs. Record results in a table similar to the following:

Graph SizeAlgorithmShortest-Path CostVertices ExploredEdges ExaminedExecution Time
—Dijkstra————
—A*————

Use at least five different source-destination pairs for each selected graph size and report average performance over the selected queries.

Part F: Analysis

  1. Why is the dataset you selected suitable for shortest-path analysis?
  2. How did you transform the raw dataset into a weighted graph?
  3. Do Dijkstra's algorithm and A* produce the same optimal path cost in your experiments? Explain.
  4. Which algorithm explores fewer vertices, and why?
  5. How does execution time vary as the graph size increases?
  6. Explain the effect of the graph's density on shortest-path computation.
  7. What is the theoretical time complexity of your Dijkstra implementation?
  8. What heuristic did you use for A*? Is it admissible and/or consistent? Justify your answer.
  9. What difficulties did you face while converting the real-world dataset into a graph?
  10. Based on your observations, which algorithm would you recommend for large-scale IoV/UAV route planning? Justify your answer.

Bonus Task: Dynamic Edge Costs

Real mobility networks are dynamic. Travel cost may change due to congestion, link quality, weather, or other factors. Define an edge cost such as:

w(u, v) = αd(u, v) + βc(u, v)
  • d(u, v) represents distance;
  • c(u, v) represents another dynamic cost such as congestion or delay;
  • α and β are weighting parameters.

Modify selected edge weights and recompute the shortest path. Compare the new route with the original route and discuss the effect of changing network conditions.

Implementation Requirements

  1. Students must independently identify a suitable dataset.
  2. The selected dataset must be publicly available and properly cited.
  3. The graph must be represented using an adjacency list.
  4. Dijkstra's algorithm must use a min-priority queue.
  5. A* must be implemented independently.
  6. Built-in shortest-path implementations are not permitted.
  7. Path reconstruction must be implemented explicitly.
  8. The implementation must handle disconnected source-destination pairs appropriately.
  9. Dataset preprocessing steps must be clearly documented.
  10. All experiments must be reproducible.

Submission

Submit the following:

  1. source code;
  2. dataset source/reference;
  3. preprocessing details;
  4. README with execution instructions;
  5. experimental results;
  6. plots comparing the algorithms;
  7. a short report containing observations and answers to Part F.
Practical Assignment Submission Link · Submit by
Practical Assignment Submission Link ↗

Place all files in a single folder and compress it into a .zip or .rar archive. Name the compressed file admission_number.zip or admission_number.rar, replacing admission_number with your admission number.

Lab 10

Graph Algorithms and Dynamic Connectivity

  1. Cycle Detection

    Implement cycle detection in directed and undirected graphs using DFS. Additionally, implement cycle detection in undirected graphs using Disjoint Set Union (DSU). Compare their time complexities.

  2. Connected Components and SCCs

    Implement an algorithm to find connected components in an undirected graph and strongly connected components (SCCs) in a directed graph using Kosaraju's algorithm. Construct the condensation graph.

  3. Bellman–Ford Algorithm

    Implement Bellman–Ford to find single-source shortest paths in a weighted directed graph. Detect negative-weight cycles reachable from the source and identify affected vertices.

  4. Minimum Spanning Tree

    Implement Prim's and Kruskal's algorithms to find an MST. Display the selected edges and total weight. Determine whether the MST is unique.

  5. Topological Sorting

    Implement topological sorting using DFS and Kahn's algorithm. Detect cycles, find the lexicographically smallest valid ordering, and determine whether the ordering is unique.

  6. Dynamic Graph Connectivity

    Implement DSU with path compression and union by rank/size to support the following operations:

    • ADD u v: Add an edge.
    • CONNECTED u v: Check connectivity.
    • COUNT: Count connected components.
    • SIZE u: Find the size of a component.

  7. Second-Best MST

    Given a connected, undirected, weighted graph, find (i) the MST weight, (ii) the minimum weight of a spanning tree different from the selected MST, and (iii) the minimum spanning-tree weight strictly greater than the MST weight.

Lab 11

Dynamic Programming

  1. 0/1 Knapsack — Top-Down Approach

    Implement the 0/1 Knapsack Problem using the top-down approach.

  2. 0/1 Knapsack — Bottom-Up Approach

    Implement the 0/1 Knapsack Problem using the bottom-up approach.

  3. Longest Common Subsequence

    Write a program to find the longest common subsequence from the given two strings.

  4. Longest Increasing Subsequence

    Write a program to find the longest increasing subsequence.

  5. Longest Decreasing Subsequence

    Write a program to find the longest decreasing subsequence.

  6. Subset Sum Problem

    Given a set of positive integers and a target sum, determine whether any subset has a sum equal to the target.

  7. Matrix Chain Multiplication

    Given the dimensions of a sequence of matrices, determine the minimum number of scalar multiplications required to multiply them.

  8. Fibonacci Series

    Write a program to calculate the nth Fibonacci number using Dynamic Programming.

  9. Climbing Stairs

    Given a staircase with n steps, find the number of distinct ways to reach the top if you can climb either 1 or 2 steps at a time.

  10. Minimum Coin Change

    Given a set of coin denominations and a target amount, find the minimum number of coins required to make that amount. Assume unlimited availability of each denomination.

Lab 12

Hashing, Knapsack, and Dynamic Programming

  1. Remove Duplicate Characters Using Hashing

    Given an array of characters, give an algorithm to remove duplicate characters using hashing techniques.

  2. Compare Sets of Numbers Using Hashing

    Given two arrays of unordered numbers, check whether both arrays contain the same set of numbers using hashing techniques.

  3. Detect a Loop in a Singly Linked List Using Hashing

    Given a singly linked list, check whether it contains a loop using hashing techniques.

  4. Find a Pair with a Given Sum Using Hashing

    Given two sets A and B, and a number K, give an algorithm to determine whether there exists a pair of elements, one from A and one from B, whose sum is K, using hashing techniques.

  5. 0/1 Knapsack — Branch and Bound

    Implement Branch and Bound to solve the 0/1 Knapsack Problem.

  6. 0/1 Knapsack — Backtracking

    Implement Backtracking to solve the 0/1 Knapsack Problem.

  7. All-Pairs Shortest Paths Using Dynamic Programming

    Implement all-pairs shortest-path algorithms using Dynamic Programming.

  8. Rod Cutting Using Dynamic Programming

    Implement the rod-cutting problem using Dynamic Programming.