Chapter 1 (Algorithms)

Question 1

Prim’s algorithm, order?

Answer 1

Cubic

Question 2

Kruskal’s algorithm, order?

Answer 2

Cubic

Question 3

Bubble sort, order?

Answer 3

Quadratic

Question 4

What’s an algorithm

Answer 4

A set of specific set of finite instructions for carrying out a procedure or solving a problem (usually terminate at one point).

Question 5

Curved rectangular box meaning?

Answer 5

Start/ End

Question 6

Rectangle box meaning?

Answer 6

Process (an instruction)

Question 7

Diamond meaning?

Answer 7

Decision

Question 8

How can you tell when a quick sort list of numbers are in order

Answer 8

Once every number has become a pivot (no more changes are made)

Question 9

What do you do if the lower bound is not an integer?

Answer 9

Round up to the next whole number

Question 10

First fit algorithm:

Answer 10

Take the items in the order they’re given, place each item in the first available bin that can take it. Start with bin one each time

Question 11

Advantages and Disadvantages of the first fit bin algorithm:

Answer 11

Quick

Not likely to lead to a good solution

Question 12

First fit decreasing algorithm:

Answer 12

Record the items so they’re in decreasing order

Apply the first fit algorithm to this recorded list

Question 13

Advantages and disadvantages of the first fit decreasing algorithm:

Answer 13

Usually get fairly good solutions
Easy to do

You may not get the optimum solution

Question 14

Full bin packing:

Answer 14

Use observation to find combinations of items that will fill a bin. Any remaining is packed using first fit algorithm.

Question 15

Advantages and Disadvantages of Full bin packaging:

Answer 15

Good solution

Takes a long time

Question 16

What can the order of an algorithm be described as?

Answer 16

As a function of its size

Question 17

If an algorithm has an order of f(n) then increasing the size of the problem from n to m will increase the run time by a factor of what?

Answer 17

f(m)/f(n)

Question 18

What number is definitely at the correct position after the first pass (list ascending order), in bubble sort?

Answer 18

The largest value

Question 19

What’s the max number of comparisons needed for a list of 10 numbers?

Answer 19

n-1

=9 comparisons