Theory of Computation

Question 1

What is an algorithm?

Answer 1

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

Question 2

What are the 4 constructs of algorithms?

Answer 2

1) Iteration
2) Selection
3) Variable assignment
4) Sequence

Question 3

What must we consider when evaluating different algorithms?

Answer 3

Efficiency, how many cases does it work, and error handling

Question 4

What are the 4 main techniques of computational thinking?

Answer 4

1) Abstraction
2) Decomposition
3) Pattern recognition
4) Algorithmic thinking

Question 5

What is abstraction?

Answer 5

Removal of detail from a a problem to focus on what is necessary to solve

Question 6

What is decomposition?

Answer 6

Breaking a problem down into smaller problems, each of which is easier to solve

Question 7

What is pattern recognition?

Answer 7

Comparing a problem to similar problems that are already solved and applying the same or similar solution

Question 8

What is algorithmic thinking?

Answer 8

Writing a solution to a problem using algorithmic constructs (iteration, sequence, assignment, selection)

Question 9

What are the different forms of abstraction?

Answer 9

1) Procedural abstraction
2) Functional abstraction
3) Data abstraction
4) Problem abstraction / reduction

Question 10

What is representational abstraction?

Answer 10

The representation arrived at by removing unnecessary details from the problem.

Question 11

What is an example of representational abstraction?

Answer 11

Maps

Question 12

What is information hiding?

Answer 12

The process of hiding all details of an object that do not contribute to its essential characteristics

Question 13

What is abstraction by generalisation?

Answer 13

Grouping common characteristics to arrive at a hierarchical relationship of the inheritance type

Question 14

What is procedural abstraction?

Answer 14

Abstracting values used in a computation to leave a single computational method (procedure)

Question 15

What is functional abstraction?

Answer 15

Abstracting the method of computation and the resultant function only focuses on inputs and outputs (functions)

Question 16

What is data abstraction?

Answer 16

Isolating how a compound data structure is used from how it is constructed

Question 17

What is problem abstraction (reduction)?

Answer 17

Removal of detail until it is possible to solve because it reduces to one that has already been solved

Question 18

What is decomposition?

Answer 18

The process of breaking down a complex problem into smaller sub-problems. Each sub-problem accomplishes a specific task that is easier to solve. These can be further subdivided until a problem is solvable.

Question 19

What is composition?

Answer 19

Form of abstraction which combines procedures to form compound procedures to solve a complex problem

Question 20

What is automation?

Answer 20

The process of using abstractions of real world phenomena (models) to solve problems

Question 21

How is automation done?

Answer 21

Create algorithms, implement in code, making models in data structures and executing code on data structures

Question 22

What are the components of a finite state machine?

Answer 22

• Finite set of input symbols (alphabet)
• Finite set of states
• Initial state (S_0<\sub>)
• State transition functions
• One or more accepting states

Question 23

What is a finite state machine?

Answer 23

A model to show how a machine changes from one state to another based on external input.

Question 24

How can we represent a finite state machine?

Answer 24

1) State transition diagram
2) State transition table

Question 25

What is the initial state symbol in state transition diagrams?

Answer 25

Question 26

What is the accepting state symbol in state transition diagrams?

Answer 26

Question 27

What is the transition symbol in state transition diagrams?

Answer 27

Question 28

What is transition symbol **with output** in state transition diagrams?

Answer 28

Question 29

What are the columns in a state transition table?

Answer 29

Current state, input, output, next state

Question 30

What are the uses of FSM's?

Answer 30

- digital (hardware) systems - software compilers - syntax parsing - network protocols

Question 31

What does it mean for a finite state machine to be deterministic?

Answer 31

The next state is only dependent on the current state and input and hence **requires no memory**.

Question 32

What do you call a finite state machine that doesn't produce an output?

Answer 32

Finite State Automata

Question 33

Which set is the subset of any set?

Answer 33

The empty set

Question 34

What is a set?

Answer 34

An **unordered** collection of values where each value **occurs at most once**.

Question 35

How to denote set where each element is dependent on certain predicates?

Answer 35

*S = { e | p }* where e is the **expression** and p is the **predicates**

Question 36

How to show AND and OR in set notation?

Answer 36

- ∧ is AND - upside down ∧ for OR

Question 37

What datatype is compact representation used for?

Answer 37

Strings

Question 38

How to show a compact representation of a string with equal numbers of 1s and 0s?

Answer 38

{ 0ⁿ1ⁿ | n >= 1} where n must be a **countable** number

Question 39

What is a finite set?

Answer 39

A set whose elements can be counted off by **natural numbers** (at which point the set stops). The number of items in the set is referred to as its cardinality.

Question 40

What is an infinite set?

Answer 40

A set with an infinite number of items.

Question 41

What is the difference between a countably infinite set and a non-countable infinite set?

Answer 41

A countably infinite set is an infinite set where the items can be counted off by the natural numbers. R is non-countable infinite set.

Question 42

How to do the cartesian product of sets?

Answer 42

A x B is the set of all ordered pairs (a,b) where a is an element of A and b is an element of B.

Question 43

What is a subset?

Answer 43

A subset (X) of the set S is a set whose values are all members of S. denoted as X ⊆ S

Question 44

What is a proper subset?

Answer 44

A subset that does not contain **all** of the elements of the original set. denoted as X ⊂ S

Question 45

What are the different operations that you can do on sets and what do they do?

Answer 45

- Union - ∪ - all elements in either set or both - Intersection - ∩ - elements shared by both sets - Difference - / - A/B is all the elements in A but not in B (also written as A-B)

Question 46

What is a tractable problem?

Answer 46

If a problem can be solved in polynomial time, it is described as **tractable**.

Question 47

What are heuristics?

Answer 47

A heuristic approach employs a method of finding a solution that might not be the best. (reducing problem space or changing constraints)