Brainscape's Knowledge GenomeTM

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


See full index

Computer Science A-Level > Section 8: Algorithms > Flashcards

Section 8: Algorithms Flashcards

1
Q

Chapter 44:

What is a Recursive Subroutine?

A

A subroutine (e.g. function) that calls itself as part of the execution.

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

Chapter 44:

What are the 3 characteristics of a Recursive Subroutine?

A

A Stopping Condition or “Base Case” must be included, which allows the Recursive Subroutine to unwind.

If the Stopping Condition is not met, the routine must call itself.

The Stopping Condition must be met in a finite number of calls.

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

Chapter 44:

How might a Recursive Subroutine calculate the factorial of an integer?

A 
SUB CallFactorial(n)
    IF n == 0 THEN
        factorial = 1
    ELSE
        factorial = n * CallFactorial(n-1)
    ENDIF
    RETURN factorial
ENDSUB
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Chapter 44:

What concept do Recursive Algorithms rely on to recall progress from the called line?

A

Stacks.
When a subroutine is called, the current values are added to a stack for later retrieval.
New values may be assigned (local variables) and some may be carried through to the next layer of the stack (parameters).

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

Chapter 44:

What are 3 related examples of where Recursion is used?

A

In-Order, Pre-Order, Post-Order Tree Traversal.

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

Chapter 44:

How would you construct a Recursive In-Order Tree Traversal in pseudocode?

A 
SUB inOrderTraversal(p)
    IF tree[p].left != -1 THEN
        inOrderTraversal( tree[p].left )
    ENDIF
    OUTPUT ( tree[p].data )
    IF tree[p].right != -1 THEN
        inOrderTraversal( tree[p],right )
    ENDIF
ENDSUB
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Chapter 44:

How would you construct a Recursive Pre-Order Tree Traversal in pseudocode?

A 
SUB preOrderTraversal(p)
    OUTPUT ( tree[p].data )
    IF tree[p].left != -1 THEN
        preOrderTraversal( tree[p].left )
    ENDIF
    IF tree[p].right != -1 THEN
        preOrderTraversal( tree[p],right )
    ENDIF
ENDSUB
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Chapter 44:

How would you construct a Recursive Post-Order Tree Traversal in pseudocode?

A 
SUB postOrderTraversal(p)
    IF tree[p].left != -1 THEN
        postOrderTraversal( tree[p].left )
    ENDIF
    IF tree[p].right != -1 THEN
        postOrderTraversal( tree[p],right )
    ENDIF
    OUTPUT ( tree[p].data )
ENDSUB
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Chapter 45:

What is the name given to how much time an algorithm takes to execute?

A

Time Complexity.

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

Chapter 45:

What are the 4 main types of algebraic function?

A

Linear,
Polynomial,
Exponential,
Logarithmic.

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

Chapter 45:

What does the ‘O’ in Big-O notation stand for?

A

Order.

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

Chapter 45:

What does Big-O notation refer to?

A

Time Complexity.

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

Chapter 45:

What does O(1) refer to?

A

An algorithm that takes constant time with variable inputs. (Always takes the same amount of time).

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

Chapter 45:

What does O(n) refer to?

A

An algorithm that takes linear time.

The time taken is directly proportional to the size of the data.

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

Chapter 45:

What does O(n^2) refer to?

A

An algorithm that takes polynomial time.

The time taken is directly proportional to the square of the size of the data.

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

Chapter 45:

What does O(2^n) refer to?

A

An algorithm that takes exponential time.

The time taken will double with every new item.

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

Chapter 45:

What does O(log n) refer to?

A

An algorithm that takes logarithmic time.

The time taken will slowly increase as the size of the data increases.

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

Chapter 45:

What does O(n!) refer to?

A

An algorithm that takes factorial time.

The time taken will quickly increase as the size of the data increases.

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

Chapter 46:

What is Linear Search?

A

Where you incrementally search through all data spaces (in order), to find what you are looking for.

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

Chapter 46:

What is it called when you incrementally search through all data spaces (in order), to find what you are looking for?

A

Linear Search.

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

Chapter 46:

What is the Time Complexity of Linear Search?

A

O(n)

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

Chapter 46:

What is Binary Search?

A

A Divide and Conquer approach to searching a list.
You first check the middle item of the data spaces.
If the target item is not found, and the value in the middle is greater than the target, we consider the sublist of all the items to the left of the middle.
If the target item is not found, and the value in the middle is less than the target, we consider the sublist of all items to the right of the middle.
Repeat until the target is found, or there are no more sublists to check.

23
Q

Chapter 46:
What is an advantage of using Binary Search over Linear Search?
(Be specific)

A

Binary Search can find most target locations quicker, as you don’t check every item up to the target.
Specifically, the Binary Search has a time complexity of O( log(n) ), whereas Linear Search has a time complexity of O(n).

24
Q

Chapter 46:

What is a disadvantage of using Binary Search over Linear Search?

A

Binary Search can only be successfully performed on an ordered list, whereas Linear Search can be performed on any list.

25
Q

Chapter 46:

What structure does a Binary Search usually take?

A

Recursive Algorithm.

26
Q

Chapter 46:

What is a searching algorithm for a Binary Tree like?

A

Binary Search Algorithm.
The starting node is the middle value.
If the target is less than the middle value, we look to the left of the starting node.
We then repeat until the target value is found or there are no more values to check.

27
Q

Chapter 46:

What is the simplest, but least efficient Sorting Algorithm?

A

Bubble Sort.

28
Q

Chapter 46:

How does the Bubble Sort work?

A

Cycle:
Look at the first item.
Look at the second item.
If the first is larger than the last, switch.
Consider the second item to be the first.
Continue until there are no more spaces to check.

Break the Cycle at the first instance where a Cycle has not switched any positions.

29
Q

Chapter 46:

What is the Time Complexity of the Bubble Sort Algorithm?

A

O(n^2)

30
Q

Chapter 46:

How does the Merge Sort work?

A

Divide the unsorted list into n sublists, each of length 1. (n = length of list).
Merge the sublists together, in order, until there is only 1 sublist remaining.

31
Q

Chapter 46:

How does the Merge process of the Merge Sort Algorithm work?

A

Given 2 lists: list1, and list2, each with an index variable ind1, and ind2 respectively, both starting at 0.

Check the item at ind1 and ind2 in list1 and list2 respectively.
Add the smaller value to the mergeList.
If list1 had the smaller value, increment ind1.
If list2 had the smaller value, increment ind2.

Once either ind1 or ind2 reaches the length of their corresponding list, add the remaining items from the other list to the end of mergeList.

32
Q

Chapter 46:

What kind of Algorithm is the Merge Sort?

A

Divide and Conquer.

33
Q

Chapter 46:

What is the Time Complexity of the Merge Sort?

A

O( n log(n) )

34
Q

Chapter 46:

What is Space Complexity?

A

The amount of Resources, such as memory, that the Algorithm requires.

35
Q

Chapter 46:
In terms of Space Complexity, what is better:
Bubble Sort, or Merge Sort?
Why?

A

Bubble Sort.

Bubble Sort requires n+1 spaces in memory: 1 for every n elements, and 1 temp value used in switching values.
Merge Sort requires roughly n + sum( x(n/x) while 2^x < n). In other words, Merge Sort requires a lot more memory.

36
Q

Chapter 46:

*Who Created the Merge Sort Algorithm?

A

John Von Neumann.

37
Q

Chapter 47:

What are the 2 types of graph traversal?

A

Depth-First

Breadth-First

38
Q

Chapter 47:

What Data Structure does Depth-First Traversal use?

A

Stack.

39
Q

Chapter 47:

What Data Structure does Breadth-First Traversal use?

A

Queue.

40
Q

Chapter 47:
What is used to represent a graph digitally?
What Data Structure is used to implement it?

What is a Disadvantage of using this method?
Why is it not that bad?

A

An Adjacency List implemented by creating a dictionary.
The Keys of the dictionary are the nodes, and the data is a list of neighbours.

A disadvantage is that, when reassembled, the graph is unlikely to look the same as it was initially imagined. This isn’t a huge problem because it will be logically the same; it will work the same.

41
Q

Chapter 47:

Explain the difference between Depth-First and Breadth First Traversal.

A

Depth-First uses a stack to keep track of the previously visited node. We add the current node to visited nodes, select a neighbour, push the current node to the stack, and recursively call the subroutine with the neighbour as the main node. When we reach a node with no neighbours, recursion unwinds until all nodes have been visited.

Breadth-First takes a starting node, and adds all of its neighbours to a queue. We then take the first item of the queue and repeat the subroutine: note the node in visited nodes, add the new neighbours to the queue, move along in the queue.

42
Q

Chapter 47:

Where might Depth-First be used?

A

Scheduling Jobs, where a series of tasks is to be performed, and certain tasks must be completed before another can start.

Solving mazes, where the maze can be represented as a graph.

43
Q

Chapter 47:

Where might Breadth-First be used?

A

Finding the Shortest Path between two points. GPS Navigation.

Social Media, friend connection.

Web Crawlers.

44
Q

Chapter 48:

What is the most popular shortest path algorithm

A

Dijkstra’s Algorithm.

45
Q

Chapter 48:

How does Dijkstra’s Algorithm work?

A

Start with the base node with a distance 0.
Every other node will have a starting distance of infinity.

Shade the starting node dark to show that it has been visited. Look at the neighbours of the starting nodes. Compare the old queue values for the neighbours to the current node value + arc length, and assign the smaller value. Reorder the queue in order of ascending value.

Move along in the queue. And repeat until the queue is empty.

46
Q

Chapter 49:

What does Tractable mean?

A

Easy to control or influence.

47
Q

Chapter 49:

What does Intractable mean?

A

Hard to control or influence.

48
Q

Chapter 49:

Is a problem that takes polynomial-time tractable or intractable?

A

Tractable.

O(n), O(n log n), O(n^k)

49
Q

Chapter 49:

Is a problem with a time complexity worse than polynomial-time tractable or intractable?

A

Intractable.

O(2^n), O(n!)

50
Q

Chapter 49:

What is a Heuristic Method?

A

A method that takes shortcuts to cut down the time complexity. Gives an estimate instead of a definite result.

An approach might be to simplify the question, taking the most significant values.

An approach for optimisation might be to get a good answer quickly, rather than the best answer slowly.

51
Q

Chapter 49:

What is the Entscheidungsproblem?

A

German for “Decision Problem”.

David Hilbert and Wilhelm Ackermann proposed a theoretical machine that takes any input, and processes it to give an answer “yes” or “no”.

It was first disproven by Alonzo Church in 1935, then again by Alan Turing in 1936 with the Halting Problem.

52
Q

Chapter 49:

What does the Halting Problem show?

A

There are some problems that cannot be solved by a computer.

53
Q

Chapter 49:

What is the Halting Problem?

A 
Does the program halt?
  yes:
    create endless loop
  no:
    halt

(No correct answer)

Computer Science A-Level (12 decks)

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