csc445 quiz 3

What is Prim’s algorithm used for?

finding the minimum spanning tree (MST) in a graph

What is the time complexity of prim’s algorithm using an adjacency matrix?

O(V²)

What is the key idea behind Prim’s algorithm?

always select the edge with the minimum weight

In prim’s algorithm, what does the “key value” of a vertex represent?

the minimum weight edge connecting the vertex to the MST

Which of the following is true about prim’s algorithm?

it works on connected, undirected graphs

What is the first step in prim’s algorithm?

choose a arbitrary vertex to start the MST

What is the total weight of the MST in the following graph?

3 (2 + 1)

What type of algorithm is Kruskal’s algorithm?

greedy algorithm

What does Kruskal’s algorithm find?

minimum spanning tree (MST)

What is the first step in Kruskal’s algorithm?

sort all edges in non-decreasing order of weight

How many edges will be present in the MST of a connected graph with V vertices?

V-1

What is the main purpose of Dijkstra’s algorithm?

find the shortest path from a source to all vertices

 In Dijkstra’s algorithm, what is the initial distance assigned to all vertices except the source?

infinity

Dijkstra’s algorithm follows which type of approach?

greedy algorithm

Which real-world application uses Dijkstra’s algorithm?

finding the shortest path in Google maps

Which algorithm uses a greedy approach to find the shortest path in a graph?

Dijkstra’s algorithm

What is a key difference between a DP-based shortest-path algorithm and and a greedy-based one?

DP considers all possible paths before making a decision, while greedy makes locally optimal choices

The Knapsack problem follows which programming paradigm?

dynamic programming

What is the time complexity of the Knapsack problem using dynamic programming?

O(nW)

What is the main advantage of using dynamic programming for the Knapsack problem?

it always finds the optimal solution

Why does the greedy algorithm fail for the Knapsack problem?

it does not consider all possible item combinations 

What is the primary goal of huffman coding?

to reduce the size of data using variable-length codes

What is the key advantage of using Huffman coding over fixed-length codes like ASCII?

it uses fewer bits for frequent symbols

What is the time complexity of building a Huffman tree?

O(nlogn)

What is the first step in the Huffman coding algorithm?

calculate the frequency of each symbol

Which of the following is true about Huffman coding?

it is a greedy algorithm

What is the main principle behind Huffman coding?

assign shorter codes to more frequent symbols

Which of the following is NOT a step in the Huffman coding algorithm?

sort the symbols alphabetically

What is the minimum number of bits required to encode 6 unique symbols using Huffman coding?

3 bits

What is the size of the encoded message “ABAC” using the following Huffman codes: A = 0, B = 10, C = 11.

6 bits

What data structure is used in BFS?

Queue

What data structure is used in DFS?

Stack

DFS traversal follows which technique?

backtracking

Backtracking is mainly used for:

constraint satisfaction problems

What technique is used in backtracking?

recursion and backtracking

What algorithm is better suited for maze solving?

DFS with backtracking

 Backtracking is most useful when:

the problem has multiple constraints that need to be checked

What is the time complexity of the knapsack problem using dynamic programming?

O(N * W)

What is the worst-case time complexity of the knapsack problem using backtracking?

O(2ⁿ)

How does the backtracking approach solve the 0/1 Knapsack problem?

it generates all possible subsets and checks if they satisfy the weight constraint

 What is the main disadvantage of using backtracking for the knapsack problem?

it has a high time complexity in the worst case