Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

zA Level Further Maths > Decision - Chapter 1 Algorithms > Flashcards

Decision - 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

In words or in a flow chart

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

Using a trace table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Roughly explain a trace table?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Have are flow charts made out of?

A

Different shaped shapes connected by arrowed lines

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

In a flow chart, what does this shape mean?

A

Start/end

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

In a flow chart, what does this shape mean?

A

Instruction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

In a flow chart, what does this shape mean?

A

Decision

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How can you write the discriminant in short hand?

A

d

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

The bubble sort algorithm
The quick sort algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

State the bubble sort algorithm.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What can the quick sort algorithm do?

A

Can sort lists alphabetically or numerically

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is an advantage of the quick sort algorithm?

A

In many circumstances it will be quicker than the bubble sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
Quadratic 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

zA Level Further Maths (35 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions