Brainscape's Knowledge GenomeTM

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


See full index

GCSE Computer Science OCR (My cards) > Section Four - Algorithms > Flashcards

Section Four - Algorithms Flashcards

You may prefer our related Brainscape-certified flashcards:
GCSE Geography - AQA flashcards GCSE Religious Studies - Edexcel Route B flashcards GCSE Religious Studies - Eduqas Route A flashcards GCSE Religious Studies - Edexcel Route A flashcards GCSE Religious Studies - Eduqas Route B flashcards Biology 101 flashcards
1
Q

What are the three KEY techniques for computational thinking?

A

Decomposition
Abstraction
Algorithmic Thinking

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

What is Decomposition?

A

Breaking a complex problem down into smaller problems and solving each other individually

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

What is Algorithmic Thinking?

A

A logical way of getting from the problem to the solution.

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

What are two ways you can write algorithms?

A

Psuedocode

Flow diagrams

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

What are Algorithms?

A

Sets of instructions for solving a problem

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

Fill in the Gaps:

Flow diagrams use (1) for different (2)

A

(1) Different Boxes

(2) Commands

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

What boxes are the BEGINNING and END of the algorithm put into?

A

Boxes with rounded corners

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

What is put in a parallelogram box?

A

Inputs/Outputs -

Anything that is put into or taken out of the algorithm

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

What boxes are INSTRUCTIONS, PROCESSES and CALCULATIONS put into?

A

Rectangular boxes

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

What is put in a diamond box?

A

Decisions -

such as ‘yes’ or ‘no’ questions

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

What is the purpose of ARROWS in flow diagrams?

A

Connect boxes and show the direction you should flow.

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

True or False?

Boxes in flow diagrams can only have ONE arrow coming in or going out?

A

False

Boxes in flow diagrams can have MULTIPLE arrows coming in or going out of them

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

What is the difference between BINARY searches and LINEAR searches?

A

A Binary Search looks for items in an Ordered List whereas a Linear Search can be used on an Unordered List.

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

Fill in the Gaps:

A linear search is much (1) than a binary search but not as (2).

A

(1) simpler

(2) efficient

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

What type of sort COMPARES pairs of items?

A

A Bubble Sort

17
Q

What is a bubble sort algorithm used for?

A

To sort an unordered list of items

18
Q

What are the advantages of a bubble sort algorithm?

A

It’s simple and can be easily implemented
It’s efficient to check if a list is already in order
Doesn’t use much memory

19
Q

What are the disadvantages of a bubble sort algorithm?

A

It’s inefficient to sort a list

It doesn’t cope well with large lists of items

20
Q

What is a merge sort algorithm an example of?

A

A divide-and-conquer algorithm

21
Q

True or False?

A Merge Sort SPLITS the list apart and then MERGES it back together

A

True

22
Q

What two facts does a merge sort algorithm take advantage of?

A

Small lists are easier to sort than larger lists

It’s easier to manage two ordered lists than two unordered lists

23
Q

What are the advantages of a merge sort algorithm?

A

More efficient and quicker than bubble sort and insertion sort
Very consistent running time

24
Q

What are the disadvantages of a merge sort algorithm?

A

Slower than other algorithms for small lists
Even if the list is already sorted it’ll go through the entire process
It uses more memory

25
Q

What programming languages is the merge sort algorithm (or variations) used in and why?

A

Java, Python and Perl

Because it’s efficient.

26
Q

How does an Insertion Sort work?

A

It takes each item in turn and puts it in the right place using the first item in the list as a starting point

27
Q

What are the advantages of an insertion sort algorithm?

A

Very intuitive way of sorting and can be easily coded
Copes well with small lists
Doesn’t require much additional memory
Quick to add items to the sorted list
Quick at checking the list is already sorted

28
Q

What is the main disadvantage of an insertion sort algorithm?

A

It doesn’t cope well with very large lists

29
Q

Order the four steps of a BINARY SEARCH algorithm:

  • 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.
  • Find the middle item in the ordered list.
  • If this is the item you’ve been looking for, then stop the search - you’ve found it.
  • You’ll be left with a list that is half the size of the original list. Repeat previous steps on this smaller list to get an even smaller one. Keep going until you find the item you’re looking for.
A

1-Find the middle item in the ordered list.

2-If this is the item you’ve been looking for, then stop the search - you’ve found it.

3-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.

4-You’ll be left with a list that is half the size of the original list. Repeat previous steps on this smaller list to get an even smaller one. Keep going until you find the item you’re looking for.

30
Q

Order the four steps of a LINEAR SEARCH algorithm:

  • Repeat steps 2-3 until you find the item you’re looking for or you’ve checked every item.
  • Look at the first item in the unordered list
  • If not, then look at the next item in the list
  • If this is the item you’re looking for, then stop the search - you’ve found it.
A

1-Look at the first item in the unordered list

2-If this is the item you’re looking for, then stop the search - you’ve found it.

3-If not, then look at the next item in the list

4-Repeat steps 2-3 until you find the item you’re looking for or you’ve checked every item.

31
Q

Order the five steps of a BUBBLE SORT algorithm:

  • Move on to the next pair of items (2nd and 3rd entries) and repeat the second step
  • Repeat the third step 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.
  • If they’re in the right order, you don’t have to do anything. If they’re in the wrong order, swap them.
  • Look at the first two items in the list
  • Repeat previous steps until there are no swaps in a pass
A

1-Look at the first two items in the list

2-If they’re in the right order, you don’t have to do anything. If they’re in the wrong order, swap them.

3-Move on to the next pair of items (2nd and 3rd entries) and repeat the second step

4-Repeat the third step 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.

5-Repeat previous steps until there are no swaps in a pass

32
Q

Order the four steps of a MERGE SORT algorithm:

  • Repeat the third step until you’ve merged all the sub-lists together
  • 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 the right order
  • Split the list in half (the smaller lists are called sub-lists) - the second sub-list should start at the middle item
  • Keep repeating the first step on each sub-list until all the lists only contain one item.
A

1-Split the list in half (the smaller lists are called sub-lists) - the second sub-list should start at the middle item

2-Keep repeating the first step on each sub-list until all the lists only contain one item.

3-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 the right order

4-Repeat the third step until you’ve merged all the sub-lists together

33
Q

Order the three steps of an INSERTION SORT algorithm:

  • Look at the second item in a list
  • Repeat the second step for the third, fourth, fifth, etc. items until the last number in the list has been inserted into the correct place
  • Compare it to all items before it (in this case just the first item) and insert the number into the right place
A

1-Look at the second item in a list

2-Compare it to all items before it (in this case just the first item) and insert the number into the right place

3-Repeat the second step for the third, fourth, fifth, etc. items until the last number in the list has been inserted into the correct place

GCSE Computer Science OCR (My cards) (7 decks)

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