Ch 3 Brute Force and Exhaustive Search

Question 1

What is Brute Force Search? (also provide examples)

Answer 1

A straightforward approach, usually based directly on the problems statement and definitions of the concepts involved.

exs:
- computing n!
- multiplying 2 matrices

Question 2

What are the 2 important properties you must consider with sorting algorithms?

Answer 2

• stability: the relative order of two equal elements is preserved
  ex:
• in place: it does not use extra memory in proportion to the input array size
  ex:

Question 3

What is a Loop Invariant?

Answer 3

A Loop Invariant is an assertion that we prove to be true each time a loop iteration starts.

Question 4

How to prove the correctness of a loop invariant?

Answer 4

There are three steps to prove the correctness of a loop invariant:

1. Initialization: The invariant is true prior to the first iteration of the loop
2. Maintenance: if an invariant is true before an iteration of the loop, then it remains true before the next iteration.
3. When the loop terminates, the loop invariant along with the reason the loop terminated is used to derive a conclusion about the state of your algorithm.

Question 5

Prove the correctness of Selection sort using loop invariants

Question 6

Write pseudocode for the brute force string match algorithm. Also, whats the time compleixty?

Answer 6

for (int i = 0; i < n-m; i++) {
j = 0;
while ((j < m) and (P[j] = T[i+j])){
j = j+1;
}
if (j == m)
return i
return -1

Question 7

write pseudocode to find the two closest points in a set of n points (in
the two-dimensional Cartesian plane. Also, whats the time complexity?

Question 8

Given n cities with known distances between each pair, find
the shortest tour that passes through all the cities exactly
once before returning to the starting city

Question 9

Whats the space and time complexity for adjacency lists?

Question 10

Whats the space and time complexity for adjacency matrices

Question 11

Give pseudocode for the depth first search algorithm? Whats the time complexity?

Question 12

Give pseudocode for the breadth first search algorhtm? whats the time complexity?

Question 13

Whats the time complexity for DFS if the graph is in adjacency list representation? What about for adjacency matrices?

Question 14

Whats the time complexity for BFS if the graph is in adjacency list representation? What about for adjacency matrices?