4.3 (every spec covered)

Question 1

What are the features of a breadth first graph traversal? (3)

Answer 1

explores graph level by level

uses a queue data structure

best for finding the shortest path in an unweighted graph

Question 2

how does a breadth first search logically work (4)

Answer 2

Uses a queue to keep track of nodes to visit
Uses a visited set to avoid resvisiting nodes

start at first node, enqueue and mark as visited

dequeue A, Enqueues A’s unvisited neighbours

Repeat

Question 3

What are the features of a depth first graph traversal?

Answer 3

Explores as deep along each possible branch before backtracking

uses a stack

applications include maze, puzzle solving and path finding

Question 4

How does a depth first search logically work

Answer 4

need a stack and a visited set of nodes

step by step:

start at node 1, push 1 onto stack

pop 1, mark 1 visited, push neighbours onto stack

pop neighbour at the top of stack push unvisited neighbours of that stack

repeat until there are no unvisited neighbours

Question 5

pre order tree traversal order

Answer 5

Node, Left, Right -

Question 6

post order tree traversal

Answer 6

Left, Right, Node -

Question 7

in order tree traversal and when its used (1)

Answer 7

Left, Node, Right -
Used in binary search trees

Question 8

What is Meant by O(N)

Answer 8

O represents the order of complexity

N represents the number of inputs

Question 9

What are the factors of complexity used in big o notation

Answer 9

Memory used, time clompexity

Question 10

Time complexity of linear search

Answer 10

O(n)

Question 11

Time complexity of Binary/Binary tree search

Answer 11

O(log n).

Question 12

Time complexity of Bubble sort

Answer 12

O(n^2).

Question 13

Time complexity of Merge sort

Answer 13

O(n log n).

Question 14

What is djikstras algorithim?

Answer 14

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

It is considered a type of breadth first algorithim

Question 15

What does it mean when algorithims are tractable?

Answer 15

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

Question 16

What is it when an algorithim is intractable?

Answer 16

These are problems that have solutions in greater than polynomial time

Question 17

What methods are used when tackling intractable problems

Answer 17

Heuristic methods

Question 18

How do we trace a graph depth first

Answer 18

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

Question 19

How do we trace a graph breadth-first

Answer 19

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

Question 20

What are heuristic methods

give 2 examples

Answer 20

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

For example trial and error, pattern recognition

Question 21

Describe the traversing of a graph breadth first using a queue

Answer 21

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

Question 22

Describe the traversing of a graph depth frist using a stack

Answer 22

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

Question 23

what does a depth first graph traversal give us

Answer 23

Suitable solutions for game or puzzle problems

Question 24

what does an inorder traversal tell us

Question 25

what does an preorder traversal tell us

Answer 25

used to copy a binary tree return prefix expressions in RPN

Question 26

what does an postorder traversal tell us

Answer 26

used to delete a binary tree outputting postfix expressions

Question 27

What is meant by infix notation

Answer 27

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

Question 28

What is the problem with infix notation

Answer 28

It can be ambiguous without brackets.

Question 29

What is reverse polish notation

Answer 29

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

Question 30

What are the three main reasons why RPN if so useful

Answer 30

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

Question 31

How do we convert a infix expression into RPN

Answer 31

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

Question 32

How can we evaluate a RPN using a stack

Answer 32

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

Question 33

What is a linear search algorithm

Answer 33

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

Question 34

What are the advantages and drawbacks of the linear search algorithm

Answer 34

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

Question 35

What is a application of the linear search

Answer 35

find and replace function in a word processor

Question 36

What is the time complexity of linear search algorithim

Answer 36

O(n)

Question 37

What is a binary search algorithim

Answer 37

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

Question 38

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

Answer 38

The list must be sorted

Question 39

Describe how a binary search works

Answer 39

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

Question 40

What is the time complexity of a binary search

Answer 40

O(log n)

Question 41

What is a bubble sort algorithim (3)

Answer 41

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.

Question 42

why is the time complexity of the bubble sort O(n^2)

Answer 42

it uses two nested loops which could each iterate up to n times

Question 43

What is the time complexity of the bubble sort

Answer 43

O(n^2)

Question 44

What is the space complexity of the bubble sort

Answer 44

O(1)

Question 45

What is the space complexity of the binary search

Answer 45

O(1)

Question 46

What is the merge sort algorithim

Answer 46

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

Question 47

What are the applications of the merge sort

Answer 47

Works best with large data sets Ideal for parallel processing environments which are computing systems that perform multiple calculations or processes simultaneously

Question 48

What is the time complexity of a merge sort

Answer 48

O(n log n)

Question 49

why is the time complexity of a merge sort O( n log n)

Answer 49

n is the number of elements in the list log n comes from the number of recursive calls n is from the merging of the n lists

Question 50

What is the space complexity of a merge sort

Answer 50

O(n)

Question 51

What are the applications of Djikstras shortest path algorithim

Answer 51

chip design finding routes from one place to another web crawlers

Question 52

Describe the operation of djikstras shortest path algorithm

Answer 52

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

Question 53

what is the time complexity of djikstras shortest path algorithm and why is it that. (2)

Answer 53

O(v^2) This is because for each vertex, finding the minimum distance node takes O(V) time.

Question 54

What are some applications of djikstras algorithim

Answer 54

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

Question 55

What is an algorithim

Answer 55

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

Question 56

What is pseudocode

Answer 56

A text based way of representing steps in an algorithm

Question 57

what is a binary search tree

Answer 57

A binary tree that maintains a specific order among its elements

Question 58

what is a binary search tree characterized by: (4)

Answer 58

each node has at most two children left child node contains values less than the parent node right child node contains values greater than the parent node rule is applied to all nodes in the tree

Question 59

describe what is meant by the binary tree search algorithm

Answer 59

Find out if a specific value exists in a binary search tree