Chapter 1 - Algorithms

What is an algorithm?

A finite sequence of step-by-step instructions used to solve a problem.

In a flowchart, what does the shape of each box represent?

The function or purpose of that step.

How can unordered lists be sorted?

Using algorithms such as bubble sort or quick sort.

What is the basic idea of bubble sort?

Compare adjacent items and swap them if they are not in order.

What happens if adjacent items in bubble sort are already in order?

They are left as they are.

When is a list sorted in bubble sort?

When a full pass is completed with no swaps.

What is the first step in quick sort?

Select a pivot.

How does quick sort split the list?

Into items less than the pivot and items greater than the pivot.

What happens after the initial split in quick sort?

Further pivots are chosen and the process is repeated on each sub-list.

What are the three bin-packing algorithms?

First-fit, first-fit decreasing, and full-bin.

How does the first-fit algorithm work?

Items are considered in the order they are given.

How does the first-fit decreasing algorithm work?

Items are sorted in descending order before applying first-fit.

How does the full-bin packing algorithm work?

Inspection is used to fill bins exactly, remaining items use first-fit.

What is an advantage of first-fit?

Quick to implement.

What is a disadvantage of first-fit?

Not likely to lead to a good solution.

What is an advantage of first-fit decreasing?

Usually gives a good solution and is easy to implement.

What is a disadvantage of first-fit decreasing?

May not produce an optimal solution.

What is an advantage of full-bin packing?

Usually gives a good solution.

What is a disadvantage of full-bin packing?

Difficult to do, especially with many or awkward numbers.

What does the order of an algorithm describe?

How run time grows as input size increases.

If an algorithm has order f(n), how does run time change from size n to m?

By approximately a factor of f(m) / f(n).

If problem size increases by factor k, how does linear time change?

It takes approximately k times as long.

If problem size increases by factor k, how does quadratic time change?

It takes approximately k² times as long.

If problem size increases by factor k, how does cubic time change?

It takes approximately k³ times as long.