Font size
WorksheetsThe Limits of Computing
Total questions: 20
Worksheet time: 10mins
A problem that cannot be solved within a reasonable amount of time
Intractable
Tractable
Tractable problems can be solved within a reasonable amount of time
True
False
A heuristic approach will find the optimal solution
True
False
Which concept is used to show whether a problem is computable or not?
A*
Heuristics
Halting
Intractable
It is possible to create an algorithm to solve the Halting Problem
True
False
What is meant when we say a program has halted?
Run to completion
Crashed
Broken
Which of the following time complexities can be classed as intractable?
O (n)
O (n2)
O (2n)
O (n!)
Select all time complexities that would be classed as tractable
Constant
Logarithmic
Factorial
Polynomial
Exponential
Identify the correct description for a problem with complexity of O (n3)
Tractable
Intractable
Non-Computable
Some problems are and always will be non-computable
True
False
Select the string that is NOT matched by the regular expression:
ab?c*d
abcbcbcbcd
acd
ad
acccd
Which regular expression matches the FSM?
ab|cb+
(a|b)+cb*
(a|cb+)+
a?c|b*
Symbol used to represent zero or one of the preceding tokens
?
*
^
+
Which symbol Indicates that there are zero or one of the preceding element i.e. optional character
|
*
+
?
()
In this FSM how many inputs are there?
4
2
1
3
In this FSM which is the Accept State
S1
S2
0
1
When the state is S2 if the input is 0
The machine will remain in the state S2
The machine will malfunction
0 is not a valid input
The machine will change state to S1
Starting at state S1 what state would input 'acd' change to
S1
S3
S4
S2
What state will the machine rest in with an input of 'aabacda'
S4
S3
S2
S1
Final Question, what is the minimum accepted input of this Finite State Machine
acdb
abc
ac
ad
