Across
- 1. A set that is not finite.
- 5. An algorithm whose execution time is directly proportional to the size of its input.
- 7. The reverse process of decomposition where a complex system of compound procedures is built from its smaller, simpler procedures.
- 9. An operator that produces a set containing only the elements present in both initial operand sets.
- 10. An optional state of a FSM that indicates whether or not an input has been accepted by the FSM.
- 15. An unordered collection of values in which each value occurs at most once.
- 19. A property of an algorithm that is related to the amount of resources (memory space and time in particular) that an algorithm uses in its execution.
- 20. A visual representation of a FSM that uses circles to represent states and arrows to indicate transitions between states.
- 22. A set with no elements. Represented by {} or Ø.
- 27. The storage and representation of data in a computer system along with its logical description and interaction with operators. This allows the construction of new compound data objects from existing ones.
- 28. The unsolvable problem of determining whether any program will eventually stop if given particular input.
- 30. An algorithm whose execution time grows exponentially with input size (higher complexity than polynomial).
- 32. A Turing Machine's initial starting state.
- 33. A sequence of steps that can be followed to complete a task and that always terminates.
- 35. An arrangement of objects such that their ordering matters.
- 36. A set with the same cardinality as some subset of natural numbers.
- 37. A function that determines how a Turing Machine moves from one state to the other. It is equivalent to a state transition diagram.
- 43. A mapping from one set of values, the domain, to another set of values, drawn from the co-domain.
- 44. The process of looking at a program's entire code or code extract and running through the instructions as though you are the computer.
- 46. The process of creating algorithms and implementing them as data structures and models of real-life situations that run without a significant need for human intervention.
- 54. An algorithm whose execution time or required memory space is proportional to the input size raised to the power of a constant (k). Eg. O(n^2), O(n^3) etc.
- 55. A set whose elements can be counted off by natural numbers up to a particular number.
- 56. Data abstractions that hide details of how data are actually represented from the user.
- 57. A model of computation for a machine that is always in one of a fixed number of states.
- 58. The process of hiding all details of an object that do not contribute to its essential characteristics.
- 59. A way of describing sets and the elements present within it using strings of characters.
Down
- 2. Problems that cannot be solved algorithmically.
- 3. A human-readable method of writing the steps of an algorithm without any particular programming language.
- 4. A notation technique to express syntax of languages in computing.
- 6. Problems that have no polynomial (or less) time solution.
- 8. A formal model of computation that consists of a finite state machine that controls one or more tapes, where at least one tape is of unbounded length (i.e., infinitely long).
- 10. Simplifying a problem by grouping together common characteristics of a problem to arrive at a hierarchical relationship.
- 11. A measure of the amount of time needed by an algorithm to solve a particular problem of a given input size.
- 12. Simplifying a problem by breaking it down into a series of reusable functions which disregard the particular computational method.
- 13. The set of all ordered pairs (a, b) where a is a member of the first set, A, and b is a member of the second set, B.
- 14. Simplifying a problem by only taking into consideration the necessary details required to obtain a solution, leaving a representation without any unnecessary details.
- 16. The property of an element being within a set.
- 17. An algorithm is said to be correct when it is consistent with the specification and produces the expected output for any given input.
- 18. The repeated removal of unnecessary details from a problem until an underlying problem representation is reached which is identical to a previously solved problem.
- 21. The creation of a set by mathematically defining the elements that qualify to be in the set, rather than listing out all its elements.
- 23. A finite state machine that determines its outputs from the present state and from the inputs.
- 24. Simplifying a problem by breaking it down into a series of procedures or subroutines that are generalised with variable parameters. Knowledge of the implementation of each procedure is irrelevant.
- 25. The process of breaking down a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided.
- 26. A set such that all its elements are present in the other set being considered.
- 29. An algorithm whose execution time grows logarithmically with input size (lower complexity than polynomial).
- 31. The process of combining data objects to form compound data.
- 32. A tabular representation of a FSM that contains the current state, inputs and their consequent successor state.
- 34. A language that can be represented by a regular expression.
- 38. An interpreter that can simulate any Turing machine by reading the description of any arbitrary Turing Machine and faithfully executing operations on data precisely as the machine would.
- 39. An operator that produces a set containing all the elements present in either of the initial operand sets, but not both.
- 40. The number of elements in the set.
- 41. A set that can be counted off by the natural numbers.
- 42. An operator that produces a set containing all the elements from both initial operand sets.
- 45. Problems that have a polynomial (or less) time solution.
- 47. A set that is fully contained in another set, and the other set contains elements that are not present in the proper subset.
- 48. A measure of the amount of memory space needed by an algorithm to solve a particular problem of a given input size.
- 49. The use of a set of facts (axioms) to draw conclusions and determine whether new information is true or false.
- 50. A state with no outgoing transitions that halts a Turing Machine.
- 51. An algorithm that always takes a constant amount of time to execute, regardless of the input size.
- 52. Problems that can be solved algorithmically.
- 53. The result of abstracting away the actual values used in any particular computation is a computational pattern or computational method.