DAA Prefinals

It is the process of finding the exact copy of patterns with all the substrings of a given text.

String matching

It deals with finding a given value called the search key in a given list or set.

Searching Problem

It is sometimes referred to as linear search.

Sequential search

It is a method of mathematical proof in which the statement to be proved is split into a finite number of cases.

Brute Force algorithm

It is used to find minimum matches in which the time of completion or cost of making all activities by the number of persons is minimized.

Hungarian Method

Who first published the Hungarian Method in 1955?

Harold W. Kuhn

It examines a series of data objects one by one until a match is encountered.

Sequential search

This sorting algorithm chooses the smallest element in the unsorted portion of a list and then swaps with the element at the beginning of the sorted portion of the list.

Selection sort

It is a path that begins and ends at the same vertex and passes through all other vertices of the graph exactly one time.

Hamiltonian circuit

Its goal is to find the least expensive or shortest way to visit through a given set of cities once and return to the original starting point.

Traveling Salesman Problem

This sorting algorithm compares the adjacent pair of elements of the list and swaps them if they are in the wrong order.

Bubble sort

It is also known as proof by exhaustion.

Brute Force Algorithm

Who is the Irish mathematician after whom the Hamiltonian circuit is named?

Sir William Rowan Hamilton

It requires pairing of people to execute jobs to minimize or maximize the total cost/profit of the pairings.

Assignment Problem

In an assignment problem, each task is to be performed by exactly how many entities?

1

In an assignment problem, how many tasks are assigned to each entity?

1

It arranges the items in a given list in ascending or descending order.

Sorting

It essentially generates a list of all potential solutions to a problem and evaluates them one by one.

Exhaustive search

Which of the following DOES NOT belong to the group? (Traveling Salesman Problem, Maximization, Minimization, Assignment Problem)

Maximization

Which of the following DOES NOT belong to the group? (Reference point, Assignment problem, Hamiltonian circuit, Traveling Salesman Problem)

Reference point

What is the first step of the Traveling Salesman Problem?

Choose a reference point or a vertex where you want to start.

Which of the following is NOT a rule of the Traveling Salesman Problem?

Align the pattern at the beginning of the text.

Which of the following is NOT TRUE about a Hamiltonian circuit?

It is a cycle that may repeat vertices multiple times to complete the path.

Which of the following is an advantage of the Brute Force algorithm?

It yields standard algorithms for graph traversal problems.

What is the first step of Brute Force string matching?

Align the pattern at the beginning of the text.

In solving a maximization problem using the Hungarian method, what should be done next after identifying the highest value in each row?

Subtract each row value from each of the highest values.

In solving a maximization problem using the Hungarian method, what should be done next after selecting the lowest entry in each column?

Subtract the lowest entry from every entry in the column.

What is the first step in solving a minimization problem using the Hungarian method?

Identify the lowest value in each row.

Which of the following steps comes first in solving a maximization problem using the Hungarian method?

Identify the highest value in each row.

In solving a minimization problem using the Hungarian method, what should be done next after selecting the lowest entry in each column?

Select the lowest entry from every entry in that column.

What is the second step of the Traveling Salesman Problem?

List all the Hamilton circuits with the chosen reference point.

Which of the following is NOT TRUE about the Hungarian Method?

It was named after Sir William Rowan Hamilton, who studied cycles in graphs.

Which of the following is NOT TRUE about the Brute Force algorithm?

It is a path that begins and ends at the same vertex.

Which of the following is NOT a rule of Brute Force string matching?

Select the smallest element among all the uncovered elements.

What is the third step of the Traveling Salesman Problem?

Determine the cost (or distance) associated with each of these Hamilton circuits