Brainscape's Knowledge GenomeTM

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


See full index

A Level Computer Studies > Unit 8 > Flashcards

Unit 8 Flashcards

1
Q

What are the three characteristics of a recursive routine?

A
  1. A stopping condition or base case must be included
  2. The routine must call itself for all values other than the base case
  3. The stopping condition must be reached after a finite number of calls
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
1
Q

T/F: The stopping condition and the base case are the same thing

A

True

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

Define base case

A

A value that stops a recursive routine from calling itself again and causes the call stack to ‘unwind’

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

How is stack overflow linked to recursive routines?

A

Recursive routines require a lot of memory space and when the call stack exceeds the designated memory space the program will crash

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

Define stack overflow

A

When the memory required for the call stack has exceeded that designated to the sub program

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

Give an example of where recursive routines are used and why

A

They can be used in tree traversal as they perform the traversal of either the right or left side of the tree multiple times

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

What is Big O notation a measure of?

A

Time complexity

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

Define Big O notation

A

A method used by computer scientists to describe the time complexity of an algorithm

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

What are the 5 time complexities we need to know (in order from least to most complex)?

A
  1. Constant time
  2. Logarithmic time
  3. Linear time
  4. Polynomial time
  5. Exponential time
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What type of statement do we use to work out the time complexity of an algorithm?

A

Assignment statements

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

How do we simplify the time complexity of an algorithm from multiple terms to just one?

A

We focus on the most significant term only

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

What is the time complexity of a binary tree search?

A

Logarithmic

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

What is the time complexity of a bubble sort?

A

O(n ** 2)

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

What is the time complexity of a linear search?

A

Linear

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

Define permutation

A

The number of ways to arrange a set of items

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

What are the two types of permutation?

A

With repetition and with no repetition

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

What is the difference between the two types of permutation?

A

Permutations with repetition are were there are the same number of options for each choice (.e.g. numbers on a padlock) where as the number of option reduces with each choice in non repetition permutations (.e.g. removing balls from a bag)

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

What is the time complexity of permutations with repetition?

A

O(x ^ n) where x represents the number of options and n represents the number of choices

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

What is the time complexity of traversing a balanced binary tree?

A

O(log(n))

19
Q

What is the worst case scenario for the time complexity of an unbalanced tree?

A

O(n)

20
Q

What is the time complexity of a merge sort?

A

O(n log(n)), with a base of 2

21
Q

What are the two methods of graph traversal?

A

Depth first and breadth first

22
Q

Describe depth first graph traversal

A

You go as far down the route of one neighbour of the current vertex until you can’t go any further and have to back track

23
Q

Describe breadth first traversal

A

Exploring all of the neighbours of the current vertex and then the neighbours of each of thsoe vertices in turn

24
Q

What ADTs does depth first traversal use and why?

A

It uses a list to keep track of nodes visited and a stack to keep track of the last node visited, this is so that the previously visited nodes can be popped from the stack in order to revisited when backtracking

25
Q

If a node has multiple neighbours how do we decide which one to traverse first?

A

Based on the position in the dictionary

26
Q

What ADTs does breadth first traversal use and why?

A

It uses a list to keep track of the nods already visited and uses a queue rather than a stack to store the order of the recently visited nodes, this is because the first item in the queue will be the neighbour that has to be traversed next

27
Q

What is the time complexity of DFS and BFS in a sparse graph?

A

O(n)

28
Q

What is the time complexity of DFS and BFS in complex graphs?

A

O(n**2)

29
Q

Which is more time efficient, DFS or BFS?

A

They are both the same!

30
Q

What does Dijkstra’s shortest path algorithm do?

A

It is designed to find the shortest path between two nodes in a weighted graph

31
Q

Describe how Dijkstra’s shortest path algorithm works

A
  1. The start node is assigned a temporary value of 0 and all other nodes are assigned a temporary value of infinity
  2. The start node is removed from the queue and each of its neighbours are visited
  3. The temporary distances of the start node’s neighbours are updated based on the weight of the edge used to get between the two nodes
  4. The process of visiting neighbouring nodes is then repeated with the first item in the priority queue until the queue is empty
  5. The shortest path can then be worked out by tracing the algorithm back
32
Q

What ADT does Dijkstra’s shortest path algorithm use?

A

A priority queue

33
Q

What is a heuristic?

A

A solution that is not perfect but will suit the situation it’s required for

34
Q

Define a computable problem

A

A problem that has a corresponding algorithm that can solve every instance of it in a finite number of steps

35
Q

Define soluble

A

A computable problem

36
Q

Define insoluble

A

An incomputable problem

37
Q

Define tractable

A

A problem that has a solution with a polynomial time complexity or better

38
Q

Define intractable

A

A problem that has no solution with a polynomial time complexity or better

39
Q

Why are some problems in theory soluble but in practice insoluble?

A

This is because they may take an excessive amount of time to solve that far exceeds the lifespan of one person

40
Q

What are the two major limitations of computers?

A

Algorithm complexity and hardware availability

41
Q

What is the travelling salesman problem?

A

TSP is a classic intractable problem where it is theoretically possible to work out the most efficient way of visiting the nodes but the brute force process to do this has a factorial time complexity which means it is practically insoluble

42
Q

Define heuristic approach

A

An approach that attempts to find a solution that is not perfect but adequate for the situation

43
Q

How came up with the Halting Problem?

A

Alan Turing

44
Q

What is the Halting Problem?

A

This is a thought problem that proves that it is impossible for a machine (H) to determine whether a program (P) will always stop running or continue running forever for any given input

45
Q

Why is the machine H in the Halting Problem impossible?

A

It is impossible to tell whether program (P) would halt for input (I) because the Machine (H) would have to run the code infinitely

46
Q

Why was the Halting Problem significant?

A

It was proved that there are some problems which just can’t be solved by computers

A Level Computer Studies (16 decks)

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