Scribd
Upload
4 views3 pages

Algorithm Questions and Answers

The document outlines key concepts in algorithm design and analysis, including steps for analyzing efficiency, asymptotic notations, and various algorithms such as Dijkstra’s and the Traveling Salesperson Problem. It also covers problems in computational complexity like P, NP, and NP-Complete, along with specific algorithms for maximum matching in bipartite graphs and the stable marriage problem. Each section includes time complexity assessments and pseudocode examples for clarity.

Uploaded by

suryaganesh2024
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views3 pages

Algorithm Questions and Answers

The document outlines key concepts in algorithm design and analysis, including steps for analyzing efficiency, asymptotic notations, and various algorithms such as Dijkstra’s and the Traveling Salesperson Problem. It also covers problems in computational complexity like P, NP, and NP-Complete, along with specific algorithms for maximum matching in bipartite graphs and the stable marriage problem. Each section includes time complexity assessments and pseudocode examples for clarity.

Uploaded by

suryaganesh2024
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithm Design and Analysis - Important

Questions with Answers

1. Steps for Analyzing the Efficiency of an Algorithm


Analyzing the efficiency of an algorithm involves determining the amount of resources (time and
space) it requires.
Steps:
1. Identify the basic operation that contributes most to running time.
2. Determine the input size (n).
3. Express total operations as T(n).
4. Find best, average, and worst cases.
5. Simplify T(n) using asymptotic notation (O, Θ, Ω).
6. Analyze space complexity if needed.

Example: Linear Search — Best: O(1), Worst: O(n), Average: O(n).

2. Asymptotic Notations and Their Use


Asymptotic notations describe the growth rate of an algorithm as input increases.

- Big O (O): Upper bound, worst case. Example: O(n^2)


- Omega (Ω): Lower bound, best case. Example: Ω(1)
- Theta (Θ): Tight bound, average case. Example: Θ(n log n)

They express efficiency independent of hardware, allowing fair comparison.

3. Brute Force String Matching & Traveling Salesperson Problem


(i) Brute Force String Matching Algorithm:
Checks pattern by shifting one position at a time.

Pseudo Code:
for i = 0 to n-m:
j=0
while j < m and text[i+j] == pattern[j]:
j=j+1
if j == m:
return i
Time Complexity: Best O(1), Worst O((n–m+1)*m).

(ii) Traveling Salesperson Problem (TSP):


Finds shortest tour visiting all cities once and returning.
All permutations are tested, minimum cost chosen.
Time Complexity: O(n!).

4. Dijkstra’s Algorithm & Huffman Tree Construction


(i) Dijkstra’s Algorithm:
Finds shortest path using greedy technique.
Steps:
1. Initialize dist[source]=0, others=∞.
2. Choose vertex u with min dist not visited.
3. Update neighbors: if dist[u]+weight(u,v)4. Repeat for all vertices.
Complexity: O(V^2) or O(E log V).

(ii) Huffman Tree Construction:


1. Create nodes for symbols with frequency.
2. Insert into min-heap.
3. Remove two smallest, combine to new node.
4. Repeat until root remains.
Higher frequency → shorter codes; lower → longer codes.

5. Maximum Matching Bipartite Graph & Stable Marriage Problem


(i) Maximum Matching Bipartite Graph (Pseudocode):

function MaxBipartiteMatch(G):
for each u in U:
mark all vertices unvisited
if BPM(G, u, visited, matchR):
result++

function BPM(G, u, visited, matchR):


for each v connected to u:
if not visited[v]:
visited[v]=True
if matchR[v]==-1 or BPM(G, matchR[v], visited, matchR):
matchR[v]=u
return True
return False
Time Complexity: O(V * E).

(ii) Stable Marriage Problem (Gale-Shapley Algorithm):


1. Each man proposes to his most preferred woman.
2. Each woman accepts the most preferred proposal.
3. Repeat until all matched.
Result: stable pairing.

6. P, NP, NP-Complete Problems & N-Queen Problem


(i) P, NP, and NP-Complete Problems:

- P: Solvable in polynomial time. (e.g., Binary Search, Dijkstra)


- NP: Verifiable in polynomial time. (e.g., Hamiltonian Cycle)
- NP-Complete: Hardest NP problems. (e.g., SAT, TSP)

(ii) N-Queen Problem using Backtracking:


Place N queens on an N×N board so none attack each other.

Steps:
1. Place queen in first column.
2. Move to next column and check safe rows.
3. Backtrack if no safe position.
4. Continue until all queens placed.
Complexity: O(N!).

You might also like