2018 p1

Question 1

represent 5 - 3 in RPN

Answer 1

5 3 -

Question 2

represent 3 + 4 * 2 - 1 in RPN

Answer 2

3 4 2 * + 1 -

Question 3

why is RPN used instead of infix notation ( e.g. of infix: 5 + 3)

Answer 3

simple for a computer to evaluate
simpler to code algorithm

Question 4

how can a stack be used in the process of evaluating an expression in Reverse polish notation

Answer 4

from LHS push values onto stack
each time operator reached pop two values off the stack and apply operator to them
add result to stack

Question 5

two components of stack frame

Answer 5

local variables
parameters

Question 6

Explain the circumstances in which it would be more
appropriate to use an adjacency list instead of an adjacency matrix.

Answer 6

when there are few edges between vertices
when edges are rarely changed

Question 7

how do you know if a graph isnt a tree

Answer 7

if it contains a cycle

Question 8

weighted graph

Answer 8

a graph where each edge has a weight

Question 9

halting program

Answer 9

Determining if a program will halt

Question 10

Why is it not possible to create a Turing machine that solves the Halting
problem?

Answer 10

there is no algorithm that solves a halting program

Question 11

components of a turing machine

Answer 11

finite set of states
a set of transition rules
halting states
current state

Question 12

universal turing machine

Answer 12

a turing machine that can execute.
it has the ability to read input from a tape, process information based on a given program, and produce output on the same tape.

Question 13

Why can a Universal Turing Machine be considered to be more powerful than any
computer that you can purchase?

Answer 13

It has an infinite amount of memory