Algorithms/ solving Problems

Question 1

existence problem

Answer 1

determining if there is a solution

Question 2

construction problem

Answer 2

finding a solution to the problem

Question 3

enumeration

Answer 3

finding how many solutions there are to a problem

Question 4

optimisation

Answer 4

finding the best solution to a problem

Question 5

pigeon hole principal

Answer 5

if there are m pigeonholes and n pigeons, where m

Question 6

proper subset

Answer 6

a part of a set that is smaller than the original set

Question 7

number of ways of arranging n objects where non are repeated

Answer 7

n!

Question 8

if there are n numbers and r positions to arrange them and a number cannot be repeated then the number of ways of arranging the numbers is

Answer 8

n!/(n-r)!

Question 9

choosing n items from a set of r where the order doesn’t matter

Answer 9

r!/n!

Question 10

The number of combinations of r objects from n is

Answer 10

n!/(n-r)!r!

Question 11

inclusion exclusion principal

Answer 11

|AUBUC| = |A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C|

Question 12

order of an algorithm

Answer 12

The value with the largest exponent with the coefficient

Question 13

Bin packing algorithms

Answer 13

next-fit
first-fit
first-fit decreasing

Question 14

Comparisons in bubble sort

Answer 14

decrements with each pass

Question 15

Comparisons in shuttle sort

Answer 15

random

Question 16

If there are no swaps in bubble sort

Answer 16

the list is sort

Question 17

what is the maximum number of passes for a bubble sort algorithm

Answer 17

n - 1

n is the number of passes

Question 18

finding the lower bound for a bin packing algorithm

Answer 18

adding all the contents and dividing it by the bin size. This gives minimum number of bins to be used.

Question 19

Quadratic complexity

Answer 19

Doubling the size of the problem results in four times the effort

Question 20

Linear complexity

Answer 20

Doubling the size of the problem doubles the effort

Question 21

worst case time complexity of a quick sort

Answer 21

O(n^2)

if the list in in reverse order

Question 22

first fit decreasing in 3D

Answer 22

sort by length, height, perimeter or area

Question 23

Knapsack problems

Answer 23

• workout value per kg
• the highest value per kg should go in the knapsack
• the remaining knapsack can be filled optimally by trial and error

Question 24

Derangement formula

Answer 24

Dn = (n-1)(Dn-2)(Dn-1)

Question 25

For passwords…

Answer 25

use selections n!/(n-r)!