Sorting, Graph, Dynamic programming, Searching, Recursion,

Questions which are related to the title

What is recursion?

• A function that calls itself to solve a smaller version of the problem.

What are the two cases in a recursive function?

1. Base case (terminates recursion)

2. recursive case (function calls itself).

Difference between recursion and iteration?

• Recursion uses function calls and stack memory;

• iteration uses loops without extra stack overhead.

Give examples of problems solved with recursion

1. Fibonacci

2. Factorial

3. Tree traversals

4. Graph traversals (DFS/BFS)

5. Towers of Hanoi."

What is sorting?

Sorting arranges elements of a list in a specific order (ascending or descending).

What is the best complexity possible for comparison-based sorting?

O(n log n).

Name two non-comparison sorting algorithms.

1. Counting Sort

2. Radix Sort.

What is a stable sort?

A sorting algorithm that preserves the relative order of equal elements

Which algorithms are recursive and which are not?

• Recursive → QuickSort, MergeSort;

• Non-recursive → Selection Sort, Insertion Sort."

What is searching in computer science?

The process of finding an item with specified properties in a collection.

Why is searching important?

To retrieve data efficiently from large datasets.

What are the main types of searching algorithms?,

1. Linear Search

2. Binary Search

3. Interpolation Search

4. Hash-based search."

What is the complexity of Linear Search?

O(n).

What is the complexity of Binary Search?

O(log n) (on sorted data).

What is a graph?

A pair (V, E) where V is a set of vertices and E is a set of edges."

What is the difference between directed and undirected graphs?

• Directed graphs have edges with a direction (u→v)

• Undirected graphs have bidirectional edges (u,v)."

What is a spanning tree?

A subgraph that connects all vertices with minimum edges and no cycles.

Which algorithm finds the shortest path in a graph with positive weights?

Dijkstra’s Algorithm.

"Which algorithm finds all-pairs shortest path, even with negative weights?

Floyd–Warshall Algorithm.

What is Dynamic Programming (DP)?

A method that solves problems by breaking them into subproblems, storing results to avoid recomputation.

What are the two key properties of DP problems?

1. Optimal substructure

2. Overlapping subproblems.

What are the two approaches of DP?

• Bottom-up (tabulation)

• Top-down (memoization).

Give classic examples of DP problems.

• Longest Common Subsequence

• Knapsack

• Matrix Chain Multiplication

• Fibonacci

• Bellman-Ford

• TSP

How is DP different from Divide & Conquer?

• Divide & Conquer solves independent subproblems,

• DP handles overlapping subproblems using memoization.

What is the average and worst case of QuickSort?

• Average = O(n log n)

• Worst = O(n²). Trick → avoid worst case by using random pivot."

What is the time complexity of MergeSort?

• O(n log n).

• Recurrence → T(n) = 2T(n/2) + O(n).

Trick to quickly compare sorting algorithms?

1. Insertion → small n, nearly sorted;

2. MergeSort → guaranteed O(n log n);

3. QuickSort → fastest in practice but avoid bad pivots;

4. HeapSort → good for memory-constrained."

How does Binary Search work?

Repeatedly divide sorted array into halves until element is found or interval is empty.

What is the recurrence relation for Binary Search?

T(n) = T(n/2) + O(1) → O(log n)

Trick for choosing searching algorithm?

1. If array is sorted & static → Binary Search;

2. if dynamic (many insert/delete) → Hashing or Trees.

What is the recurrence for Fibonacci using recursion?

T(n) = T(n-1) + T(n-2) + O(1) → O(2^n).

How to optimize recursive Fibonacci?

Use Dynamic Programming (memoization) → reduces to O(n).

What is the time complexity of BFS and DFS?

O(V + E).

Trick to remember BFS vs DFS?

• BFS = Queue (level order)

• DFS = Stack (depth-first).

Which algorithm finds the Minimum Spanning Tree (MST)?

1. Kruskal (greedy with edges)

2. Prim (greedy with vertices)

3. Trick: Prim = Grow a tree

4. Kruskal = Join forests.

Formula for Longest Common Subsequence (LCS)?

if X[i] = Y[j];
    LCS[i][j] = LCS[i-1][j-1] + 1 ;
else max(LCS[i-1][j], LCS[i][j-1]);

Trick for recognizing DP problems?

Look for overlapping subproblems and optimal substructure.