Design and Analysis of Algorithms

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.

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

1. Exponentiation Using Recursion

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

   xⁿ = { (x^n/2)²,  if n is even x · (x^⌊n/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.

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.

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

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.