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
State the quick sort algorithm.
How do you choose the pivot when doing the quick sort algorithm?
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
How do you do the quick sort algorithm in an exam (workings out)?
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
What are the 3 different types of bin packing algorithms that you need to know?
Firs fit
First fit decreasing
Full bin
What is an optimal solution?
A solution which can’t be improved
What is often useful to do in bin packing questions?
Why?
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
What do you need to be aware of when doing problems in decision maths?
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
What is the method for the first fit algorithm?
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)
What are the advantages of the first fit algorithm?
It is quick to implement
What are the disadvantages of the first fit algorithm?
It is unlikely to lead to a good solution/optimal solution
How do you do the fist fit algorithm in an exam (workings out)?
What is the method for first fit decreasing algorithm?
1) Sort the items so that they are in descending order
2) Apply the first-fit algorithm to the reordered list
What are the advantages of the first fit decreasing algorithms?
You usually get a fairly good solution
It is easy to implement
What are the disadvantages of the first fit decreasing algorithms?
You may not a optimal solution
What is the method for full bin packing?
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
What are the advantages of full bin packing?
You usually get a good solution
What are the disadvantages of full bin packing?
It is difficult to do, especially when there are a lot of numbers and the numbers are awkward
How do you do full bin packing in an exam (working out)?
What is the order of an algorithm?
The order of an algorithm tells us how an increase in the size of a problem will effect the run time of an algorithm
What is another way to say the order of an algorithm?
The complexity of an algorithm
What is the size of a sorting algorithm?
The n. Things that need to be sorted
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?
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
What is often used to determine the order of an algorithm?
The number of steps needed to complete an algorithm
What do you need to keep in mind if you are asked to find the order of an algorithm?
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
What is the order of the bubble algorithm?
What is this called?
Since this is a quadratic equation the bubble sort algorithm is said to have a quadratic order
What is a tip for when you are working out the order of an algorithm?
Consider the worst case scenario
What are the common orders that you. Need to be able to recognise?
Linear order
Quadratic order
Cubic order
What is meant by a cubic order?
In the expression for the order of an algorithm the highest power of n is 3
What is the special rule for linear orders?
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
What is the special rule for quadratic orders?
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
What is the special rule for cubic orders?
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
What may be 2 common tricks when working out the order?
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
