Worksheets7517 04 Section Assessment
Total questions: 60
Worksheet time: 3600secs
Which of the following is not an example of abstraction?
Identifying essential details
Disregarding non-essential information
Breaking the problem down into smaller tasks
Which of the following is not a feature of decomposition?
Looking into a system in terms of procedures or subroutines
Disregarding non-essential information
Breaking a problem down into smaller tasks
In abstraction by categorisation, aspects of a problem are placed in broader categories to create a hierarchical representation
True
False
Abstraction and Decomposition are examples of...
Computational Thinking
Algorithmic Thinking
Computer Science
Logical Reasoning
Why do we decompose a complex problem?
To make it easier to solve
To make its solution more cyclical
To change the problem we have
What is automation?
Modelling of real-world problems
Breaking a problem down in to smaller chunks
removing unnecessary detail
Information hiding
what is composition?
Linking procedures to form a compound procedure
Breaking a problem down in to smaller chunks
Modelling of real-world problems
Information hiding
What is an algorithm?
A sequence of instructions on how to solve a problem.
The breaking down of a problem into smaller parts.
Focusing on important parts and ignoring the irrelevant details
The easiest route through a coding problem
In this finite state machine how many states are there
1
2
3
4
What do the arrows represent
States
Transformations
Inputs
Transitions
In this FSM how many inputs are there?
4
2
1
3
In this FSM which is the Accepting State
S1
S2
0
1
When in State S2, if the input is 1...
The machine will remain in state S2
The machine will change state to S1
The Machine will return to the Start State
The machine will return the value of 0
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
Starting at state S1, an input of 'ab' would result in state
S1
S2
S3
S4
For a Turing machine, the initial state is called a Start State, and a state that has no outgoing transitions is called a Halting State
True
False
The set of symbols used for a Turing Machine is called an
Alphabet
Symbols Collection
Dictionary
Functional Set
Which of these explains a Turing machine ?
Demonstrates the ability of humans to build computers
Provides a definition of what is computable
Used to prove that there are problems which cannot be solved by computers
Allows for the completion of complex mathematical calculations
A "intractable" problem is one which...
can theoretically be solved, but not within polynomial time
cannot theoretically be solved, unless within polynomial time
What would this notation mean?
δ (S1, A) = (S1, B, →)
IF in state 1, and read an "A" Stay in state 1, Write a B and move right
IF in state 1, and read an "B" Stay in state 1, Write an A and move right
IF in state 1, and read an "A" Change to state 2, Write a B and move right
IF in state 1, and read an "B" Change to state 2, Write an A and move left
Which of the following operation can be applied on regular expressions?
Union
Intersection
Difference
All of these
The set of all strings over ∑ = {0,1} in which all strings that begin and end with 0 is
0(0+1)0
00
00(0+1)0
All of these
The set of all strings over ∑ = {a,b} in which all strings having bbbb as substring is
(a+b)* bbbb (a+b)*
(a+b)* bb (a+b)*bb
bbbb (a+b)*
bb (a+b)*
The set of all strings over ∑ ={a,b} in which single a is followed by any number of b’s, or single b followed by any number of a’s is:
ab* + ba*
ab*ba*
a*b + b*a
None
The set of all strings over ∑ = {a,b} in which all strings of a’s and b’s ending in bb is
ab
a*bbb
(a+b)* bb
All of these
Which of the following statements is true?
Every language that is defined by regular expressions can also be defined by Finite state Machines
Every language defined by Finite State Machines can also be defined by regular expressions
We can convert regular expressions into Finite State Machines
All of these
Which of the following BNF rules uses recursion?
<Number> ::= <Digit> | <Digit><Number>
<Name> ::= <Forename><Surname>
<Age> ::= <Digit>|<Digit><Digit>
<Name> ::= <Name>
Select the 2 strings that are matched by the regular expression:
a(bc)*d
abcbcbcbcd
acd
ad
acccd
Select the 2 strings that are matched by the regular expression:
a(b|c)?d
abcbcbcbcd
acd
ad
acccd
Regular expressions are used to...
match patterns in text
draw FSMs
define programming language
correct spellings
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
?
*
^
+
What is the correct syntax for a line of Python code which imports the re module?
Import re
import RE
import re
Import RE
If A = {1,2,3}, B = {3,4,5}, C = {5,6,7}, find A U B U C.
{1,2,3,4,5,6,7}
{1,2,3,4,5,6,7,8}
{1,2,3,3,4,5,5,6,7}
{3,4,5}
List the elements of A
{2,3}
{2,3,5,9}
{1,2,3,4,5}
{5,9}
List the elements of A Ո B
{5,9}
{2,3,7,6,8}
{2,3,5,9,7,6,8}
{1,4}
List the elements of B
{4,5,6,7,8,9,10,11}
{4,6,7,8}
{9,5,10,11}
{4,5,6,7,8,9,10}
List the elements of A △ B'
{2,3}
{5,9}
{2,3,6,7,8}
{1,2,3,4,5,6,7,8}
The Venn diagram for A∪B is represented in green as
Which of the following operations on sets describe the given Venn Diagram?
(A ∩ B)′
(A−B)′
(A∪ B)′
A′ ∪ B
Which of the following operations on sets describe the given Venn diagram?
B − A
A′ − B′
B′ − A′
Indicate constant time complexity in terms of Big-O notation
O(N)
O(1)
O(log N)
O (N^2)
Indicate exponential time complexity in terms of Big-O notation
O (N)
O (N^2)
O (2^N)
O (log N)
Find the slowest time complexity
O (N)
O (N^2)
O (N!)
O (2^N)
Which notation is consistent for every execution?
O (N)
O (N^2)
O (1)
O (2^N)
Indicate polynomial time complexity in terms of Big-O notation
O (N!)
O (1)
O (N^2)
O (log N)
The graphs shows
O(N^2)
O(N)
O(log N)
O(1)
O(N log N)
The graphs shows
O(N^2)
O(N)
O(log N)
O(1)
O(2^N)
The graphs shows
O(N^2)
O(N)
O(log N)
O(1)
O(2^N)
The graphs shows
O(N^2)
O(N)
O(log N)
O(2^N)
O(1)
The graph shows
O(1)
O(2^N)
O(n^2)
O(log N)
O(N)
O(n) is ...
Quadratic
Linear
Logarithmic
Constant
Linearithmic
O(log n) is ...
Quadratic
Linear
Logarithmic
Exponential
Linearithmic
O(2^n) is ...
Quadratic
Linear
Logarithmic
Exponential
Linearithmic
Name the function that can be denoted by n!, where it is the product of all positive integers less than or equal to n; e.g. 3! is 3 x 2 x 1
Equicomplex
Factorial
Linear
Polylinial
Dimensional
The set of values that could possibly come out of a function is called the (a) ?
__________ __________ is the process of providing a definition or interface of a system or object, whilst keeping the inner workings hidden.
(a)
