unit 4 aos 1/2

Question 1

Class

Class Change making problem

Answer 1

NP-complete (min number of coins)

NP-hard (how many possibilities)

Question 2

Dynamic (divide and conquer)

Knapsack

runtime

Answer 2

Runtime: O(n*w)

Question 3

Heuristic solution (guesstimate)

Travelling salesmen

runtime

Answer 3

• randomly guessing and run several times
  O(n * c) where c is the time that u run it

Question 4

Greedy (NN - nearest neighbour):

Travelling salesmen

runtime

Answer 4

• nearest neighbour approach
  
  • pick the closest node all the time that has not been visited
• runtime is O(n^2)

Question 5

Binary search
Runtime and design type (include best case)

Answer 5

Start from the middle and keep on removing half of it until it is lower or higher until it finds the number.
Best -> O(1)
Worse/Average -> O(log N)
Design type -> decrease and conquer

Question 6

Merge sort

runtime and design type

Answer 6

Best/Worse/Average -> O(n log n)
* input does the same thing no matter what (input of array)

Design type -> divide and conquer

Question 7

Quick sort

runtimes & design type & when does best and worse case occur

Answer 7

best: O(N log N)
- pivot middle value for best time
- array is random

average: O(N log N)
Worse: (n^2)

• ascending and descending order for worse time

Design type -> divide and conquer

• acts like decrease and conquer in worse case)

Question 8

When does Merge sort perform the worse

Answer 8

• input does the same thing no matter what (input of array)

Question 9

When does quick sort perform the worse

Answer 9

• if the pivot happens to be the smallest or largest element in the list
• list is already sorted

Question 10

When does the A* Algorithm guarantee the smallest node

Answer 10

• heuristic needs to underestimate the distance for guarantee getting the smallest node
• depending on the way heuristics are implemented.

Question 11

Runtime for knapsap bruteforce

Answer 11

O(2^n)

Question 12

Stochastic hill climbing

what it is

Answer 12

The algorithm takes the initial point as the current best candidate solution and generates a new point within the step size distance of the provided point. The generated point is evaluated, and if it is equal or better than the current point, it is taken as the current point

Question 13

Simulated annealing

Answer 13

Simulated annealing executes the search in the same way as stochastic hill climbing but new points that are not as good as the current point (worse points) are accepted sometimes

• lower the temperature, lower the chance

Question 14

advantage and limitations of using heuristics as an algorithm in TSP

Answer 14

• Limitation: may not give the most optimal solution
• Advantage: relatively fast compared to brute force

Question 15

Change making problem “formula”

Answer 15

min(array[coin - i] + 1, array[i])
where: coin is the value coins in the array
i is the iterations looping through the array