CS401A's Pre-Finals: Design & Analysis of Algrthms. Module 04

Question 1

Definition of || What is

• It is also known as “proof by exhaustion.”

Answer 1

Brute-Force Algorithm || Brute Force Algorithm Design Technique?

Question 2

Definition of Brute-Force Algorithm

What is Brute Force Algorithm Design Technique?
* It is also known as

Answer 2

“proof by exhaustion.”

Question 3

Definition of || What is

• It is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases, where each type of case is checked to see if the proposition in question holds.

Answer 3

Brute-Force Algorithm || Brute Force Algorithm Design Technique?

Question 4

Definition of || What is

• It is a straightforward approach to solve a problem based on the problem’s statement and definitions of the concepts involved.

Answer 4

Brute-Force Algorithm || Brute Force Algorithm Design Technique?

Question 5

Definition of || What is

It is a straightforward approach in the sense that it specifically gives an idea of what approach to use.

Answer 5

Brute-Force Algorithm || Brute Force Algorithm Design Technique?

Question 6

Definition of || What is

• “Force” comes from using computer power, not intellectual power, In short, Brute Force means “just do it”.

Answer 6

Brute-Force Algorithm || Brute Force Algorithm Design Technique?

Question 7

Definition of Brute-Force Algorithm

What is Brute Force Algorithm Design Technique?
* “\_\_\_\_\_” comes from using computer power, not intellectual power, In short, \_\_\_\_\_ \_\_\_\_\_ means “\_\_\_\_ \_\_ \_\_”.

Answer 7

Force
Brute Force
just do it

Question 8

Definition of || Importance of Using

• It is applicable to a very wide variety of problems,

such as sorting, searching, string matching.

Answer 8

Brute-Force Algorithm || Brute Force Algorithm Design Technique

Question 9

Definition of || Importance of Using

• It yields reasonable algorithms of at least some practical value with no limitation on instance size.

Answer 9

Brute-Force Algorithm || Brute Force Algorithm Design Technique

Question 10

Definition of || Importance of Using

• Sometimes, a particular problem can be solved so quickly with a \_\_\_\_\_ \_\_\_\_\_ \_\_\_\_\_\_ that it does not make sense to waste time devising a more elegant solution.

Answer 10

Brute-Force Algorithm || Brute Force Algorithm Design Technique
Brute Force method

Question 11

Definition of || Importance of Using

• It can still be useful for solving small-size instances of a problem.

Answer 11

Brute-Force Algorithm || Brute Force Algorithm Design Technique

Question 12

Definition of || Importance of Using

• It can serve as an important theoretical or education purpose.

Answer 12

Brute-Force Algorithm || Brute Force Algorithm Design Technique

Question 13

Definition of || Strengths of

• There is wide applicability of the technique.

Answer 13

Brute-Force Algorithm || Brute Force Algorithm Design Technique

Question 14

Definition of || Strengths of

• It is simple, yields reasonable algorithms for some important problems and yields standard algorithms for simple computational tasks and graph traversal problems.

(e.g., matrix multiplication, sorting, closest-pair; convex-hull),

Answer 14

Brute-Force Algorithm || Brute Force Algorithm Design Technique

Question 15

Definition of || Strengths of

• It is simple, yields \_\_\_\_\_\_\_\_\_\_ \_\_\_\_\_\_\_\_\_\_ for some important problems and yields \_\_\_\_\_\_\_\_ \_\_\_\_\_\_\_\_\_\_ for simple computational tasks and graph traversal problems.

(e.g., matrix multiplication, sorting, closest-pair; convex-hull),

Answer 15

Brute-Force Algorithm || Brute Force Algorithm Design Technique
reasonable algorithms
standard algorithms

Question 16

Definition of || Weaknesses of

• It rarely yields efficient algorithms.

Answer 16

Brute-Force Algorithm || Brute Force Algorithm Design Technique

Question 17

Definition of || Weaknesses of

• Some are unacceptably slow

(such as the recursive algorithm for computing Fibonacci numbers).

Answer 17

Brute-Force Algorithm || Brute Force Algorithm Design Technique

Question 18

Definition of || Weaknesses of

• It is not as constructive as some other design techniques.

Answer 18

Brute-Force Algorithm || Brute Force Algorithm Design Technique

Question 19

Application of Brute Force Algorithm

Answer 19

• Sorting problem
• Searching problem
• Brute Force String Matching
• Exhaustive Search

Question 20

Application of

asks to rearrange the items of a given list in ascending or descending order.

Answer 20

Brute Force Algorithm
Sorting problem

Question 21

Application of

List of Sorting Algorithms

Answer 21

Brute Force Algorithm
* Selection sort
* Bubble sort

Question 22

Application of

is a type of sorting algorithm in which the smallest element in the unsorted portion of a list is selected and then swapped with the element at the beginning of the sorted portion of the list. The steps are then repeated until all of the data are sorted.

Answer 22

Brute Force Algorithm
* Selection sort

Question 23

Application of

is a type of sorting algorithm that compares the adjacent pair of elements of the list and swaps them if they are in the wrong order. The steps through the list are repeated until no more swaps are required, which indicates that the list is sorted.

Answer 23

Brute Force Algorithm
* Bubble sort

Question 24

Application of

This shows the ‘\_\_\_\_\_\_\_\_ \_\_’ of the largest element to the last position on the list.

Answer 24

Brute Force Algorithm
* Bubble sort
bubbling up

Question 25

# **Application of** deals with finding a given value called the `______ ___` in a given list or set.

Answer 25

**Brute Force Algorithm** **Searching problem** **search key**

Question 26

# **Application of** (sometimes called a linear search) examines a sequence of data objects one by one until a match is encountered (successful search), or the list is exhausted without finding a match (unsuccessful search).

Answer 26

**Brute Force Algorithm** * **Sequential Search**

Question 27

# **Application of** (sometimes called a `______ ______`) examines a sequence of data objects one by one until `_ _____ __ ___________` (successful search), or `___ ____ __ _________ _______ _______ _ _____` (unsuccessful search).

Answer 27

**Brute Force Algorithm** * **Sequential Search** linear search a match is encountered the list is exhausted without finding a match

Question 28

# **Application of** It is the process of finding the exact copy of pattern/s ***P*** with all substrings of a given text ***T***.

Answer 28

**Brute Force Algorithm** **Brute Force String Matching**

Question 29

# **Application of** Those comparisons between substring and pattern proceed character by character unless a mismatch is found.

Answer 29

**Brute Force Algorithm** **Brute Force String Matching**

Question 30

# **Application of** Whenever a mismatch is found, the pattern is shifted one (1) position to the right and comparison is repeated until a match is found or until the end of the text is reached.

Answer 30

**Brute Force Algorithm** **Brute Force String Matching**

Question 31

# **Application of** **Brute Force String Matching** *Rules:*

Answer 31

**Brute Force Algorithm** 1. Align pattern at the beginning of the text. 2. Moving from left to right, compare each character of pattern to the corresponding character in the text until (a) all characters are found to match (successful search) or (b) a mismatch is detected. 3. While the pattern is not found and the text is not yet exhausted, realign pattern one (1) position to the right and repeat Step 2.

Question 32

# **Application of** It is a brute-force approach to a combinatorial problem.

Answer 32

**Brute Force Algorithm** **Exhaustive Search**

Question 33

# **Application of** It essentially generates a list of all potential solutions to the problem systematically, evaluates potential solutions one by one, disqualifies the infeasible ones, and, for an optimization problem, keeps track of the best one found so far.

Answer 33

**Brute Force Algorithm** **Exhaustive Search**

Question 34

# **Application of** When the search ends, announce the solution/s found.

Answer 34

**Brute Force Algorithm** **Exhaustive Search**

Question 35

# **Application of** **Exhaustive Search** These are the important problems:

Answer 35

**Brute Force Algorithm** * **Traveling Salesman Problem (TSP)** * **Assignment problem**

Question 36

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

Answer 36

**Brute Force Algorithm** * **Traveling Salesman Problem (TSP)**

Question 37

# **Application of** * **Traveling Salesman Problem (TSP)** *Rules:*

Answer 37

**Brute Force Algorithm** 1. Choose a reference point or a vertex where you want to start. 2. List all the Hamilton circuits with that reference point. 3. Determine the cost (or distance) associated with each of these Hamilton circuits. 4. The Hamilton circuit with the lowest cost (or shortest distance) is the optimal solution.

Question 38

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

Answer 38

**Brute Force Algorithm** A **Hamiltonian circuit**

Question 39

# **Application of** It is named after the Irish mathematician Sir William Rowan Hamilton (1805-1865), who became interested in such cycles as an application of his algebraic discoveries.

Answer 39

**Brute Force Algorithm** A **Hamiltonian circuit**

Question 40

# **Application of** It is named after the `_____ _____________ ___ _______ _____ ________` (`_________`), who became interested in such cycles as an application of his algebraic discoveries.

Answer 40

**Brute Force Algorithm** A **Hamiltonian circuit** Irish mathematician Sir William Rowan Hamilton 1805-1865

Question 41

# **Application of** — It requires pairing of n people to execute n jobs in such a way that the total cost/profit of the pairings is minimized or maximized.

Answer 41

**Brute Force Algorithm** * **Assignment problem**

Question 42

# **Application of** *Characteristics of an Assignment Problem*

Answer 42

**Brute Force Algorithm** ○ Each entity is to be assigned to exactly one (1) task. ○ Each task is to be performed by exactly one (1) entity.

Question 43

# **Application of** ○ It is also known as Flood's Technique or Matrix Reduction Method.

Answer 43

**Brute Force Algorithm** *Hungarian Method*

Question 44

# **Application of** *Hungarian Method* ○ It is also known as `_______ _________` or `______ _________ ______`.

Answer 44

**Brute Force Algorithm** Flood's Technique Matrix Reduction Method

Question 45

# **Application of** ○ 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.

Answer 45

**Brute Force Algorithm** *Hungarian Method*

Question 46

# **Application of** ○ It was first published by Harold W. Kuhn in 1955.

Answer 46

**Brute Force Algorithm** *Hungarian Method*

Question 47

# **Application of** *Hungarian Method* ○ It was first published by `______ __ ____` in `____`.

Answer 47

**Brute Force Algorithm** Harold W. Kuhn 1955

Question 48

# **Application of** ○ It was based on the earlier work of Hungarian mathematicians Dénes König and Jenö Egerváry.

Answer 48

**Brute Force Algorithm** *Hungarian Method*

Question 49

# **Application of** *Hungarian Method* ○ It was based on the earlier work of Hungarian mathematicians `_____ _____` and `____ ________`.

Answer 49

**Brute Force Algorithm** Dénes König Jenö Egerváry