# Chapter 1 Algorithms Flashcards

What is an algorithm?

An algorithm is a finite sequence of step by step instructions carried out to solve a problem

What are the different ways that an algorithm can be expressed?

In words or in a flow chart

When can you say that an algorithm has been repeated?

When a RESULT has been repeated. Even if you know that the result is about to be repeated you need to show that result.

What is a trace table?

A trace table is a table which is used to record the values of each variable as the algorithm is run

How can you record the values of each variable in an algorithm as its run?

Using a trace table

Roughly explain a trace table?

How can you show that you have deleted (or ignored) a row?

You draw a simple straight horizontal line through the row

Have are flow charts made out of?

Different shaped shapes connected by arrowed lines

In a flow chart, what does this shape mean?

Start/end

In a flow chart, what does this shape mean?

Instruction

In a flow chart, what does this shape mean?

Decision

How can you write the discriminant in short hand?

d

Eg

If b^2-4ac>0 the d>0

How can you use a trace table in relation to flow charts?

Since a trace table to keeping trace of the values of variables in the flow chart, the column will consist of the different variables as well as any decision boxes

What 2 algorithms from chapter 1 can be used to sort a list?

The bubble sort algorithm

The quick sort algorithm

What is a common mistake when using the bubble sort or quick sort algorithm?

Order them in the wrong way. The question will say ascending or descending

State the bubble sort algorithm.

What are the exam tips for doing the bubble sort?

You may be asked to show the full bubble sort for the first pass

But generally you will only need to show the state of the list after each pass

At the end of a question you need to state: no swaps were made in the xth pass so the list is in ascending/descending order

If you mix up descending and ascending then you can then swap it around at the end

What is useful to consider when doing the bubble sort?

It is useful to consider the whole list as 2 sub list of a:

Working list - where comparisons are being made

Sorted list - items that are in their correct positions

How do you do a bubble sort in an exam (workings out)?

Circle the items that you swap

You may not need to show every swap

What can the quick sort algorithm do?

Can sort lists alphabetically or numerically

What is an advantage of the quick sort algorithm?

In many circumstances it will be quicker than the bubble sort