SLR 2.1 Algorithms Flashcards Preview

GCSE Computer Science > SLR 2.1 Algorithms > Flashcards

Flashcards in SLR 2.1 Algorithms Deck (27)
Loading flashcards...
1
Q

In Computer Science what is ‘abstraction’?

A

‘abstraction’ means to ignore unnecessary details - e.g when giving instructions how to travel to somewhere we don’t mention every lamp-post and house you go past.

2
Q

In Computer Science what is ‘decomposition’?

A

‘decomposition’ means breaking a problem down into smaller chunks that are more easily solved.

3
Q

In Computer Science what is an ‘algorithm’?

A

An ‘algorithm’ is a series of instructions that combine to solve a problem.

4
Q

Which of these two search algorithms is easier to code?

a. binary search
b. linear search

A

b. linear search

5
Q

Which of these two search algorithms is usually more efficient?

a. binary search
b. linear search

A

a. binary search

6
Q

What is the precondition that must be true before we can use a binary search?

A

The data must be ordered

7
Q

How does a linear search work?

A

Each item in turn from the data set is compared with the target until either the target item is found or the end of the list is reached.

8
Q

How does a binary search work?

A

The data set MUST be ordered. The middle item (round down if an even number of items) is compared to the target. If the item is not the target then a check is run to see whether the target would appear ‘above’ (further forward in the list) or ‘below’ (further back in the list) - if it is present at all, which it may not be.
If the item would appear above the original mid point then a new mid point at the centre of the upper-half (all items above the original mid-point) is chosen.
Else if the item would appear below the original mid point a new mid point at the centre of the lower-half (all items below the original mid point) is chosen.
The process is then repeated with the new mid point until either the target is found OR the last item has been checked and the item has been proven not to be in the data set.

9
Q

Which search algorithm is represented by the following pseudocode?

found = False
number = 0
target = value
WHILE found == False AND number < LEN(book)
	IF data[number] == target
		found = True
	number = number + 1
END WHILE
IF found == True
	PRINT “target found”
ELSE
	PRINT “target not data”
END IF
A

a linear search

10
Q

Which search algorithm is represented by the following pseudocode?

found = False
left = 0
right = LEN(data) - 1
target = value

WHILE found == False and left <= right
mid = (left + right) DIV 2

    IF data[mid] == target
        found = True
    ELSE
        IF target > data[mid]:
            left = mid + 1
        ELSE
            right = mid - 1
        END IF
    END IF
END WHILE
IF found == True
	print("target found")
ELSE
	print("target not in data")
END IF
A

a binary search

11
Q

Which search algorithm is most efficient if the target item is near the start of the data set?

A

The linear search

12
Q

Which sort algorithm makes repeated passes of the data set and guarantees to move one item at a time to the end of the data set?

A

A bubble sort

13
Q

What is the effect of this snippet of pseudocode?

items = ["y", "x"]
i = 1
if items [ i - 1 ] > items [ i ]:
    temp = items [ i - 1 ]
    items [ i - 1 ] = items [ i ]
    items [ i ] = temp
A

it swaps the items so that they become [“x”, “y”]

14
Q

Why is temp used in this snippet of pseudocode?

items = ["y", "x"]
i = 1
if items [ i - 1 ] > items [ i ]:
    temp = items [ i - 1 ]
    items [ i - 1 ] = items [ i ]
    items [ i ] = temp
A

Because otherwise the value of items [ i - 1 ] would be lost (it would be overwritten by the value of items [ i ]

15
Q

How does a merge sort work?

A
  1. The set of unsorted data is split into two
  2. Step 1 is repeated with each new unsorted data set until we have single items (so 16 unsorted items is split into 2 sets of 8 unsorted items, then 4 sets of 4 unsorted items then 8 sets of 2 unsorted items and finally 16 sets of 1 item each - 1 item is considered sorted)
  3. Pairs of sorted data sets (started with single items) are merged into a new sorted data set
  4. Step 3 is repeated until 1 fully sorted data set exists (so 16 sets of 1 sorted item becomes 8 sets of 2 sorted items then 4 sets of 4 sorted items etc.)
16
Q

How does an insertion sort work?

A

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. As the items are met they are inserted into the correct position within the items that have already been met.

17
Q

What is pseudocode?

A

Pseudocode is a detailed, yet readable description of what a program must do. It can be turned into many different languages by a competent programmer.

18
Q

What does a diamond-shaped flowchart symbol represent?

A

A decision

19
Q

What does a rectangular flowchart symbol represent?

A

A process

20
Q

What does a flowchart symbol of a rectangle with rounded ends represent?

A

A terminator

21
Q

What does a flowchart symbol of a rectangle with additional parallel lines at the sides represent?

A

A sub-routine

22
Q

What does a flowchart symbol of a parallelogram represent?

A

An input or an output

23
Q

Give two advantages of decomposition

A
  • Making problems easier to solve.
  • Different people can work on different parts of a problem…
  • …reducing development time.
  • Program components developed in one program can be reused in other programs.
24
Q

What is an abstract model?

A

Any model of a system which has been taken from, or based on (abstracted) a real life situation or problem.

25
Q

What are system inputs?

A

Anything which will be required to go into a system in any form in order for it to operate as intended. These inputs are then processed by the system following the rules or algorithms of the system.

26
Q

What are system outputs?

A

Anything which exits a system in any form in order for it to operate as intended. These outputs are often the result of complex processing of inputs along with other data.

27
Q

What are solution preconditions?

A

Any condition which pre-exists the suggested solution. For example for a road traffic speed camera program their would be pre-conditions which could be as simple as requiring the camera to be in place ready to be triggered by passing cars.