63 Questions
What is the common way to represent a graph in computer science?
Using a matrix of adjacencies
Which graph traversal algorithm is used to visit all reachable nodes from a given starting node?
Breadth-First Search (BFS)
What is the time complexity of Breadth-First Search (BFS) on a graph with $V$ vertices and $E$ edges?
$O(V + E)$
Which graph data structure is used to represent a tree?
Rooted tree
What is the purpose of Kruskal's algorithm in graph theory?
To find the minimum spanning tree of a weighted graph
What topic does the section 'Undirected graph components' in the text fall under?
Graphs
Which section in the text mentions 'Minimum spanning tree'?
Graphs
In which part of the text would you expect to find information about 'Topological sort'?
Graphs
Which part of the text discusses 'Jousting' and 'Dot product'?
Graphs
'Longest common subsequence' and 'Knapsack' are topics found in which part of the text?
Dynamic Programming
'Borrow a book' and 'Levenshtein distance' are mentioned in which part of the text?
Complexity classes
What is the purpose of the adjacency matrix representation of a graph?
To represent the connectivity between nodes in a graph
Which graph traversal algorithm is used to visit all reachable nodes from a given starting node?
Depth-First Search (DFS)
What is the purpose of Topological Sort in graph theory?
To order the nodes of a directed graph based on their dependencies
What is the purpose of the adjacency list representation of a graph?
To allow for fast lookups of node degrees
What is the purpose of Kruskal's algorithm in graph theory?
To find the minimum spanning tree of a graph
What is the purpose of the edge list representation of a graph?
To efficiently store the edges of a sparse graph
What is the most common way to represent a graph in computer science?
Adjacency list
Which graph traversal algorithm is used to visit all reachable nodes from a given starting node?
Breadth-First Search (BFS)
What is the time complexity of Breadth-First Search (BFS) on a graph with $V$ vertices and $E$ edges?
$O(V + E)$
Which graph data structure is used to represent a tree?
Rooted tree
What is the purpose of Kruskal's algorithm in graph theory?
To find the minimum spanning tree of a graph
What is the purpose of Prim's algorithm in graph theory?
To find the minimum spanning tree of a graph
What is the purpose of Dijkstra's algorithm in graph theory?
To find the shortest path between two nodes
What is the purpose of Topological Sort in graph theory?
To find a linear ordering of the vertices in a directed acyclic graph (DAG)
What is the purpose of the Strongly Connected Components (SCC) algorithm in graph theory?
To partition a directed graph into its strongly connected components
What is the purpose of the Tarjan's algorithm in graph theory?
To find the strongly connected components of a directed graph
What starts with an empty candidate sequence or set and extends it one item at a time?
Partial candidates
Which technique only generates a fraction of all candidates making it more efficient than exhaustive search?
Tree traversal
In backtracking, what core traversal is used for generating permutations and subsets?
Tree traversal
When extending a candidate in backtracking, what does the algorithm do if it cannot lead to a solution or a better solution?
Goes back and tries a different item or candidate
At the core of backtracking is a recursive pre-order traversal of what structure?
Tree
Which problems in M269 are solved using backtracking on sequences of non-duplicate items or subsets of items?
Constraint satisfaction and optimization problems
What is the purpose of the first check in a backtracking algorithm?
To check if it's worth extending the candidate with a chosen item
What is the purpose of the second check in a backtracking algorithm?
To check if a candidate satisfies the global constraints
How can the search space be further pruned for subset problems in a backtracking algorithm?
By sorting the items in advance and stopping when a candidate cannot be extended
What is the purpose of the third check in a backtracking algorithm for optimization problems?
To compute the value of each solution found and update the current best
What represents the local constraints in a backtracking algorithm?
The conditions that a partial candidate must satisfy to be extended
In the context of backtracking algorithms, what do 'candidates' and 'extensions' represent?
Candidates are partial solutions, and extensions are the steps to complete them
What is the primary purpose of backtracking?
To generate candidates incrementally and prune the search space
Which condition is necessary for backtracking to be applicable?
Each solution (and candidate) is a collection of items
What is the primary advantage of backtracking over exhaustive search?
It is more efficient because it can prune the search space substantially
What is the primary difference between global constraints and local constraints in backtracking?
Global constraints apply to the entire solution, while local constraints apply to individual items
In the context of backtracking, what is a partial candidate?
An incomplete candidate that satisfies all constraints so far
What is the typical approach used by backtracking algorithms to explore the search space?
Depth-first search
What is the primary advantage of backtracking over exhaustive search?
Backtracking can generate fewer candidates by pruning the search space
What is the primary difference between global constraints and local constraints in backtracking?
Global constraints apply to the entire candidate solution, while local constraints apply to individual items in the candidate
When extending a candidate in backtracking, what does the algorithm do if it cannot lead to a solution or a better solution?
The algorithm backtracks to the previous step and explores a different extension
How can the search space be further pruned for subset problems in a backtracking algorithm?
By only considering unique items when extending the candidate
What is the purpose of the first check in a backtracking algorithm?
To determine if the current candidate is a complete solution
Which technique only generates a fraction of all candidates, making it more efficient than exhaustive search?
Backtracking
What is the primary advantage of backtracking over exhaustive search?
Backtracking explores the search space more efficiently by pruning branches that do not satisfy the local constraints.
What do the 'local constraints' represent in the context of a backtracking algorithm?
The constraints that apply to the current candidate solution, regardless of the rest of the solution.
What is the purpose of the first check in a backtracking algorithm?
To check if extending the current candidate solution with a chosen item is worth pursuing, based on the local constraints.
How can the search space be further pruned for subset problems in a backtracking algorithm?
By sorting the items in advance so that when one can't extend a candidate, neither can any of the subsequent items.
What is the primary difference between global constraints and local constraints in a backtracking algorithm?
Global constraints apply to the entire candidate solution, while local constraints only apply to the current item being considered.
What is the key ingredient that turns an exhaustive traversal into a backtracking algorithm?
The check to see if it's worth extending the current candidate solution with a chosen item, based on the local constraints.
What is a key advantage of backtracking over exhaustive search?
Prunes vast parts of the search space
In backtracking, where are global constraints checked?
On all candidate sequences
What differentiates backtracking from brute-force search in terms of candidate generation?
Backtracking prunes candidate generation
How does backtracking handle local constraints during candidate generation?
Local constraints are checked for each extension
Why is backtracking more efficient than generating all permutations?
It prunes vast parts of the search space
What is a distinguishing feature of backtracking compared to brute-force search regarding the search space?
'Prunes parts of the search space'
Test your knowledge on collections, algorithms, and coding style in TMA 01 Part 2. Questions cover topics like ordered and unordered collections, different algorithms, and best coding practices.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
