D1, C1 - Algorithms Flashcards

1
Q

What is an algorithm

A

A process or a set of instructions that need to be followed PRECISELY

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

How can you use a table to implement algorithms (what goes in the top row (headers))

A

Step number
Variables (such as A, B, et…)
Print (if things are printed)

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

What numbers does an algorithm generate if it generates (1, 1, 2, 3, 5, 8, …)

A

Fibonacci sequence

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

What is a flow chart

A

A way of listing instructions or a process

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

What shape is a start / end in a flow chart

A

Oval

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

What shape is an instruction in a flow chart

A

Rectangle

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

What shape is a decision (question) in a flow chart

A

Diamond

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

What is a trace table

A

A table that record actions / results

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

What goes in the header of a trace table

A

Actions
Variables
Print
Decisions

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

Perform a bubble sort on 4, 1, 3, 2 to get them into ascending order

A

1) 4, 1, 3, 2
2) 1, 3, 2, 4
3) 1, 2, 3, 4
4) 1, 2, 3, 4

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

What are the steps for a bubble sort

A

1) Start at the beginning and move from left to right comparing adjacent items, if in order leave, if out of order swap
2) When you get to the end of the working list, last item will be in its final position, this item is no longer in the working list
3) If you have made some swaps in the last pass repeat step 1
4) When a pass is completed with no swaps, every item is in final position and the list is in order

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

What is ascending

A

Smallest to biggest

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

What is descending

A

Biggest to smallest

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

Bubble sort into ascending order:
24, 18, 37, 11, 15, 30

A

1) 24, 18, 37, 11, 15, 30
2) 18, 24, 11, 15, 30, 37
3) 18, 11, 15, 24, 30, 37
4) 11, 15, 18, 24, 30, 37
5) 11, 15, 18, 24, 30, 37

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

What working should you show with bubble sorts

A

Circle letters / numbers being swapped
Write swap / leave
Perform a FINAL pass to show nothing changes

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

How do you find the pivot of a quick sort for even and odd n (where n is the number of letters / numbers)

A

(n + 1) / 2 if n is odd
if n is even round up

17
Q

What are the steps of a quick sort (ascending) (6)

A

1) Choose the item at the midpoint of the list to be the first pivot ((n+1)/2)
2) Write down all the items that are less than the pivot, keeping their order, in a sub list
3) Write down the pivot
4) Write down the remaining items ( greater than the pivot) in a sub list
5) Apply steps 1 to 4 for each sub list
6) When all items have been chosen as pivots, stop

18
Q

Perform a quick sort on 8, 3, 6, 4, 2 into ascending order

A

1) 8, 3, (6), 4, 2
2) 3, (4), 2, (6), (8)
3) 3, (2) (4), (6), (8)
4) (2), (3), (4), (6), (8)

19
Q

What are bin packing algorithms

A

Algorithms that allow us to put different sized items into bins, so that there is the least amount of wasted space and the least number of bins is used

20
Q

What are examples of bin packing uses

A

Production lines
Files on a hard disk
Packing items into a lorry

21
Q

What is the lower bound in bin packing

A

The least number of bins required for packing

22
Q

Is the lower bound in bin packing always achievable

A

NO

23
Q

What does it mean if a solution for bin packing is the lower bound

A

Solution = optimal solution

24
Q

What is the formula for lower bound in bin packing

A

Total size of all items / bin size
(round up)

25
Q

What is a first-fit algorithm

A

Take each item in the order it is given
Place it into the first available bin it will fit

26
Q

Pros and cons of first fit algorithm

A

+ Easy to implement
- Not likely to be efficient

27
Q

What is a first-fit decreasing algorithm

A

Sort items into descending order
Apply first fit algorithm

28
Q

Pros and cons of first-fit decreasing algorithm

A

+ Usually a good solution
- May not be optimal solution

29
Q

What is a full-bin packing algorithm

A

Put together items that will completely fill a bin
Place any remaining items using first-fit algorithm

30
Q

Pros and cons of full-bin backing algorithm

A

+ Usually get a good solution
- Difficult to implement

31
Q

What is the equation when time is proportional to number of items (n)

A

t = kn

32
Q

What is the equation when time is proportional to number of items squared (n^2)

A

t = kn^2

33
Q

What is the equation when time is proportional to number of items cubed (n^3)

A

t = kn^3

34
Q

What does the order / complexity / size of problem of an algorithm mean

A

Whether time is proportional to number of items linear / quadratic / cubed

35
Q

What is the time taken to complete an algorithm also called

A

Run time

36
Q

What is important about values worked out for run time

A

They are estimates

37
Q

The bubble sort algorithm has quadratic order. Given that it takes a computer 0.2 seconds to sort a list of 1600 numbers using the bubble sort, estimate the time needed to sort a list of 480,000 numbers

A

t proportional to n^2
t = kn^2
0.2 = k * 1600^2
k = 7.8125 * 10^-8
t = 7.8125 * 10^-8 * n^2
t = 180,000 seconds
t = 5 hours

38
Q

A bubble sort algorithm has quadratic order, comment on the suitability of the bubble sort algorithm for sorting large data sets

A

Since the time taken increases by a factor of the number of items squared, this algorithm is NOT suitable for sorting large data sets of items