2.3 - Algorithms (Unfinished)

Question 1

What is an Algorithm?

Answer 1

A set of instructions that complete a task when executed

Question 2

Stack PUSH Algorithm

Answer 2

PROCEDURE AddToStack (item):
IF top == max THEN
stackFull = True
ELSE
top = top + 1
stack[top] = item
ENDIF
ENDPROCEDURE

Question 3

Stack POP Algorithm

Answer 3

PROCEDURE DeleteFromStack (item):
IF top == min THEN
stackEmpty = True
ELSE
stack[top] = item
top = top - 1
ENDIF
ENDPROCEDURE

Question 4

Queue PUSH Algorithm

Answer 4

PROCEDURE AddToQueue (item):
IF ((front - rear) + 1) == max THEN
queueFull = True
ELSE
rear = rear - 1
queue[rear] = item
ENDIF
ENDPROCEDURE

Question 5

Queue POP Algorithm

Answer 5

PROCEDURE DeleteFromQueue (item):
IF front == min THEN
queueEmpty = True
ELSE
queue[front] = item
front = front + 1
ENDIF
ENDPROCEDURE

Question 6

What is this code for?

FUNCTION ______(graph, node, visited):
markAllVertices (notVisited)
createStack()
start = currentNode
markAsVisited(start)
pushIntoStack(start)
WHILE StackIsEmpty() == false
popFromStack(currentNode)
WHILE allNodesVisited() == false
markAsVisited(currentNode)
//following sub-routine pushes all nodes connected to
//currentNode AND that are unvisited
pushUnvisitedAdjacents()
ENDWHILE
ENDWHILE
ENDFUNCTION

Answer 6

Depth-First Graph Traversal

Question 7

What is this code for?

FUNCTION bfs(graph, node):
markAllVertices (notVisited)
createQueue()
start = currentNode
markAsVisited(start)
pushIntoQueue(start)
WHILE QueueIsEmpty() == false
popFromQueue(currentNode)
WHILE allNodesVisited() == false
markAsVisited(currentNode)
//following sub-routine pushes all nodes connected to
//currentNode AND that are unvisited
pushUnvisitedAdjacents()
ENDWHILE
ENDWHILE
ENDFUNCTION

Answer 7

Breadth-First Graph Traversal

Question 8

Algorithm to Output a Linked List

Answer 8

FUNCTION OutputLinkedListInOrder ():
Pointer = start value
REPEAT
Go to node(Pointer value)
OUTPUT data at node
Pointer = value of next item Pointer at node
UNTIL Pointer = 0
ENDFUNCTION

Question 9

Depth-First Graph Traversal

Answer 9

FUNCTION ______(graph, node, visited):
markAllVertices (notVisited)
createStack()
start = currentNode
markAsVisited(start)
pushIntoStack(start)
WHILE StackIsEmpty() == false
popFromStack(currentNode)
WHILE allNodesVisited() == false
markAsVisited(currentNode)
//following sub-routine pushes all nodes connected to
//currentNode AND that are unvisited
pushUnvisitedAdjacents()
ENDWHILE
ENDWHILE
ENDFUNCTION

Question 10

Binary Search Algorithm

Answer 10

FUNCTION BinarySearch (A[0..N-1], value, low, high)

 if high < low THEN
      return error_message
 endif

 mid = (low + high) / 2

 if A[mid] > value THEN
      return BinarySearch(A, value, low, mid-1)
 elseif A[mid] < value THEN
       return BinarySearch(A, value, mid +1, high)

 else
      return mid
 endif

endfunction

Question 11

What is the purpose of Big O notation?

Answer 11

To:

Evaluate the complexity of the algorithm

Show how the time / memory / resources increase as the data size increases

Evaluate worst case scenario for the algorithm

Question 12

What are the different types of Big O Notation, in ascending order of length? (Both Names)

Answer 12

Constant O(1)
Logarithmic O(LogN)
Linear O(N)
Polynomial O(n^2)
Exponential O(2^n)