Brainscape's Knowledge GenomeTM

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


See full index

Computer Science AS level OCR > 2.3 > Flashcards

2.3 Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

big O notation classifications

A

Classifications of big O notation, ranging from fast efficient algorithms that remain constant despise their input size to the bad ones to be avoided.
- Can help you select the most appropriate one to use and optimise your code.

O(1) Constant
Will always take the same amount of memory (in addition to the list itself).

O(n)Linear
Best time grows at the same rate as the number of elements
This is the case when the data is already in order

O(n2) Polynomial / Quadratic
Worst and average time is proportional to the square (polynomial) of the number of elements
Worst case is when the data is initially in the reverse order

Logarithmic complexity: impact of an algorithm directly proportional to the logarithmic result of the input size (e.g., binary search)

Exponential complexity: the time it take to execute will double with each additional item in the input.

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

stack

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

stack operations

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

stack words

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

stack push

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

stack pop

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

stack peek

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

stack and queue efficenies

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

queues

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

queue operations

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

enqueueing and dequeuing item from queue

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

enqueue code

A

function enqueue(newJob)
if queueTail == 99 then
return -1
else
queueTail = queueTail + 1
buffer[queueTail] = newJob
return 1
endif
endfunction

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

dequeue code

A

function dequeue()
if queueHead > queueTail then
return null
else
queueHead = queueHead + 1
return buffer[queueHead-1]
endif
endfunction

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

difference between stack and queue

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

how Dijkstra’s algorithm would find the shortest path

A

 Mark A as the initial node and then visit B (5)
 Node E (8) is then visited (chosen from C (13), D (14), E (8))
 Node I (12) is then visited after E
 Node J (14) is then visited after I
 Visiting G (18) from I;
 Visiting G (15) from C – overriding the previous value of 18
 solution A-B-E-I-J path length 14

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

Compare the performance of Dijkstra’s algorithm and the A* search algorithm,

A

Heuristic helps produce a solution in a faster time
 A* uses estimated distance from final node
 Dijkstra uses a weight/distance
 A* chooses which path to take next based on lowest
current distance travelled

AO2: Application
 Description of how A* will differ from Dijkstra, e.g.
taking the shorter route A-B-E-I before exploring
nodes from D and E
 Description of the different number of comparisons
that would be needed in this problem
 A* doesn’t need to find all possible solutions (saves
time)

AO3: Evaluation
Candidates will need to evaluate the benefits and
drawbacks of each algorithm
 Small-scale problem
 Quick to find a solution using either method
 Difference in programming complexity is minimal
 Don’t know if this problem needs to scale
 Most efficient route needed

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

array

A

An array is a static collection of items of the same data type called elements. An array is typically used when the required number of data items is known in advance, to store data that would otherwise be stored in multiple variables.

Limitations of using arrays:
1. All data elements in an array must be of the same data type. For example, an array of strings cannot contain an integer.
2. The size of an array is determined when it is declared – i.e., when the algorithm is written – and cannot usually be changed when the program is running.

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

Assigning data to array

A

Assigning data to the array can be carried out using syntax similar to:

name[0] = “Craig”
name[1] = “Dave”
name[2] = “Sam”
name[3] = “Carol”

Possible to use an iteration to output all the data in the array:

For index = 0 to 3
Print(name[index])
Next

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

operations of an array

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

binary tree

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

tree operations

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

multi branch tree

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

difference between graph, binary tree, tree

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

linked list

A

data structure that provides a foundation upon which other structures can be built, e.g. stacks, queues, graphs, trees. constricted from nodes and pointers and a start pointer identifies the first node. each node contains data and a pointer to the next node.
data in lists can be stored anywhere in memory, with pointers indicating the address of the next item.

doubly linked lists have extra pointers, where nodes can point to previous/next items.
circular linked lists can be created by making the last node point to the first.
doubly circular linked lists is when each node in a circular linked list can also have an additional pointer pointing to the previous item.

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

why and how trees are traversed

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

depth-first (post-order) traversal

A
27
Q

depth-first (post-order) traversal code

A
28
Q

breadth-first traversal

A
29
Q

breadth-first traversal code

A
30
Q

stages of binary search

A

works on ordered set of data
Repeat
 Calculating an array midpoint…
 …by adding the array lower bound to the array upper bound, dividing by 2 and rounding
 Compare array midpoint with value to search for…
 …if equal set found flag to true
 …if array midpoint < value to search for, change lowerbound to equal midpoint + 1
 …if array midpoint > value to search for, change upperbound to equal midpoint – 1
 Until lowerbound is greater than or equal to upperbound
 Return/output found flag

31
Q

binary search code

A
32
Q

linear search

A

.Start at the first item in the list.
2.If the item in the list is the one to be found, the search is complete.
3.If it is not, move to the next item.
4.Repeat from step 2 until the item is found or there are no more items in the list.
5.If the item has been found, output its data. If it has not, output “Not found”.

33
Q

linear search code

A
34
Q

bubble sort

A

In bubble sort all adjacent items are compared against each other.
The biggest number in the adjacent pair is swapped over with the smallest number and when a swap is made a flag is set.
A temp variable is used to hold the data while it’s being moved. This is repeated for all adjacent values, known as one pass.
At the end of one pass, the largest item should appear at the end of the list.
If at the end of the list the flag has been set the flag is unset and the algorithm starts from the beginning of the list again.
When the algorithm gets to the end of the list and the flag is unset the list is sorted the inner loop will compare l the adjacent items in a single pass the outer loop will repeat the process of checking adjacent items until all passes are completed

35
Q

bubble sort code

A
36
Q

how insertion sort works

A
37
Q

insertion sort code

A
38
Q

merge sort

A
39
Q

merge sort code

A
40
Q

quicksort

A
  • Choose a pivot // identify start and end pointers
  • Compare each element to the pivot… // compare start and end pointers
  • Put items < pivot in the left sublist
  • Put items > pivot in the right sublist
  • Choose a pivot in each sublist
  • If start pointer is larger than end pointer…
  • …then swap data items around
  • And repeat the process until each item becomes a pivot

decomposing data sets into smaller subsets
* and then sorting each split subset
* until each subset is sorted
* and then combining the subsets to provide a solution

41
Q

quicksort code

A
42
Q

implementations of linked list

A

can be implemented using a static array, being static data structures, arrays are stored contiguously in memory, requiring the use of index register to determine where a specific index is in relation to a base address. in a linked list the items would be stored alphabetically because of their pointers.

OOP- any available memory address can be used to store data, does not need to be adjacent as each node points to the next in the structure.

43
Q

applications of linked list

A

operating systems managing a processor to store process blocks in ready state.
image viewers to switch between previous and next images.
music players to store tracks in a playlist.
web browsers to navigate forwards/backwards.

44
Q

operations of a linked list

A
45
Q

adding an item to a linked list

A
46
Q

deleting an item from a linked list

A
47
Q

traversing a linked list

A
48
Q

analysing an algorithm

A

Goal is that algorithm should always:
- Run as quickly as possible (time complexity)
- Take up the least amount of memory possible space complexity)

When considering algorithms complexity you should think about time to execute and amount of memory it uses.

49
Q

classification symbols

A
50
Q

labelling classifications

A
51
Q

comparison- linear search

A
52
Q

comparison- binary search

A
53
Q

comparison- bubble sort

A
54
Q

comparing searching algorithms

A
55
Q

comparing sorting algorithms

A
56
Q

enqueue

A

Check if the queue is full … if the firstElement pointer (+1) = lastElement … if it is return False
* Adds element at lastElement (+1) position … increments lastElement pointer
* If lastElement is greater than last Index …reset to 0

57
Q

delete node from tree

A

find node to delete- search the tree to find the location of Node
* Replace the content of the node with null
* Make node before point to the next node
* Add node E to the empty node list

58
Q

add node to tree

A

check for dree memory output error if not
Search the tree to find the location of previous node
* Create a new node with value K
* Add a pointer from node before to the new node
* Make new node point to null

59
Q

similarities and diff of graph and tree

A

Both consists of nodes
* Both are connected by edges/links
* Both are non-linear data structures
* Both are dynamic data structures
1 mark per difference to max 2
* Tree is 1-directional whereas a graph is 2-directional
* Tree has a root node whereas a graph does not have a (clear) root node
* Tree will not have cycles whereas graphs can contain cycles
* Tree will not be weighted whereas edges in a graph can be weighted

60
Q

finding node in linked list

A

Initialise message string
* Start with the headPointer
* Check if the headPointer is null …return that the list is empty
* Check the pointer of the node at headPointer
* If it is not null
* loop through all the linkedList elements
* …concatenate the pointer to the message
* …replacing the pointer with the current node’s pointer each time
* …if the data is found concatenate the pointer and “found” to the message
and return it
* …if the loop ends and the data item is not found, concatenate “not found” to
the message and return it

61
Q

linked list adv

A
  • …items can be added at different points in the linked list depending on priority
  • …by changing the pointers to items needing priority
  • Have different queues for different priorities
  • …add the job to the queue relevant to its priority
  • …print all the jobs in the highest priority queue firs
62
Q

deleting item from linked list

A

Traverse the list to the item immediately prior to the item to be
removed (1)
 … which is DataItem 1 - Daisy
 Find the value of the NextPointer of the item to be removed
 … which is the NextPointer of DataItem 2 - Hosta, value 7
 Set the nextPointer of the item prior to the item to be removed to
the NextPointer value of the DataItem to be removed
 … update the NextPointer of DataItem 1 - Daisy from 2 to 7
(Lavender)

63
Q

outputing contents of linked list

A

currentElement = firstElement
while(currentElement != null) print(plantList[currentElement,0])
currentElement = plantList[currentElement,1]
endwhile

64
Q

difference between array, list and object

A

Computer Science AS level OCR (20 decks)

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