Brainscape's Knowledge GenomeTM

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


See full index

Computer Science Paper 1 > 4.3 Fundamentals of Algorithims > Flashcards

4.3 Fundamentals of Algorithims Flashcards

1
Q

What are the 2 features of a breadth first graph traversal?

A

Shortest path for an unweighted graph
uses a queue

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

What are the 2 features of a depth first graph traversal?

A

Navigating a maze
uses a stack

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

pre order tree traversal order

A

Node, Left, Right -

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

post order tree traversal

A

Left, Right, Node -

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

in order tree traversal and when its used (1)

A

Left, Node, Right -
Used in binary search trees

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

What is Meant by O(N)

A

O represents the order of complexity

N represents the number of inputs

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

What are the factors of complexity used in big o notation

A

Memory used, time clompexity

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

Time complexity of linear search

A

O(n)

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

Time complexity of Binary/Binary tree search

A

O(log n).

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

Time complexity of Bubble sort

A

O(n^2).

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

Time complexity of Merge sort

A

O(n log n).

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

What is djikstras algorithim?

A

Finds the shortest path between one node and all other nodes on a weighted graph.

It is considered a type of breadth first algorithim

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

What does it mean when algorithims are tractable?

A

These are problems that have a polynomial (or less) time solution (x^2)

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

What is it when an algorithim is intractable?

A

These are problems that have solutions in greater than polynomial time

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

What methods are used when tackling intractable problems

A

Heuristic methods

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

How do we trace a graph depth first

A

Start at a root and follow one branch as far as it will go. (using stack)

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

How do we trace a graph breadth-first

A

start at root scan every node connected and then continue scanning from left to right (using queue)

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

What are heuristic methods

give 2 examples

A

practical approaches used when finding an optimal solution is impractical or impossible due to time constraints

For example trial and error, pattern recognition

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

Describe the traversing of a graph breadth first using a queue

A

Set the root node as current node
Add current node to list of visited nodes
For every edge connected to that node enqueue the linked node

Then dequeue the current node and move front pointer up by one and repeat steps with the new current node

output all visited nodes

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

Describe the traversing of a graph depth frist using a stack

A

Visited nodes are pushed onto the stack, when there are no nodes left to visit the nodes are popped off the stack.

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

what does a depth first graph traversal give us

A

Suitable solutions for game or puzzle problems

22
Q

what does an inorder traversal tell us

A
23
Q

what does an preorder traversal tell us

A

used to copy a binary tree
return prefix expressions in RPN

24
Q

what does an postorder traversal tell us

A

used to delete a binary tree
outputting postfix expressions

25
Q

What is meant by infix notation

A

Standard notation for where the operator is fixed between the operands : A + B

26
Q

What is the problem with infix notation

A

It can be ambiguous without brackets.

27
Q

What is reverse polish notation

A

An alternative to infix notation without ambiguity, where the operator comes after the two operands (postfix)

28
Q

What are the three main reasons why RPN if so useful

A

Eliminates the need for brackets in sub-expressions
Expressions are suitable for evaluation using a stack
Can be used in interpreters based on a stack

29
Q

How do we convert a infix expression into RPN

A

Store in a binary tree, take the first number and put it as a node when you come across a operator move up the tree and make it a central node, repeat

Then By using a post order traversal, left right node

30
Q

How can we evaluate a RPN using a stack

A

When you hit an operand push it onto the stack, when you hit an operator pop the last two items off the stack perform the calculation and push the result back onto the stack

31
Q

What is a linear search algorithm

A

Linear search finds an item in a sorted or unsorted list by checking each item one by one

32
Q

What are the advantages and drawbacks of the linear search algorithm

A

Doesn’t require the data set to be in order
Can be efficient for smaller data sets
easy to implement

Is inefficient for large data sets

33
Q

What is a application of the linear search

A

find and replace function in a word processor

34
Q

What is the time complexity of linear search algorithim

A

O(n)

35
Q

What is a binary search algorithim

A

An efficient algorithm for finding an item in a sorted data list

36
Q

What does a binary search require from a list in order to work

A

The list must be sorted

37
Q

Describe how a binary search works

A

Midpoint of list is found, by performing integer division on the first and last index values added together

Checks if midpoint is value we are looking for, if not then it checks if the value that it is looking for is larger or smaller

In either case it halves the size of the data set and move to the midpoint of the top or lower half of the data set.

Process is repeated until value is found or search range is empty

38
Q

What is the time complexity of a binary search

A

O(log n)

39
Q

What is a bubble sort algorithim

A

A bubble sort orders an unordered list of items by comparing each item with the next on and swapping the items if they are out of order

The algorithim is complete when there are no more swaps to be made

In effect it bubbles the largest value to the end of the list hence the name.

40
Q

What is the time complexity of the bubble sort

A

O(n^2)

41
Q

What is the space complexity of the bubble sort

A

O(1)

42
Q

What is the space complexity of the binary search

A

O(1)

43
Q

What is the merge sort algorithim

A

A sorting algorithm which is very fast that carries out the following operation:

Data set is repeatedly split in half until each item is in its own list

Adjacent list sare then merged back together with each item being compared and sorted in the new combined list

This process is repeated until new list is reconstructed

44
Q

What are the applications of the merge sort

A

Works best with large data sets

Ideal for parallel processing environments which are computing systems that perform multiple calculations or processes simultaneously

45
Q

What is the time complexity of a merge sort

A

O(n log n)

46
Q

What is the space complexity of a merge sort

A

O(n)

47
Q

What are the applications of Djikstras shortest path algorithim

A

chip design
finding routes from one place to another
web crawlers

48
Q

Describe the operation of djikstras shortest path algorithm

A

Start with the source node and set its distance to 0, all others to ∞.
Pick the closest unvisited node and update its neighbors’ distances if a shorter path is found.
Mark the node as visited (processed).
Repeat until all nodes are processed.
At the end, you have the shortest path distances from the source to every node

49
Q

What are some applications of djikstras algorithim

A

Geographical maps application, towns = nodes, distances = edge weights

50
Q

What is an algorithim

A

A specific sequence of stems that can be followed to complete a task that always terminates.

51
Q

What is pseudocode

A

A text based way of representing steps in an algorithm

Computer Science Paper 1 (6 decks)

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