Module 3

Question 1

A straightforward approach, usually based directly on the problem’s statement and definitions of the concepts involved

Answer 1

Brute Force

Question 2

Examples of Brute Force

Answer 2

1. Computing an (a > 0, n a nonnegative integer)
2. Computing n!
3. Multiplying two matrices
4. Searching for a key of a given value in a list

Question 3

Brute Force Strengths

Answer 3

• wide applicability
• simplicity
• yields reasonable algorithms for some important problems (e.g., matrix multiplication, sorting, searching, string matching)

Question 4

Brute Force Weaknesses

Answer 4

• rarely yields efficient algorithms
• some brute-force algorithms are unacceptably slow
• not as constructive as some other design techniques

Question 5

__________ sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.

Answer 5

Selection Sort Algorithm

Question 6

T or F

The Selection Sort Algorithm maintains two subarrays in a given array.

Answer 6

True

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

Question 7

T or F

In every iteration of selection sort, the minimum element (considering descending order) from the unsorted subarray is picked and moved to the sorted subarray.

Answer 7

False (Descending)

Question 8

In Brute Force String Matching what is a string of m characters to search for?

Answer 8

Pattern

Question 9

In Brute Force String Matching what is a a (longer) string of n characters to search in?

Answer 9

Text

Question 10

Compares a given pattern with all substrings
of a given text.

Answer 10

Brute Force String Matching

Question 11

T or F

Those comparisons between substring and pattern proceed character by
character unless a mismatch is found.

Answer 11

True

Question 12

Whenever a mismatch is found, the remaining character comparisons for that substring are dropped and the next substring can be selected
immediately.

Answer 12

True

Question 13

Brute Force Algorithm Steps:

Answer 13

Step 1 Align pattern at beginning of text

Step 2 Moving from left to right, compare each character of pattern to the corresponding character in text until all characters are found to match (successful search); or a mismatch is detected

Step 3 While pattern is not found and the text is not yet exhausted, realign pattern one position to the right and repeat Step 2

Question 14

A brute force solution to a problem involving search for an element with a special property, usually among combinatorial objects such as permutations, combinations, or subsets of a set.

Answer 14

Exhaustive Search

Question 15

Exhaustive Search Method

Answer 15

• generate a list of all potential solutions to the problem in a systematic manner evaluate potential solutions one by one, disqualifying infeasible ones and, for an optimization problem, keeping track of the best one found so far
• when search ends, announce the solution(s) found