GCSE Computer Science > 2.1 Algorithms > Flashcards

2.1 Algorithms Flashcards

(70 cards)

Study These Flashcards
1
Q

What is an algorithm?

A

A set of instructions for solving a problem or completing a task.

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

What is abstraction?

A

Ignoring or filtering out the unnecessary details in order to simplify the problem.

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

What is decomposition?

A

Breaking down a large problem into smaller sub-problems.

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

What is algorithmic thinking?

A

Identifying the steps involved in solving a problem, in other words, designing the algorithm.

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

What is pattern recognition?

A

Looking for similarities among and within problems.

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

What are the principles of computational thinking?

A
  • decomposition
  • pattern recognition
  • abstraction
  • algorithms
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

State the two standard searching algorithms

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

What is a searching algorithm?

A

These allow a set of data to be examined and for a specific item to be found

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

What are the main steps involved in a linear search?

A
  • List doesn’t have to be sorted
  • Look at each item in turn. Is it the one you’re looking for?
  • If so, then you’ve found it. If not then look at the next item.
  • If however, you reach the end of the list before
    finding the item, then the item is NOT in the list!!!
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the main steps involved in a binary search?

A
  • list must be sorted
  • Start by setting the counter to the middle position in the list.
  • If the value held there is a match, the search ends.
  • If the value at the midpoint is less than the value to be found, the list is divided in half. The lower half of the list is ignored and the search keeps to the upper half of the list.
  • If the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list.
  • The search moves to the midpoint of the remaining items. Steps 2 through 4 continue until a match is made or there are no more items to be found.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the worst case scenario for a binary search?

A

n + 1

Where n = number of times data set can be halved

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

What is the best case scenario for a binary search?

A

1

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

What is the worst case scenario for a linear search?

A

N
Where N is the number of items in the data set

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

What is the best case scenario for a linear search algorithm?

A

1

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

What are three differences between binary and linear search algorithms?

A

BINARY:
- data must be ordered
- worst case scenario is n + 1 (where n = number of times the list can halve itself)
- longer + more complex to write

LINEAR:
- data does not need to be ordered
- worst case scenario = N, where N = number of items in the data set
- simpler to write

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

What are the pre-requisites for a binary search algorithm?

A

The list of data must already be sorted

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

What are the pre-requisites for a linear search algorithm?

A

It does not require any pre-requisites

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

State the 3 standard sorting algorithms.

A
  • bubble sort
  • merge sort
  • insertion sort
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is a sorting algorithm?

A

These allow a data set to be sorted into order

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

Why do computers work more efficiently with sorted lists?

A

This allows computers to use a binary search, which is far more efficient than a linear search.

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

Describe the main steps of bubble sort

A

Start with the leftmost item
• Compare this item with the one next to it
• If the one next to it is less, swap the items
• Repeat for all the other items
• At the end of one pass through the list, the largest item is at the end of the list
Repeat the process until the items are sorted

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

What is a pass in the bubble sort algorithm?

A

Each run through the list, from start to finish.

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

Are there any pre-requisites for bubble sort?

A

No

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

Describe the main steps of insertion sort.

A

An insertion sort compares values in turn, starting with the second value in the list.

If this value is greater than the value to the left of it, no changes are made.

Otherwise this value is repeatedly moved left until it meets a value that is less than it.

The sort process then starts again with the next value.

This continues until the end of the list is reached.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Are there any pre-requisites for insertion sort?
No
26
Describe the main steps of merge sort.
Divide the unsorted list in two • Continue to divide these lists into two until there is just one item in each list • Now merge each list back by: 1) reading the item from list A, and reading the item from list B 2) writing the smaller to output list 3) reading the next item from the list that held the smaller value 4) repeating until all items are written to output list.
27
Are any pre-requisites required for merge sort?
No
28
Order the sorting algorithms from least to most efficient (generally).
1) bubble sort 2) insertion sort 3) merge sort
29
How will Bubble Sort’s performance compare with the other sorting algorithms when the list is small / largely ordered.
Its performance will be similar, if not better
30
How many passes will be required to complete a bubble sort algorithm?
n - 1 passes, where n = number of elements in the list.
31
What does an oval represent in flowcharts?
A terminal (start / end)
32
What does a rhombus represent in flowcharts?
A decision (n > 3?)
33
What does a parallelogram represent in flowcharts?
An input/output
34
What does an arrow represent in flowcharts?
A line, shows the direction of the flow
35
What does a rectangle represent in flowcharts?
A process (e.g. count = count + 1)
36
What does a rectangle with 2 parallel vertical lines represent in flowcharts?
A sub-program
37
What is a sub-program?
Sub programs are used when you wish to call another procedure or function
38
What is a variable?
A variable is a location in memory in which you can temporarily store a value such as a string or number. This value can be changed while the program is running.
39
What are the three programming constructs?
- sequence - selection - iteration
40
What are the three programming constructs used for?
To control the flow of a program
41
What is sequence?
A sequence is a series of steps which are completed one after the other In a flow diagram they are shown as process, input or output symbols shown one after the other
42
What is selection?
Selection is the ability to choose different paths through a program In flowcharts, decision symbols are used for selection
43
What is iteration?
Iteration means repeating a part of a program, and is also referred to as repeating or looping In flowcharts, iteration is shown by using arrows that repeat a section of the flowchart. A decision will control whether more iterations are required
44
What are algorithms usually written as?
- pseudocode - a flow diagram
45
What must be considered in order to decompose a problem?
What are the inputs into the problem? What will be the outputs of the problem? In what order do instructions need to be carried out? What decisions need to be made in the problem? Are any areas of the problem repeated?
46
What are structure diagrams?
a visual way of breaking down a problem into smaller parts. They show how a problem is organised by dividing it into components and are frequently used when designing systems. Each box on the diagram represents a separate part with lines showing how each one connects or depends upon the other.
47
What is pseudocode?
A simple way of describing a set of instructions in a manner that resembles a programming language.
48
What are the two types of errors that can occur in algorithms?
- syntax errors - logic errors
49
What is a syntax error?
syntax error occurs when code written does not follow the rules of the programming language.
50
What is a logic error?
A logic error is an error in the way a program works. The program simply does not do what it is expected to do.
51
State 3 common logic errors.
- unintentionally creating a situation where an infinite loop may occur - incorrectly using logical operators, eg expecting a program to stop when the value of a variable reaches 5, but using <5 instead of <=5 - incorrectly using brackets in calculations
52
State three common syntax errors
- misspelling a statement, eg writing pint instead of print - using a variable before it has been declared - missing brackets, eg opening a bracket but not closing it
53
What are trace tables?
Can be used to determine what an algorithm/program does by determining its output, given a set of inputs. It does this by recording the value of each variable as it changes by ‘tracing’ through the program line by line.
54
What must trace tables have columns for?
- each variable - any conditions being tested which affect the flow of the program (selection and iteration) - any output from the program
55
What is an integer?
A whole number
56
What is a real/float?
A number with a decimal point?
57
What is a Boolean?
Either true or false
58
What is a character?
A single alphabetic or numeric character
59
What is a string?
A sequence of one or more characters
60
State the 5 data types.
- integer - real - Boolean - character - string
61
What are the 5 Boolean operators?
> greater than >= greater than or equal to < less than <= less than or equal to == equal to != not equal to
62
What are Boolean operators used for?
To compare two values
63
What are Boolean expressions?
A Boolean expression evaluates to TRUE or FALSE
64
How is sequence shown in pseudocode?
By placing statements one below the other: they will be executed in the order they are written.
65
How is selection shown in pseudocode?
Using an IF statement: if…then else endif
66
What is the switch/case statement in pseudocode?
The switch/case statement is used if there are several possible options to be tested. SEE GC LESSON 5
67
What are the 3 main types of iteration statements in pseudocode?
for…next while…endwhile do…until
68
When is the for…next loop used?
when you want to execute the loop a specific number of times
69
When is the while…endwhile loop used?
when you want to execute the loop while a certain condition is true.
70
When is the do…until loop used?
when you want to execute the loop until a certain condition is true • The condition is tested at the end of the loop
GCSE Computer Science
flashcards
Decks in class (10)
# Cards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2026 Bold Learning Solutions. Terms and Conditions