1. Algorithms

Question 1

What is an algorithm?

Answer 1

A finite sequence of step-by-step instructions carried out to solve a problem

Question 2

Name 2 methods of sorting unordered lists

Answer 2

1. Bubble Sort

2. Quick Sort

Question 3

What are the steps to the bubble sort algorithm?

Answer 3

1. Start at beginning of working list and move from left to right, comparing adjacent items
2. If the two items are not in order, swap them
3. If the two items are in order, leave them
4. Once at the end of the working list, the last item is in its final position (no longer part of working list)
5. If you had swaps in last pass, repeat steps 1-3
6. If not, the list is sorted

Question 4

What are the steps to the quick sort algorithm to sort a list in ascending order?

Answer 4

1. Choose item at midpoint of list (even-numbered list has a midpoint of item to the right of middle) to be the pivot point
2. Write all items less than pivot point, keeping their order, as a sub-list
3. Write down the pivot point
4. Write remaining items after pivot point as sub-list
5. Apply steps 1-4 to each sub-list
6. Once all items have been chosen, the list is ordered

Question 5

What are the 3 bin-packing algorithms?

Answer 5

1. First-fit
2. First-fit decreasing
3. Full-bin

Question 6

What is the state of the order of a list for the first-fit algorithm?

Answer 6

Items are in the order they are given

Question 7

What is the state of the order of a list for the first-fit decreasing algorithm?

Answer 7

Requires the items to be in descending order before applying algorithm

Question 8

What is the state of the order of a list for the full-bin algorithm?

Answer 8

Order does not matter

Question 9

What are the steps to the first-fit algorithm?

Answer 9

1. Take items in order they are given

2. Place each item in first available bin that can take it, starting from Bin 1 each time.

Question 10

What are the steps to the first-fit decreasing algorithm?

Answer 10

1. Sort items in descending items

2. Apply first-fit algorithm to this list

Question 11

What are the steps to the full-bin algorithm?

Answer 11

1. Use observation to find combinations of items that will fill a bin, packing these items first
2. Any remaining items should be packed using first-fit algorithm

Question 12

What is the advantage and disadvantage of using first-fit algorithm?

Answer 12

Advantage: Quick to implement
Disadvantage: Unlikely to lead to good solution

Question 13

What are the advantages and the disadvantage of using the first-fit decreasing algorithm?

Answer 13

Advantages: Easy to implement and usually get a fairly good solution
Disadvantage: May not get optimal solution

Question 14

What is the advantage and disadvantage of using the full-bin algorithm?

Answer 14

Advantage: Usually get a good solution
Disadvantage: Difficult to do, esp. with many awkward numbers

Question 15

What is the order of an algorithm?

Answer 15

A function of its size

Question 16

If an algorithm has an order of f(n), what factor will the algorithm’s run time increase by if the size of the problem n to m?

Answer 16

f(m) / f(n)

Question 17

When the size of a problem is increased by a factor of k, how long does it take a linear order algorithm to complete?

Answer 17

k times as long

Question 18

When the size of a problem is increased by a factor of k, how long does it take a quadratic order algorithm to complete?

Answer 18

k squared times as long

Question 19

When the size of a problem is increased by a factor of k, how long does it take a cubic order algorithm to complete?

Answer 19

k cubed times as long