Brainscape's Knowledge GenomeTM

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


See full index

GCSE Computer Science > Algorithms > Flashcards

Algorithms Flashcards

1
Q

What is Decomposition?

A
  • breaking a complex problem down into smaller problems & solving each one individually
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is Algorithmic Thinking?

A
  • a logical way of getting from the problem to the solution
  • if the steps you take to solve a problem follow an algorithm then they can be reused & adapted to solve similar problems in the future
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is Abstraction?

A
  • picking out the important bits of information from the problem, ignoring the specific details that don’t matter
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q
A

Start/Stop

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

Processes

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

Input/Output

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

Decision

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

Sub Program

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

Arrows

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

What does binary search look for?

A
  • Items in an ordered list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the first stage in binary search?

A
  • Find the middle item in the ordered list
  • To find the middle item in a list of n items do (n + 1) / 2 & round up if necessary
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the second stage in binary search?

A
  • If this is the item you’re looking for, then stop the search - you’ve found it
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the third stage in binary search?

A
  • If not, compare the item you’re looking for to the middle item
  • If it comes before the middle item, get rid of the second half of the list
  • If it comes after the middle item, get rid of the first half of the list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the fourth stage in binary search?

A
  • You’ll be left with a list that is half the size of the original list
  • Repeat stages 1 to 3 on this smaller list to get an even smaller one
  • Keep going until you find the item you’re looking for
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are linear searches used on?

A
  • an unordered list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the first stage in linear search?

A
  • Look at the first item in the unordered list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the second stage in linear search?

A
  • If this is the item you’re looking for - then stop the search - you’ve found it
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is the third stage in linear search?

A
  • If not, then look at the next item in the list
19
Q

What is the fourth stage in linear search?

A
  • Repeat stages 2 & 3 until you find the item that you’re looking for or you’ve checked every item
20
Q

Compare linear search to binary search

A
  • Linear search is much simpler than binary search but not as efficient
  • Linear search can be used on any type of list, it doesn’t have to be ordered
  • Due to it being inefficient, a linear search is often only used on small lists
  • However once the list has been ordered, a binary search is much more efficient than a linear search
  • In general a binary search takes fewer steps to find the item you’re looking for, which makes it more suitable for larger lists of items
21
Q

What does a bubble sort compare?

A
  • compares pairs of items
22
Q

What is a bubble sort used for?

A
  • to sort an unordered list of items
23
Q

What is the first stage in bubble sort?

A
  • Look at the first two terms in the list
24
Q

What is the second stage in bubble sort?

A
  • If they’re in the right order, you don’t have to do anything
  • If they’re in the wrong order, swap them
25
Q

What is the third stage in bubble sort?

A
  • Move on to the next pair of items (the 2nd & 3rd entries’ & repeat stage 2
26
Q

What is the fourth stage in bubble sort?

A
  • Repeat stage 3 until you get to the end of the list - this is called one pass
  • The last item will now be in the correct place, so don’t include it in the next pass
27
Q

What is the fifth stage in bubble sort?

A
  • Repeat stages 1 to 4 until there are no swaps in a pass
28
Q

Why is bubble sort considered as one of the simplest sorting algorithms?

A
  • Only ever focuses on two items rather than the whole list of items
29
Q

What are the pros of bubble sort?

A
  • It’s a simple algorithm that can be easily implemented on a computer
  • It’s an efficient way to check if a list is already in order. For a list of n items you only have to do one pass of (n - 1) comparisons to check if the list is ordered or not
  • Doesn’t use very much memory as all the sorting is done using the original list
30
Q

What are the cons of bubble sort?

A
  • It’s an unefficient way to sort a list - for a list of n items, the worst case scenario would involve you doing (n(n-1) / 2) comparisons
  • Due to being inefficient, the bubble sort algorithm does not cope well with a very large list of items
31
Q

What type of algorithm is a merge sort?

A
  • divide & conquer
32
Q

What makes the merge sort useful?

A
  • Small lists are easier to sort than large lists
  • It’s easier to merge two ordered lists than two unordered lists
33
Q

What is the first step of the merge sort?

A
  • Split the list in half (the smaller lists are called sub-lists)
  • The second sub-list should start at the middle item
34
Q

What is the second step of the merge sort?

A
  • Keep repeating step 1) on each sub-list until all the lists only contain one item
35
Q

What is the third step of the merge sort?

A
  • Merge pairs of sub-lists so that each sub-list has twice as many items
  • Each time you merge sub-lists, sort the items into a right order
36
Q

What is the fourth step of the merge sort?

A
  • Repeat step 3) until you’ve merged all the sub-lists together
37
Q

What are the pros of merge sort?

A
  • In general it’s much more efficient & quicker than the bubble sort & insertion sort algorithms for large lists
  • It has a very consistent running time regardless of how ordered the items in the original list are
38
Q

What are the cons of merge sort?

A
  • It’s slower than other algorithms for smaller lists
  • Even if the list is already sorted it still goes through the whole splitting & merging process
  • It uses more memory than the other sorting algorithms in order to create the seperate lists
39
Q

What is the first step of insertion sort?

A
  • Look at the second item in a list
40
Q

What is the second step of insertion sort?

A
  • Compare it to all items before it (in this case just the first item)
  • Insert the number into the right place
41
Q

What is third step of insertion sort?

A
  • Repeat step 2) for the third, fourth, fifth, etc. items until the last number in the list has been inserted into the correct place
42
Q

Why are insertion sorts advantageous over other sorting algorithms?

A
  • It’s an intuitive way of sorting things & can be easily coded
  • Copes very well with small lists - for this reason, an insertion/merge hybrid sort is often used to take advantage of the strengths of each algorithm
  • All the sorting is done on the original list, so, like the bubble sort, it doesn’t require very much additional memory
  • It’s very quick to add items to an already ordered list
  • It’s also very quick at checking that a list is already sorted
43
Q

What are the disadvantages of bubble sort?

A
  • Doesn’t cope well w/ large lists
  • For a list containing n items:
    1) Best case scenario (when the list is already ordered) requires n-1 comparisons
    2) Worst case scenario requires n(n-1) / 2 comparisons

GCSE Computer Science (1 decks)

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