OLLSCOIL NA hÉIREANN MÁ NUAD THE NATIONAL UNIVERSITY OF IRELAND MAYNOOTH AUTUMN 2019 EXAMINATION CS430 Advanced Concepts and Issues 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 Answer at least three questions Your mark will be based on your best three answers 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 chosen structure/task. [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 use of examples to illustrate your answer. 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 Programming. Answer the following. 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 advantage and one disadvantage for each of these. [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] 欢迎咨询51作业君
