# Chapter 1 Algorithms Flashcards

1
Q

What is an algorithm?

A

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

2
Q

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

A

In words or in a flow chart

3
Q

When can you say that an algorithm has been repeated?

A

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

4
Q

What is a trace table?

A

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

5
Q

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

A

Using a trace table

6
Q

Roughly explain a trace table?

A
7
Q

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

A

You draw a simple straight horizontal line through the row

8
Q

Have are flow charts made out of?

A

Different shaped shapes connected by arrowed lines

9
Q

In a flow chart, what does this shape mean?

A

Start/end

10
Q

In a flow chart, what does this shape mean?

A

Instruction

11
Q

In a flow chart, what does this shape mean?

A

Decision

12
Q

How can you write the discriminant in short hand?

A

d

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

13
Q

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

A

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

14
Q

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

A

The bubble sort algorithm
The quick sort algorithm

15
Q

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

A

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

16
Q

State the bubble sort algorithm.

A
17
Q

What are the exam tips for doing the bubble sort?

A

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

18
Q

What is useful to consider when doing the bubble sort?

A

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

19
Q

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

A

Circle the items that you swap
You may not need to show every swap

20
Q

What can the quick sort algorithm do?

A

Can sort lists alphabetically or numerically

21
Q

What is an advantage of the quick sort algorithm?

A

In many circumstances it will be quicker than the bubble sort

22
Q

State the quick sort algorithm.

A
23
Q

How do you choose the pivot when doing the quick sort algorithm?

A

For n items in a list the pivot point will be the (n+1)/2 item
If it is an decimal then you round up

24
Q

How do you do the quick sort algorithm in an exam (workings out)?

A

You should circle the number that is about to become the pivot
In the next line that circled number will become the pivot and therefore you draw a square around the pivot number

25
Q

What are the 3 different types of bin packing algorithms that you need to know?

A

Firs fit
First fit decreasing
Full bin

26
Q

What is an optimal solution?

A

A solution which can’t be improved

27
Q

What is often useful to do in bin packing questions?

Why?

A

Find the lower bound of bins needed

Because if you use an algorithm to pack the bins and you get the lower bound as your answer then you know that it is the optimal solution

28
Q

What do you need to be aware of when doing problems in decision maths?

A

Many problems involve the physical world and therefore you may need to round up a lot

Eg you can’t have 4.5 bins. You would need 5

29
Q

What is the method for the first fit algorithm?

A

1) Take the items in the order given
2) Place each item in the first available bin that can take it. (Start from bin 1 each time)

30
Q

What are the advantages of the first fit algorithm?

A

It is quick to implement

31
Q

What are the disadvantages of the first fit algorithm?

A

It is unlikely to lead to a good solution/optimal solution

32
Q

How do you do the fist fit algorithm in an exam (workings out)?

A
33
Q

What is the method for first fit decreasing algorithm?

A

1) Sort the items so that they are in descending order
2) Apply the first-fit algorithm to the reordered list

34
Q

What are the advantages of the first fit decreasing algorithms?

A

You usually get a fairly good solution
It is easy to implement

35
Q

What are the disadvantages of the first fit decreasing algorithms?

A

You may not a optimal solution

36
Q

What is the method for full bin packing?

A

1) Use observation to find combinations of items hat will fill a bin. Pack these items first.
2) Any remaining items are packed using the first-fit algorithm

37
Q

What are the advantages of full bin packing?

A

You usually get a good solution

38
Q

What are the disadvantages of full bin packing?

A

It is difficult to do, especially when there are a lot of numbers and the numbers are awkward

39
Q

How do you do full bin packing in an exam (working out)?

A
40
Q

What is the order of an algorithm?

A

The order of an algorithm tells us how an increase in the size of a problem will effect the run time of an algorithm

41
Q

What is another way to say the order of an algorithm?

A

The complexity of an algorithm

42
Q

What is the size of a sorting algorithm?

A

The n. Things that need to be sorted

43
Q

How do you calculate the order of an algorithm?

CHECKWITHMRSCOSTELLO

How do you use this information to work out the new run time of an algorithm?

A

You can find the order of an algorithm by (new size)/(original size)

To find the new run time of an algorithm do the number above multiplied by the original time stated in the question

44
Q

What is often used to determine the order of an algorithm?

A

The number of steps needed to complete an algorithm

45
Q

What do you need to keep in mind if you are asked to find the order of an algorithm?

A

It may be a variable quantity that depends on the input. As a result you may need to use an unknown

Eg the order may be √n

46
Q

What is the order of the bubble algorithm?
What is this called?

A

Since this is a quadratic equation the bubble sort algorithm is said to have a quadratic order

47
Q

What is a tip for when you are working out the order of an algorithm?

A

Consider the worst case scenario

48
Q

What are the common orders that you. Need to be able to recognise?

A

Linear order
Cubic order

49
Q

What is meant by a cubic order?

A

In the expression for the order of an algorithm the highest power of n is 3

50
Q

What is the special rule for linear orders?

A

If the size of a problem is increased by some factor k, then:
An algorithm of linear order will take approximately some factor k as long to complete

51
Q

What is the special rule for quadratic orders?

A

If the size of a problem is increased by some factor k, then:
An algorithm of linear order will take approximately some factor k^2 as long to complete

52
Q

What is the special rule for cubic orders?

A

If the size of a problem is increased by some factor k, then:
An algorithm of linear order will take approximately some factor k^3 as long to complete

53
Q

What may be 2 common tricks when working out the order?

A

Bubble sort 1 + 2 … n-1 (no n) so 1/2(n+1)-n

Work out the order for 1 iteration then for the whole thing (normally multiply by n floyds)

Be careful