Midterm Stuff

What is a brute force algorithm?

A brute force algorithm is an algorithm that is the most straightforward way to solve a problem.

It systematically tries every single possibility until it gets the answer.

Why do we use brute force? Is brute force always bad?

We use it because it’s easy to understand and implement.

Brute force isn’t always bad, it can be just fine if your input sizes are small, efficiency isn’t important, and development speed matters.

In the following pseudocode, how come we never see i++ or j++ being mentioned anywhere?

largest = -infinity
for i = 0 to n-1
  for j=i+1 to n-1
    product = A[i] * A[j]
    if product > largest
       largest = product
    end-if
   end-for
end-for

We never see it mentioned anywhere because in pseudocode, the for loop updates automatically.

The other thing about pseudocode is that since there is no i++ or j++, the i+1 part belonging to:
for j=i+1 to n-1 only happens on the first iteration of the code.

So it only happens once, at the beginning, when j first becomes j = 1. After that, j becomes an ordinary loop variable that increments independently.

Trace through some of the following code using the array: A = [3, 8, 1, 9, 5]

Show your workings on a piece of paper.

largest = -infinity
for i = 0 to n-1
  for j=i+1 to n-1
    product = A[i] * A[j]
    if product > largest
       largest = product
    end-if
   end-for
end-for

What are the exhaustive types of brute force algorithms like?

They generate every possible solution and test each one.

The steps are:

• You generate a candidate solution.

• You check to see whether or not it works.

• If it doesn’t work, you generate another, and then repeat until you’re done.

The String Matching Algorithm says the following:

• Put the pattern at the beginning of the text.

• Compare characters.

• If mismatch occurs, shift the pattern over by one.

• Try again.

• Continue until found or end reached.

How can we apply the String Matching algorithm to the following word: BANANA

If we want to find an instance of the substring: ANA

Step 1: Align the letters

BANANA

ANA

= No match, therefore, shift over by one

BANANA
ANA

= Match!! Returns index 1.

What is the Travelling Salesman Problem about?

The Travelling Salesman Problem is about a Salesperson that must travel to each city at least once, and return to their starting city. They also want to minimize the total distance they travel.

Given the following graph, how can you find the most optimal route for our Travelling Salesman to travel?

What is the Assignment Problem about?

The assignment problem is about a group of people who all need to be assigned jobs.

The goal is that we have to give one person exactly one job, and give each job to exactly one person, as well as minimize the total cost of hiring them.

When doing Assignment Problems, you’ll typically see tables like this, which tells us the cost of assigning each person to a job (people are on the left hand side, jobs at the top).

	J1	J2	J3	J4
P1	9	2	7	8
P2	6	4	3	7
P3	5	8	1	8
P4	7	6	9	4

You will also see solutions to these types of problems written out like this:

<1,2,3,4>

This means that:

P1 → J1 (Person 1 gets Job 1)

P2 → J2 (Person 2 gets Job 2

P3 → J3

P4 → J4

And something else like:
<4,1,2,3>

Means that:

P1 → J4

P2 → J1

P3 → J2

P4 → J3

Given the following Assignment table, how can we assign people to jobs such that we get the cheapest assignments? Show your solution on paper.

	J1	J2	J3	J4
P1	9	2	7	8
P2	6	4	3	7
P3	5	8	1	8
P4	7	6	9	4

How can we solve the following Dark-Light Problem?

The problem: D L D L D L

The Dark Light Algorithm says the following:

• Scan left to right, and find the first DL pair

• Swap it

• Start scanning again, find another DL pair

• Swap it

The goal is to arrange the sequence such that all the lights are on the left, like this:

L L L D D D. However, the only allowed move is swapping adjacent discs (they must be side by side, not one character apart). DL must eventually become LD.

What is Decrease And Conquer?

Decrease and Conquer is a type of Algorithm where you solve a smaller version of the same problem, then apply that smaller answer to solve the original problem.

For example:

To compute 5!, compute 4! then use it to get 5!

What are the 2 Type of Decrease & Conquer Algorithms?

Type #1: Decrease by a constant amount

Subtracting 1 or 2 from the original value, but it could be more:

n → n-1

OR

n→ n-2

It’s usually done with recursion, where every recursive call removes the same amount.

Type #2: Decrease by a constant factor

Dividing the original value by 2 (or more), but it’s usually 2.

n → n / 2

Describe what the Fake Coin Algorithm is about.

The fake coin algorithm is about a sneaky banker who gives you N coins, except one of the coins is fake. You know that its fake because it weighs less.

The best way to find this fake coin is to take your pile of coins, split it in half, weigh it on a 2-sided scale, and see which side is lighter. Then, you take the lighter half and split it in half again.

If you somehow manage to get an odd number of coins, you set aside one coin and only split the rest in half.

Before we continue, make sure you have all of the following on your cheat sheet:

Or at least have this image saved somewhere. It will help you answer some of the next few questions about Complexity.

 

Quiz Question: Which of these short descriptions of algorithm patterns refers to decrease and conquer algorithms?

Question 10 options:

A)	Check if a problem of size N has been solved before If yes, return the result If no, calculate the result and store it for later use
B)	Generate all possible solutions to the problem Test each possible solution to see if it is the solution
C)	Divide the problem into 2 or more subproblems Solve all of the subproblems Combine the results to obtain the answer to the original problem
D)	Solve a smaller instance of the same problem Extend the result to obtain the answer to the original problem

Answer: D)

A) is not decrease and conquer because it stores something for later use. Decrease and conquer never stores anything.

B) is not decrease and conquer because it generates all possible outcomes. This is obviously referring to Brute Force.

C) Is not decrease and conquer because we are not dividing the problem into MULTIPLE subproblems, we only solve one smaller problem. We also don’t combine any answers; This is actually referring to Divide and Conquer, which we’ll go over later.

D) IS DECREASE AND CONQUER!! This is the exact definition. We solve a smaller instance of the same problem, then extend/apply the answer of the smaller problem to get the answer of the bigger problem.

Here is an English description of a decrease-and-conquer algorithm (not quite pseudocode) to determine whether a character string is a palindrome.

Input: A string S of length n (characters indexed from 0 to n-1).
Output: TRUE if S is a palindrome; FALSE otherwise.

1. If the length of S is 0 or 1, return TRUE.
2. Otherwise, let S' be the substring of S that excludes the first and last characters.
3. Recursively test if S' is a palindrome.
4. If the test in line 3 is TRUE AND the first and last characters of S are equal, return TRUE.
5. Otherwise, return FALSE.

What type of decrease-and-conquer algorithm is this?

Question 4 options:

A)	Decrease by one-half (constant factor)
B)	Decrease by one-third (constant factor)
C)	Decrease by 1 (constant amount)
D)	Decrease by 2 (constant amount)

D) Decrease by 2.

We know this because it explicitly states that for a string, such as: “Sofia”

We exclude the first and last characters, leaving us with: “ofi”

Then we check to see if “ofi” is a palindrome (if it can be read the same backwards and forwards.

Since we went from 5 characters to 3 characters, this is decreasing by a constant amount of 2.

Here is an English description of the basic idea of performing Binary Search to find a key in a sorted list. One word is incorrect. What is the correct replacement for the incorrect word?

If the list is trivially small (0 or 1 element), return the appropriate answer (either "found" or "not found"). Otherwise, examine the middle element of the list. If it matches the key, return "found". Otherwise, check whether the key is less than or greater than the middle element. Based on this test, disregard one third of the list (either the left or the right). Repeat the process using the remaining portion of the list.

Your answer below should be a single word:

Half

(Refer to the Cheat Sheet About Binary Search)

Describe how the algorithm for Exponentiation by Squaring works
(Best to write the answer for this on a cheat sheet)

A number is raised to a power of 20 by using the decrease and conquer "exponentiation by squaring" algorithm. What is the total number of multiplications performed throughout the calculations?

Answer: 5

A number is raised to a power of 17 using the decrease-and-conquer Exponentiation by Squaring algorithm. How many multiplications are performed throughout the calculations?

Answer: 5

If you have 20 identical-looking coins, what is the worst case (most number of weighings possibly needed) for the two-pile fake-coin algorithm?

Your answer should be just a number.

What is the big-O time complexity of the following algorithm?

Fake coin problem (N = number of identical-looking coins)

Answer: O(log N)

(See cheat sheet)

What is the big-O time complexity of the following algorithm?

Generating subsets of N items

Answer: O(2^N)

See cheat sheet.

If you have 19 identical-looking coins, what is the best case (least number of weighings possibly needed) for the two-pile fake-coin algorithm?

Your answer should be just a number.

Answer: 1 Weighing

A number is raised to a power of 37 by using the decrease and conquer "exponentiation by squaring" algorithm. What is the total number of multiplications performed throughout the calculations?

Answer: 7

What is merge sort?

Merge sort is a method of sorting an array in ascending order. It uses the divide and conquer algorithm because it repeatedly divides each subarray into one element, then it merges everything in sorted order.

Merge sort is in O(n log n) order.

Perform merge sort on the following array:

[8,3,5,1]

Perform merge sort on the following 2 arrays:

[10,23,24] and [1,3,5,25]

What is the big-O class of the following algorithm?

Answer: O(N²)

You may be confused because the nested for loops at the top produce something which goes from i=1 to n, adding up one each time, and then the second nested for loop runs from i=1 to i, and adds up one each time.

However, you should assume that the nested for loop can only go up to n because i is only as great as n.

What is the basic operation in the pseudocode fragment shown here?

j = 0
i = n
while i > 0 do
   j = j+1
   if j > 0 then
      x = i
      while x > 0
         x = x - j
      end-while
   end-if
   i = i/2
end-while

Question 2 options:

A)	Line 3 - while loop/condition
B)	Line 4 – assignment statement j=j+1
C)	Line 5 – if statement/condition
D)	Line 8 – assignment statement x=x-j

Answer: D) assignment statement x=x-j

Which equivalency class is bigger?

Bigger means that the class contains more functions than the other class.

Question 3 options:

A)	O(2n2 + 3n)
B)	O(2n2 + 3n3 + 5)
C)	They are the same size

B) is the biggest because it has n³

Note that the efficiency classes increase as such:

SMALLEST

O(1) = constant

O(log n) = logarithmic

O(n) = linear

O(n log n) = linearithmic

O(n²) = quadratic

O(n³) = cubic

O(2ⁿ) = exponential

O(n!) = factorial

LARGEST

 

Saved

Which equivalency class is bigger?

Bigger means that the class contains more functions than the other class.

Question 4 options:

A)	O(nlogn)
B)	O(n2)
C)	They are the same size

B) O(n²)

Write the summation formula that expresses the number of times the basic operation of this algorithm will be executed.

Algorithm Mystery(n)
    prod = 1
    for i = 1 to n
        prod = prod * 2
    end-for
    return prod
END

The complexity classes O(n³) and O(n³+5n) represent exactly the same set of functions.

Question 6 options:

A)	True
B)	False

A) True, because the dominant term in both is the n³, so we can just completely disregard the 5n in each.

The complexity classes O(n³) and O(2n³ + 3n² + 5n) represent exactly the same set of functions.

Question 7 options:

A)	True
B)	False

A) True

They have the same dominant term.

Suppose you know that a function g(n) is in the complexity class O(n). Then what else do you know for certain?

Question 8 options:

A)	g(n) is in O(1)
B)	g(n) is in O(n2)
C)	g(n) is in both O(1) and O(n2)
D)	There is not enough information to know about either of these classes

B) g(n) is in O(n²)

First, let’s figure out what Big O actually means/represents.

Big O represents the “maximum speed limit”; When we say Big O(n), we mean that this function will never grow faster than a straight line (than linear).

So if a function can never grow faster than linear, we know that it’s small enough to fit in bigger complexity classes.

For example:

if Big O(n) represents $5

and Big O(n²) represents $10,

then we know our function, g(n), in the complexity class O(n), will also fit in Big O(n²).

It cannot fit into something smaller, like Big O(1), which probably only represents $0.50.

Therefore, our answer is B) g(n) is in O(n²)

Suppose you know that a function g(n) is in the complexity class O(nlogn). Then what else do you know for certain?

Question 9 options:

A)	g(n) is in O(n)
B)	g(n) is in O(n2)
C)	g(n) is in both O(n) and O(n2)
D)	There is not enough information to know about either of these classes

B) g(n) is in O(n²)

Remember that O(n log n) is smaller than O(n²), therefore it can fit inside O(n²).

Which one of these things do we LEAST care about when we are comparing two algorithms to decide which one is "better"?

Question 10 options:

A)	Space efficiency
B)	Number of lines of code
C)	Time efficiency
D)	Correctness

B) Number of lines of code.

What is a Max Heap in the following question?

• Write a pseudocode algorithm that takes an array A as input and returns TRUE if the order of elements in the array is a valid max-heap, or FALSE otherwise. Assume that the elements of A are indexed from 1 to N. Hint: Your algorithm should run in O(N) time. Also, be careful to avoid array OOB errors.

A max heap is an array, such as: [3, 4, 5, 6] that when transformed into a binary tree, has every one of its root nodes greater than its children.

To transform an array into a binary tree, we place the first element at the top of the tree, and every subsequent element on the left first, then on the right.

How can we find the left and right elements on a binary tree using a generic formula involving i?

• Write a pseudocode algorithm that takes an array A as input and returns TRUE if the order of elements in the array is a valid max-heap, or FALSE otherwise. Assume that the elements of A are indexed from 1 to N. Hint: Your algorithm should run in O(N) time. Also, be careful to avoid array OOB errors.

The left element on a tree is: 2 x i

The right element on a tree is 2 x i + 1

Write a pseudocode algorithm that takes an array A as input and returns TRUE if the order of elements in the array is a valid max-heap, or FALSE otherwise. Assume that the elements of A are indexed from 1 to N. Hint: Your algorithm should run in O(N) time. Also, be careful to avoid array OOB errors.

We already established that to find the left and right elements of a tree, we do:

left = 2 x i

right = 2 x i + 1

And we know that the root node is the one that always needs to be greater than its children.

So the root = i

We need to go through and make sure that in every case, the value of the array at the root is greater than the value of the array on either the left or right side (its children).

We know that as soon as we encounter a single instance of the root being smaller than its child, we should exit out and conclude that we do not have a max heap. So instead of returning TRUE, we should return FALSE.

And only return TRUE in the case that we never returned FALSE.

We also have to make sure never to go out of bounds. Since the question tells us that we use 1-based indexing instead of 0 based indexing, all we have to do is make sure we never go over N, which is the number of total elements.

Answer:

Note: Here I used the variable king to represent the root.

Algo: isMaxHeap(A[1...N])
for i <- 1 to N
  king <- i
  left <- 2 * i
  right <- 2 * i + 1

  if left <= N then
    if A[king] < A[left]
      return FALSE

  if right <= N then
    if A[king] < A[right]
      return FALSE

return TRUE

A similarity between HeapSort and MergeSort is that they are both O(nlogn) algorithms.

Question 1 options:

A)	True
B)	False

A) True

Given a valid min-heap, the array representation of the tree is already in sorted order (descending).

Question 2 options:

A)	True
B)	False

B) False

If an array is sorted in descending order, it could be considered to be a valid max-heap.

Question 3 options:

A)	True
B)	False

A) True

Only one of these arrays is a valid max-heap. Which one?

Question 4 options:

A)	[ 74, 19, 55, 11, 13, 37 ]
B)	[ 74, 19, 55, 37, 13, 11 ]
C)	[ 55, 19, 74, 11, 13, 37 ]
D)	[ 11, 13, 19, 37, 55, 74 ]

A)

[ 74, 19, 55, 11, 13, 37 ]

The binary tree below represents a min-heap. What is the equivalent array-based representation of this heap?

A)	[ 99, 66, 18, 37, 54, 13, 9 ]
B)	[ 9, 54, 99, 66, 13, 18, 37 ]
C)	[ 9, 54, 13, 99, 66, 18, 37 ]
D)	[ 9, 13, 18, 37, 54, 66, 99 ]

C)	[ 9, 54, 13, 99, 66, 18, 37 ]

Shown below are two algorithms that solve the same problem (given an unsorted array, find the pair of numbers that have the smallest difference).

Algorithm SmallestDiff_VERSION_ONE(A[0..n-1])
A = MergeSort(A)
smallestDiff = MAXINT
smallestPair = (A[0], A[1])
for i = 1 to n-2 do
if abs(A[i] - A[i+1]) < smallestDiff then
smallestDiff = abs(A[i] - A[i+1])
smallestPair = (A[i], A[i+1])
endif
endfor
return smallestPair
END



Algorithm SmallestDiff_VERSION_TWO(A[0..n-1])
smallestDiff = MAXINT
for i = 0 to n-2 do
for j = i+1 to n-1 do
if abs(A[i] - A[j]) < smallestDiff then
smallestDiff = abs(A[i] - A[j])
smallestPair = (A[i], A[j])
endif
endfor
endfor
return smallestPair
END

Which one of these algorithms is a Transform and Conquer algorithm?

Question 6 options:

A)	SmallestDiff_VERSION_TWO (the red coloured one)
B)	SmallestDiff_VERSION_ONE (the blue coloured one)

A)

Consider the algorithm we studied in class for computing the "mode" of an array.
Which of the following is a reason that this algorithm could be considered a transform and conquer algorithm?

Question 7 options:

A)	The overall algorithm runs in O(nlogn) time.
B)	The 2nd part of the algorithm runs in O(n) time.
C)	The algorithm "pre-sorts" the array and as a result it can perform a more efficient search for the most frequent item.
D)	There is a brute-force algorithm that has a longer running time than this algorithm.

C)	The algorithm "pre-sorts" the array and as a result it can perform a more efficient search for the most frequent item.

What is the "structure property" that a binary tree must have for it to be a valid max-heap?

Question 8 options:

A)	The tree is "almost complete"
B)	Every parent has exactly 0 or 2 children
C)	The maximum value is stored in the root
D)	Every parent node has a value greater than or equal to its children

A)	The tree is "almost complete"

What are the names of the two properties of a binary tree that are required to make it a valid heap?
(You must choose TWO answers.)

Question 9 options:

A)	Value property
B)	Equivalence property
C)	Parent-child property
D)	Sorted order (ascending vs. descending)
E)	Structure property

A) and E)

What is the correct relationship between two SIBLING nodes in a valid max-heap?

Question 10 options:

A)	The left sibling is greater than or equal to the right sibling
B)	The siblings are of equal value
C)	Any of the other relationships are possible
D)	The right sibling is greater than or equal to the left sibling

C)	Any of the other relationships are possible