Theory of Computation

Question 1

What is an algorithm?

Answer 1

An algorithm is a sequence of unambiguous instructions for solving a problem for obtaining a required output for any legitimate input in a finite amount of time.

Question 2

What is assignment?

Answer 2

Assignment is the process of giving a value to a variable or constant.

Question 3

What is sequence?

Answer 3

Sequence is the name given to instructions that follow on from one another.

Question 4

What is selection?

Answer 4

Selection is the process of choosing an action to take based on the result of a comparison of values.

Question 5

What is iteration?

Answer 5

Iteration is the process of repeating an operation. For and While loops

Question 6

What is abstraction?

Answer 6

Abstraction is the name given to the process of emitting unnecessary details from a problem. When a solving a problem, abstraction can be used to simplify the problem which can in turn make finding a solution easier.

Question 7

Two types of abstraction

Answer 7

Representational and Generalisation

Question 8

What is representational abstraction?

Answer 8

A representation of a problem arrived at by removing unnecessary details from the problem.

Question 9

What is abstraction by generalisation?

Answer 9

A grouping by common characteristics to arrive at a hierarchical relationship of the ‘is a king of’ type.

Question 10

What is information hiding?

Answer 10

Information hiding is defined s the process of hiding all details of an object that do not contribute to its essential characteristics.

Question 11

Pros of information hiding

Answer 11

• allows different objects to have identical interfaces
• sharing of an interface means that objects do not have to be retrained when changing from using one object to using another
• it means that the user needs to have no knowledge of the object’s internal design
• the internal design can be kept secret
• changes are made easier because changes are local to modules

Question 12

What is procedural abstraction?

Answer 12

Procedural abstraction involves breaking down a complex model into a series of reusable procedures. The actual values used in a computation are abstracted away and a computational method is achieved.

Question 13

What is a procedure?

Answer 13

A procedure is a small section of a program that performs a specific task.

Question 14

What is a function?

Answer 14

A function is a small section of a program that performs a specific task that can be used repeatedly throughout a program, but the task is usually a calculation. Functions perform the task and return a value to the main program.

Question 15

What is functional abstraction?

Answer 15

Procedural abstraction results in a procedure. Abstracting further disregards the particular method of a procedure and results in just a function.

Question 16

What is data abstraction?

Answer 16

In data abstraction, specific details of how data is actually represented are abstracted away, allowing new kinds of data structure to be created from previously defined data structures. Data abstractions forms the basis of abstract data types

Question 17

What is problem abstraction?

Answer 17

In problem abstraction, details are removed from a problem until it is represented in a way that is solvable. This works because a simplified problem is often similar to a problem that has already been solved, meaning that a solution for the problem can be found.

Question 18

What is decomposition?

Answer 18

When using decomposition, a problem is divided into a series of smaller sub-problems. These smaller problems can be solved individually or further divided until all parts of the original problem have been solved.

Question 19

What is composition?

Answer 19

When dealing with a complex problem, composition can be used to combine procedures to form a larger system. Composition is used in abstract data types, where a complex abstract data type is formed for smaller and simpler data types.

Question 20

What is automation?

Answer 20

Automation is the process of putting abstractions of real world phenomena into action to solve problems. Automation is achieved by creating algorithms which are later implemented in code, implementing models in data structures and finally executing the code on the data structures.

Question 21

What is the computational complexity of an algorithm?

Answer 21

The way to think about efficiency is to think about the “cost” of the algorithm. The algorithm that can solve the problem for the lowest cost could then be declared the better algorithm. In general, the amount for resources (or cost) that an algorithm requires in order to return that expected result is called computational complexity. This has two sections: time and space. The time complexity of an algorithm indicates how fast the algorithm runs. The space complexity of an algorithm indicates how much memory the algorithm needs.

Question 22

Big O notation

Answer 22

Simplified analysis of an algorithm’s efficiency. It refers to the complexity in terms of input size, N

Question 23

Orders of complexities

Answer 23

Constant time: independent of input size N: O(1)

linear time: O(N)

quadratic time: O(N^2)

Question 24

Exponential time

Answer 24

The amount of time taken to complete an algorithm will double with every additional item. O(2^n)

Question 25

Polynomial time

Answer 25

Polynomial time often arises when nested loops are used, for example in a number of sorting algorithms.: O(n^2)

Question 26

Linear time

Answer 26

Linear time usually arises from algorithms which go through data step by step. If you have a data structure with n elements and you through it step by step, you end up with linear time complexity. O(n)

Question 27

Logarithmic time

Answer 27

Logarithmic time arises when an algorithm is designed in such a way that the execution time does not increase as fast as the input size.- 0(log n)

Question 28

Constant time

Answer 28

The amount of time taken to complete an algorithm is independent from the number of elements inputted

Question 29

Time complexity of initialising a grid size with empty cells?

Answer 29

O(n^2)

Question 30

Time complexity of the CheckForMatchWithPattern

Answer 30

O(n^2*m), where n is the Gridsize and m is the num of allowed patterns. This is because the method iterates over each cell of the grid in O(n^2) and checks against each allowed pattern

Question 31

Time complexity of the GetSymbolFromUser method

Answer 31

O(k), k number of times the user enters an invalid symbol

Question 32

Time complexity of the DisplayPuzzle

Answer 32

O(n^2); the method iterates through each cell in the grid to print the symbols and creates horizontal lines for each row

Question 33

Time complexity of AddToNotAllowedSymbols

Answer 33

O(1), since it is in constant time

Question 34

Explain the purpose of the Puzzle class.

Answer 34

The puzzle class represents the entire puzzle grid. It contains methods for initializing the grid, checking for matches with a given pattern, getting user input, creating horizontal lines for display, and displaying the puzzle

Question 35

Describe the process and purpose of initializing the grid in the Puzzle class.

Answer 35

The grid is initialized to create an empty puzzle of size GridSize x GridSize. This involves creating and storing instances of the Cell class in a list representing the grid. Each cell starts as empty, and the grid setup allows for easy access and manipulation of individual cells.

Question 36

Explain the logic behind the CheckForMatchWithPattern method. How does it work, and what is its purpose?

Answer 36

The CheckForMatchWithPattern method checks if a specific pattern matches any part of the grid starting from a given row and column. It iterates through possible starting positions, constructs a string representing the symbols in a potential match area, and compares it to allowed patterns. If a match is found, it marks the symbols as not allowed for the cells involved in the pattern. This method is crucial for validating the puzzle against predefined patterns.

Question 37

What is the role of the GetSymbolFromUser method, and how does it ensure valid input?

Answer 37

The GetSymbolFromUser method prompts the user to enter a symbol and ensures that the input is valid by checking it against a list of allowed symbols. It loops until a valid symbol is entered, thus preventing invalid input from being used in the puzzle.

Question 38

Describe how the DisplayPuzzle method works and its purpose in the Puzzle class.

Answer 38

The DisplayPuzzle method prints the current state of the grid to the console. It includes row and column labels for easier reference and creates horizontal lines to separate rows. This method helps visualize the puzzle, making it easier for users to understand the grid’s layout and current state.

Question 39

What is the purpose of the Pattern class, and how does the MatchesPattern method function?

Answer 39

The Pattern class defines a specific pattern that can be matched against the grid. It stores a symbol and a sequence representing the pattern. The MatchesPattern method checks if a given string matches the stored pattern sequence for the specified symbol. This class is used to validate parts of the grid against predefined patterns.

Question 40

Explain the functionality of the Cell class and its methods.

Answer 40

he Cell class represents an individual cell in the puzzle grid. It stores a symbol and a list of symbols that are not allowed in this cell. Key methods include GetSymbol for retrieving the cell’s symbol, ChangeSymbolInCell for updating the symbol, CheckSymbolAllowed for verifying if a symbol is allowed, and AddToNotAllowedSymbols for marking symbols as not allowed. The class encapsulates the state and behavior of a cell.

Question 41

Describe the purpose and behavior of the BlockedCell class.

Answer 41

The BlockedCell class is a specialized type of Cell that is always blocked, meaning no symbols are allowed in it. It overrides the CheckSymbolAllowed method to always return false, ensuring that no symbol can be placed in this cell. This class is used to represent permanently blocked areas in the puzzle.

Question 42

Class: Puzzle

Answer 42

Purpose: Manages the entire puzzle grid, including initialization, user interaction, and display.

Key Methods:
CheckForMatchWithPattern:Checks if a specific pattern matches the grid.

GetSymbolFromUser: Ensures valid symbol input from the user.

CreateHorizontalLine: Creates a string for horizontal grid lines.

DisplayPuzzle: Displays the current state of the grid.

Question 43

Class: Pattern

Answer 43

Purpose: Defines and manages specific patterns that can be matched against the grid.

Key Methods:
MatchesPattern: Checks if a given string matches the stored pattern sequence.

Question 44

Class: cell

Answer 44

Purpose: Represents an individual cell in the puzzle grid.

Key Methods:
GetSymbol: Retrieves the cell’s symbol.

ChangeSymbolInCell: Updates the cell’s symbol.

CheckSymbolAllowed: Verifies if a symbol is allowed.

AddToNotAllowedSymbols: Marks symbols as not allowed.

Question 45

Class: BlockedCell

Answer 45

Purpose: Represents a permanently blocked cell in the puzzle grid.

Key Methods:
CheckSymbolAllowed: Always returns false, indicating no symbols are allowed.

Question 46

What is encapsulation?

Answer 46

Encapsulation is the concept of bundling the data (attributes) and methods (functions) that operate on the data into a single unit, or class, and restricting access to some of the object’s components

Classes like Cell and Pattern encapsulate data and methods.

The Cell class has attributes like Symbol and SymbolsNotAllowed, and methods like GetSymbol(), IsEmpty(), and AddToNotAllowedSymbols(). The details of how symbols are stored and manipulated are hidden from other classes.

The Pattern class encapsulates the symbol and pattern sequence, providing methods like MatchesPattern() to work with these attributes.

Encapsulation ensures that the internal state of objects is protected from unintended interference and misuse, providing a controlled interface for interaction

Question 47

What is inheritance?

Answer 47

Inheritance is a mechanism where a new class inherits the properties and behavior (methods) of an existing class.

The BlockedCell class inherits from the Cell class.
The BlockedCell class extends the Cell class, inheriting its attributes and methods but overriding the CheckSymbolAllowed method to always return false, indicating that no symbols are allowed in a blocked cell

Inheritance allows the creation of a new class based on an existing class, promoting code reuse and establishing a natural hierarchy.

Question 48

What is polymorphism?

Answer 48

Polymorphism is the ability of different classes to be treated as instances of the same class through a common interface. It often involves method overriding and allows for dynamic method invocation.

Method overriding in BlockedCell:
The BlockedCell class overrides the CheckSymbolAllowed method of the Cell class. This allows BlockedCell instances to be treated as Cell instances, but when CheckSymbolAllowed is called on a BlockedCell object, the overridden method is executed.

Polymorphism enables objects of different types to be treated uniformly, allowing for flexible and interchangeable code.

Question 49

What is abstraction?

Answer 49

Abstraction is the concept of hiding the complex implementation details and showing only the essential features of an object.

Abstracting the concept of a cell in the grid:
The Cell class provides a simple interface (GetSymbol(), IsEmpty(), etc.) for interacting with a cell without exposing the underlying details of how symbols are managed and restricted.
The Pattern class abstracts the pattern recognition logic, allowing the main application to use patterns without needing to know the specifics of how patterns are matched.

Abstraction simplifies interaction with complex systems by exposing only what is necessary, making it easier to work with objects and reducing complexity.

Question 50

Explain the difference between an attribute that has a public specifier and an attribute that has a protected specifier.

Answer 50

A public attribute can be accessed from any other class, making it completely accessible throughout the application. A protected attribute, on the other hand, can only be accessed within its own class and by subclasses that inherit from it, providing a higher level of encapsulation and control over how the data is accessed and modified.

Question 51

In object-oriented programming, what is meant by overriding?

Answer 51

Overriding is the process where a subclass provides a specific implementation of a method that is already defined in its superclass. This allows the subclass to tailor or extend the behavior of the method to fit its specific needs.

Question 52

The CheckForMatchWithPattern method in the Puzzle class retrieves symbols from the grid and compares them to allowed patterns. Explain how encapsulation is used in this method.

Answer 52

Encapsulation is used in the CheckForMatchWithPattern method by accessing and manipulating the cell data through methods such as GetCell and GetSymbol, rather than directly accessing the attributes of the Cell class. This ensures that the internal state of each cell is managed through controlled interfaces.

Question 53

Explain why the CheckForMatchWithPattern method would not work correctly if the sequence of symbol retrieval and comparison was altered.

Answer 53

If the sequence of symbol retrieval and comparison in CheckForMatchWithPattern was altered, the pattern string might not be constructed correctly, leading to incorrect matches. The specific order ensures that the pattern string correctly represents the intended sequence of symbols on the grid, which is essential for accurate pattern matching.

Question 54

State one reason why a stack could not have been used instead of a list to store the grid cells in the Puzzle class.

Answer 54

A stack could not have been used instead of a list because stacks operate on a Last-In-First-Out (LIFO) principle, which does not allow for random access to elements. The Puzzle class requires random access to cells for pattern checking and updating, which is efficiently provided by a list.

Question 55

A hash table could have been used instead of a list to store grid cells. Describe how a cell would be added to a hash table.

Answer 55

To add a cell to a hash table, the cell’s position or identifier would be used as the key, and the cell object itself would be the value. The hash table uses a hash function to compute an index based on the key, where the cell is stored. If a collision occurs (i.e., two keys hash to the same index), the hash table employs a collision resolution strategy, such as chaining or open addressing, to store the cell.

Question 56

A hash table can be used to implement a dictionary data structure. Explain why a hash table is a suitable choice for storing cells in the Puzzle class.

Answer 56

A hash table is suitable for storing cells in the Puzzle class because it provides efficient average-case time complexity for insertions, deletions, and lookups (typically O(1)). This efficiency is crucial for operations like checking and updating cell states, which are frequent in the puzzle application. Additionally, a hash table can handle a dynamic number of cells, which may be beneficial if the grid size changes.

Question 57

Describe how the DisplayPuzzle method in the Puzzle class makes use of the CreateHorizontalLine method.

Answer 57

The DisplayPuzzle method calls the CreateHorizontalLine method to generate a string representing a horizontal line. This line is used to visually separate rows of the puzzle grid when displaying the puzzle. By using the CreateHorizontalLine method, DisplayPuzzle maintains a clean and readable output format, enhancing the user interface.

Question 58

Helix Pattern Matching

Answer 58

The method CheckForMatchWithPattern constructs a string from a 3x3 section of the grid arranged in a helix pattern. This string is then compared against known patterns stored in the Pattern class.

Question 59

Storage in a 1D List

Answer 59

The grid is represented as a one-dimensional list. The method GetCell is used to access cells in this list using a formula that converts 2D coordinates to a 1D index: Grid[(GridSize - Row) * GridSize + Column - 1].

Question 60

False Positives

Answer 60

Due to the linear nature of the 1D list, constructing patterns based on incorrect assumptions about grid boundaries can lead to false positives. For example, accessing indices that wrap around the grid’s edges inadvertently may result in incorrect pattern matches.

Question 61

Explain how encapsulation is implemented in the Cell class

Answer 61

Encapsulation in the Cell class is implemented by keeping the Symbol and SymbolsNotAllowed attributes private. Access to these attributes is provided through methods such as GetSymbol(), AddToNotAllowedSymbols(), and CheckSymbolAllowed(). This ensures that the internal state of a cell cannot be directly modified from outside the class, maintaining data integrity.

Question 62

Describe how inheritance is used in the application with an example.

Answer 62

Inheritance is used in the application by having the BlockedCell class inherit from the Cell class. The BlockedCell class extends the functionality of the Cell class by overriding the CheckSymbolAllowed method to always return false, indicating that no symbols are allowed in a blocked cell. This allows BlockedCell to reuse the attributes and methods of Cell while providing specialized behavior.

Question 63

Explain the concept of polymorphism with reference to the CheckSymbolAllowed method in the Cell and BlockedCell classes.

Answer 63

Polymorphism is demonstrated in the application through the CheckSymbolAllowed method. Both Cell and BlockedCell classes have this method, but BlockedCell overrides it to provide a different implementation. This allows instances of BlockedCell to be treated as Cell objects, but when CheckSymbolAllowed is called, the method in BlockedCell is executed, demonstrating polymorphic behavior.

Question 64

Discuss how abstraction is achieved in the Pattern class

Answer 64

Abstraction in the Pattern class is achieved by hiding the details of pattern storage and matching. The class provides a public method MatchesPattern that allows other parts of the application to check if a string matches the pattern without knowing the internal representation of the pattern. This simplifies the interaction with the pattern matching functionality and hides the complexity.

Question 65

Explain a potential issue with false positives in pattern recognition and suggest a fix

Answer 65

: A potential issue with false positives in pattern recognition arises when accessing cells at the edges of the grid, leading to incorrect pattern matches. This can happen due to the 1D list representation of the grid and improper handling of boundaries. A fix for this issue involves implementing boundary checks before accessing cells to ensure indices are within valid ranges. Additionally, modifying the pattern recognition logic to account for edge cases can prevent false positives.

Question 66

What is a set?

Answer 66

A set is an abstract data type which contains unordered unique values.

Question 67

What is set comprehension?

Answer 67

= means such that
£ = means is drawn from
N = natural numbers
^ = and

Question 68

What are empty sets?

Answer 68

Sets can contain 0 elements. Symbols for empty sets are {} and Ø

Question 69

What are finite sets?

Answer 69

Finite sets contain a finite number of items.

Question 70

What is cardinality of a finite set?

Answer 70

Refers to the number of elements in a set

Question 71

What are infinite sets?

Answer 71

Infinite sets are the opposite of finite sets, in that they contain an infinite number of items. There are two divisions: countable and non-countable sets

Question 72

Non-Countable Sets

Answer 72

Non-countable sets contain a larger infinity of numbers - they cannot be paired with natural numbers. Non-countable sets include the real numbers.

Question 73

What are subsets?

Answer 73

Set A is a subset of Set B if it only contains items from Set B. If set A was the same as set B they would be subsets of each other

Question 74

What are proper subsets?

Answer 74

Set A is a proper subset of set B if it only contains items from set b but not all of them. Set A cannot be equal to set B to be a proper subset

Question 75

What are countable sets?

Answer 75

Countable sets have the same cardinality as some subsets of the natural numbers. They include finite sets and countably infinite sets.

Question 76

Membership

Answer 76

If an item is in a set, then ∈ is used to denote this. E.g 3 ∈ R.
If an item is not contained in a set, then ∉ can be used to show this. E.g. -3.2 ∉ N

Question 77

Difference

Answer 77

A set created by set difference will only contain items exclusive to one set. The set
difference symbol is \ or -.

Question 78

What is regular language?

Answer 78

A regular language is any language that a finite state machine will accept.

Question 79

What are regular expressions?

Answer 79

Regular expressions are shorthand ways of describing sets. There are several metacharacters.

• = 0 or more repetitions - ab* is {a, ab, abb, abbb…}
  + = 1 or more repetitions - c+d is {cd, ccd, cccd..}
  ? = previous character options = Colou?r is {Colour, color}
  | = or = e|f is {e,f}
  () = used to group regular expressions = (ab)|(cd)e is {abe, cde}

Question 80

What is a context-free language?

Answer 80

A context-free language is a set of string and symbols that follow the rules of a context-free grammar. Context-free grammars describe which strings are and are not possible in a language by laying out production rules.

Question 81

What is Backus-Naur form?

Answer 81

BNF is a notation which is used to create context-free grammar rules for a regular or natural language; these rules are what govern the syntax of a language. A natural language is that which arises naturally and is used as an everyday language with syntax rules that govern how the language is used to construct expressions

Question 82

What is recursive subroutine?

Answer 82

A recursive subroutine (or recursive function) is a function that calls itself in order to solve a problem. This technique allows the function to break down a problem into smaller, more manageable sub-problems of the same type. Recursive subroutines are particularly useful for problems that can be naturally divided into similar subproblems, like mathematical computations and algorithms involving hierarchical structures.

Question 83

Rules of BNF

Answer 83

Has meta-component(the thing being defined) and a definition. The meta-component is enclosed in angle brackets and comes first in a statement. Next comes the …=

- logical expression OR

Question 84

Syntax diagrams

Answer 84

A syntax diagram is a visual representation of a regular language. Syntax diagrams use rectangles to represents non-terminals and ellipses to represent terminals

Question 85

Limits of computation

Answer 85

While the development of computer hardware and software has meant that many things thought to be difficult by computer have become reality, there is a limit to what is actually able to be solved using a computer. These problems are where there is no algorithmic solution. For example, ai is a limit on computation; we may model behaviour using a series of algorithms but is the computer actually thinking.

Question 86

Classification of algorithmic problems

Answer 86

An algorithmic problem with a finite set of inputs will always be solvable but this does not necessarily mean computable. A problem that has an infinite set of valid inputs causes more problems as some will be solvable whereas others may not. One classification of algorithmic problems can be determined by its time complexity. Any problem that can be solved with an polynomial time complexity or less is known as tractable. Any problem that has no polynomial time complexity of less is called intractable.

Question 87

Halting Problem

Answer 87

The Halting Problem is a fundamental problem in computer science and mathematics that pertains to determining whether a given computer program will eventually stop running (halt) or continue to run indefinitely for a particular input. This problem was first formulated and proven to be undecidable by Alan Turing in 1936. The Halting Problem is important because it illustrates the limitations of what can be computed. It shows that there are certain problems that no algorithm can solve for all possible inputs.

Question 88

What is a stack frame?

Answer 88

Stack frames are fundamental components of the call stack in computer systems, playing a crucial role in function call management and execution. Each stack frame, also known as an activation record, contains all the information necessary to manage and execute a single function call. It contains: return address, local variables, stack pointer