Theory of Computation

Which of the following is a key characteristic of an algorithm?

• It is always implemented in a high-level programming language

• It is a specific sequence of steps that can be followed to complete a task and always terminates

• It is a graphical representation of the logic of a program

• It is a computer program in its own right

Abstraction by generalisation or categorisation is best described as:

• Removing all details of an object that do not contribute to its essential characteristics

• A representation arrived at by removing unnecessary details

• Grouping by common characteristics to arrive at a hierarchical relationship of the 'is a kind of' type

• Representing a computational method

What is the purpose of problem decomposition?

• To combine procedures to form compound procedures

• To hide the particular computation method

• To break a problem into a number of sub-problems, each accomplishing an identifiable task

• To remove details until the problem reduces to one that has already been solved

According to the sources, what is required for automation to solve problems?

• Primarily just implementing models in data structures

• Solely creating and implementing algorithms in program code

• Putting models (abstractions of real-world objects/phenomena) into action by creating algorithms, implementing them in code, implementing models in data structures, and executing the code

• Simply executing pre-existing program code

What is a regular expression primarily used for, according to the sources?

• To define the syntax of a programming language unambiguously

• To model the behaviour of sequential logic circuits

• To describe a set and allow particular types of languages to be described in a convenient shorthand notation

• To compare the time and space efficiency of different algorithms

Which of the following best explains why BNF can represent some languages that cannot be represented using regular expressions?

• a) BNF uses graphical representations called syntax diagrams, which are more powerful than regular expressions

• b) BNF can define terminal symbols, which regular expressions cannot

• c) BNF allows for recursion in its definitions, enabling the representation of nested structures that regular expressions cannot handle

• d) BNF focuses on describing the meaning of language constructs, while regular expressions only focus on patterns

When comparing the complexity of algorithms, what is the key factor to consider?

• The number of lines of code in the algorithm

• The specific programming language in which the algorithm is implemented

• How the algorithm's resource requirements (time or space) grow relative to the size of the problem

• The actual implementation of the algorithm

What does Big O notation primarily describe?

• The exact execution time of an algorithm for a given input

• The amount of memory an algorithm uses for a specific input size

• The upper bound on the growth rate of an algorithm's resource usage (time or space) as the input size increases, often focusing on the worst-case scenario

• The average-case performance of an algorithm across all possible inputs

A problem is considered tractable if: a) It can be solved by any algorithm, regardless of its time complexity b) It has a polynomial (or less) time solution c) It can be solved using a Turing machine d) It has an exponential time solution

• It can be solved by any algorithm, regardless of its time complexity

• It has a polynomial (or less) time solution

• It can be solved using a Turing machine

• It has an exponential time solution

What is the significance of the Halting problem?

• It proves that all programs will eventually stop given sufficient input

• It demonstrates the limitations of current hardware in executing complex algorithms

• It is an example of a tractable problem that is difficult to solve in practice

• It is an unsolvable problem demonstrating that there exist some problems that cannot be solved algorithmically