THE NATIONAL UNIVERSITY OF IRELAND
MAYNOOTH

AUTUMN 2019 EXAMINATION

CS430

in Computer Science 1

Dr. C. Hayes, Dr. J. Timoney, Dr. D. O'Donoghue, Dr. B. Davis, Dr. E. Galvan,
Dr. D. Woods

Time allowed: 2 hours

All questions carry equal marks

CS430 Page 1 of 3 Autumn 2019
[25 marks]
1 (a) What problem on 6-bit binary words is solved by the following
iterated Boolean circuit (IBC)? Show how the circuit operates by
giving two example 6-bit inputs and then clearly showing how
those inputs are transformed layer-by-layer.

[5 marks]
(b) Specify an iterated Boolean circuit (IBC) called "Sorting"
that sorts any 6-bit string, by moving all 1-bits to the top and all
0-bits to the bottom. Gates can be specified pictorially using
clear drawings or by using truth table(s). Explain how your circuit
works in a few sentences. (For example given inputs 000010 or
000001 the Sorting circuit should output 10000; or given
inputs 001010 or 100001 the Sorting circuit should output
110000.)

[5 marks]
(c) The following four tiles were converted from an IBC gate. Define
the gate, either pictorially or by giving the gate truth table. (You
can assume the tiles are designed to grow to the right starting
from a seed on the left.)

2
2
2
2
0w1′
0w21w2′
1w1
0w1′
0w2 0w2
1w10w1
0w2′ 0w2′
1w1′
1w11w1′
1w21w2′

[5 marks]
CS430 Page 2 of 3 Autumn 2019
(d) Specify a randomised iterated Boolean circuit and describe what
it does. Gates can be specified pictorially using clear drawings or
by using truth table(s).

[5 marks]
(e) Self-assembly is concerned with the formation of structure by
components (e.g. molecules in practice, or tiles in theory)
coming together to form assemblies. Algorithmic self-assembly
is concerned with using algorithms to drive the process of self-
assembly. Give an example of a structure that can be built, or a
task that can be solved, using the technique of algorithmic self-
assembly. Explain what is intrinsically algorithmic about your
[5 marks]

[25 marks]
2 (a) Describe three ways that the Turing Test (TT) is Not suitable as
a basis for evaluating computational creativity? Discuss any
implications this might have for the task of assessing the output
of computationally creative systems.

[5 marks]
(b) Describe the difference between the following two pairs of terms,
as related to their use within Computational Creativity? Make
P-Creativity and H-Creativity,
Combinatorial (Improbable) creativity and Analogical
Creativity

[5 marks]
(c) Using an example or otherwise, discuss how an evolutionary
algorithm might produce a “creative” output. Why might its
outputs be considered creative and what aspects of the EA
contributed most to its “creativity”?

[5 marks]
(d) Consider the problem of finding novel comparison between
lexical data (C#, Java or even English text). Describe in detail
how you would go about finding novel analogies to some given
problem? How might you use that analogical similarity to create
new knowledge?

[10 marks]

[25 marks]
3 (a) Multiple operators have been proposed in tree-like based Genetic
 Name and briefly describe two recombination mechanisms.
[ 10 marks]
CS430 Page 3 of 3 Autumn 2019
 Name and briefly describe two mutation mechanisms.
 Draw these four mechanisms and explain their implications
during evolution.
(b) Name two gradient-based optimisation methods and indicate one
[8 marks]
(c) What is an inverse problem? Provide a concrete example to
explain this.

[7 marks]

[25 marks]
4 (a) Define information Extraction(IE)? Briefly state how it differs from
Information Retrieval(IR)? List and define two of the core tasks
in IE.

[4 marks]
(b) Summarise and compare knowledge based approaches with
machine learning based approaches within the context of
Natural Language Processing(NLP) for Information Extraction.

[8 marks]
(c) List five linguistic features used for Machine Learning
approaches to IE used?

[5 marks]
(d) List and describe each of the standard linguistic components in
a Natural Language Processing(NLP) pipeline for Information
Extraction.

[8 marks]

Email:51zuoyejun

@gmail.com