The Brute Force Technique
What is the brute force approach?
A straightforward approach that tries all possible solutions to find the best one.
In the context of a BFS traversal, what does it mean when a vertex is dequeued from the queue?
The vertex has been fully explored, and its neighbors are now being processed.
Which type of search successively compares elements until is encounters a match?
Sequential search
What problem involves finding the smallest distance between a pair of vertices in a graph?
Closest-pair problem
How does BFS determine the order of visiting vertices?
FIFO
Why is brute force considered inefficient for large inputs?
It often has exponential or factorial time complexity, making it computationally expensive.
In the context of a DFS traversal, what does it mean when a vertex is popped from the stack?
The vertex has been fully explored, and the algorithm is back tracking
What improvement can be made to the initial version of the bubble sort?
Stop the algorithm of no exchanges occur in a pass.
What problem involves maximizing the value of the items is a bag structure without exceeding the bags capacity?
The knapsack problem
Which sorting algorithm begins by scanning a given list in it's entirety to fins the smallest element?
Selection sort
T/F Many Brute Force algorithms can be improved with modes effort
True
DFS is a _____ -based technique, while BFS is a ___-based technique.
Vertex, Edge
When is it advantageous to stop a sequential search in a sorted list?
When an element larger than or equal to the search key is found.
What problem involves finding the smallest polygon that encloses a given set of points in a plane?
Convex Hull
What is the primary idea behind brute-force problem solving?
Try every possible solution
What is the primary characteristic of the brute force approach to string-matching algorithms?
It systematically compares characters in the text and pattern
In the context of BFS, what does the queue represent?
The current level of the vertices being explored
What type of searching algorithm does this describe?
"the algorithm evaluates every possible solution within the problem domain"
exhaustive search
What is the primary objective of the assignment problem?
Minimize the total cost of assigning people to jobs.
What makes the Hungarian method effective in solving the assignment problem?
It ensure that the total cost is minimized by iteratively improving the solution through augmentation and reduction
Describe Brute force technique for password cracking
Brute force password cracking, where all possible combinations are tested
In the context of a DFS, what does the stack trace represent?
The current path of the vertices being explored
What is the key characteristic of Bubble Sort that makes it inefficient for large datasets?
Bubble Sort repeatedly swaps adjacent elements if they are in the wrong order, leading to a worst-case time complexity of O(n²), making it slow for large datasets
Which optimization problem describes visiting a set of cities exactly one and then returning to the start?
Traveling Salesman problem
Doom