Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Computer Science > Fundamentals of Computational Thinking. > Flashcards

Fundamentals of Computational Thinking. Flashcards

1
Q

What is logical reasoning?

A

The process of using a set of given facts to determine whether new facts are true or false.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the advantages of logical reasoning?

A

Helps understand the nature of problems, identify the facts relevant to the problem and to draw conclusions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is an algorithm?

A

A step-by-step procedure for carrying out a particular task.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is automation?

A

Creating a computer model of a real-life situation and putting it into action.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How is automation done?

A

Understanding the problem
Creating suitable algorithms
Using appropriate data to solve the problem.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are the considerations with automation?

A

Identify the key factors that make the model accurate and to consider what data to use and where to get it from.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is abstraction?

A

To reduce problems to their essential features, ignoring the unnecessary details.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is representational abstraction?

A

Process of removing unnecessary details so only information required to solve the problem remains.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is abstraction by generalisation/ categorisation?

A

The concept of reducing problems by putting similar aspects of a problem into hierarchical categories.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is procedural abstraction?

A

The concept that all solutions can be broken down into a series of subroutines.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is Top-Down design?

A

The main system at the top and breaking it down into smaller units.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are the considerations of Top-Down design?

A

What event triggers the subroutine
How subroutines link together
How errors are handled.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is functional abstraction?

A

Breaking down a complex problem into a series of reusable functions.
Main processes defined in terms of functions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is data abstraction?

A

Hiding how data is represented so it is easier to build a new kind of data object.
Separates implementation from interface.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is data composition?

A

Data objects are combined to create a compound structure.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is problem abstraction?

A

Reducing a problem into its simplest components until the underlying processing requirements to solve the problem are identified.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is information hiding?

A

The process of hiding all the details of an object that doesn’t contribute to its essential characteristics.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is encapsulation?

A

A method of implementing the information hiding principle by storing data and methods within a class/ object.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is decompositon?

A

Breaking down a large task into smaller more manageable subtask.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is deprocedural composition?

A

The process of looking at system as a whole then breaking it down into subroutines needed to complete the task.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is composition?

A

Building up a whole system from smaller units.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is procedural composition?

A

Process of creating a working system from the abstraction.
Linking procedures to make compound ones and combining data structures to form compound structures.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What are finite state machines (FSM)?

A

Any device that stores its current status and whose status can change as the result of an input.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What are FSM used for?

A

Used as an conceptual model for designing and describing systems.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What are state transition diagrams?

A

A visual representation of an FSM.
Uses circles to represent each state and arrows to represent the transitions that occur as a result of an input.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is a state transition table?

A

A tabular representation of an FSM machine.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is a Turing machine?

A

A theoretical model of computation.
A FSM with the ability to read/write data to an infinite tape.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What components make up a Turing machine?

A

Tape divided into cells, where each cell contains a symbol. (Acts as memory)
Read/Write head which travels along the tape one cell at a time.
Finite alphabet of symbols.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What does the symbol □ mean in the Turing machine?

A

An empty/blank cell.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What states must the Turing machine contain?

A

Start state
At least one state
Halting state, which stops the Turing machine.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What is the definition of a transition function for Turing machines?

A

A method of indicating how the machine moves between states and what data is written at each state.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is the formula for transition functions?

A

δ(CurrentState, InputSymbol) = (NextState, OutputSymbol, Movement)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What is a Universal Turing machine?

A

A theoretical machine that can simulate any number of Turing machines by taking their description and input data, to produce a range of outputs.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

What is a regular language?

A

Any language that can be described with regular expressions or FSM.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What is a regular expression?

A

A notation containing strings of characters that can be matched to the contents of a set.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

What are the uses of regular expressions?

A

To define and search a set.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

What is a set?

A

A defined collection of objects that do not repeat.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

What does a|b|c mean in regular expressions?

A

a or b or c

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What does abc mean in regular expressions?

A

a and b and c

40
Q

What does * mean in regular expressions?

A

Zero or more of the proceeding element.

41
Q

What does + mean in regular expressions?

A

One or more of the proceeding element.

42
Q

What does ? mean in regular expressions?

A

Zero or one of the proceeding element.

43
Q

How can regular expressions be represented?

A

Using FSMs.

44
Q

What does . mean in standard expressions?

A

Wildcard - matches to any character.
eg: .ole = mole, hole, vole

45
Q

What are standard expressions?

A

Used to describe a sets of strings that conform to a particular pattern.

46
Q

What does [] mean in standard expressions?

A

Matches a single character.
eg: [mh]ole = mole, hole, not vole

47
Q

What does [^] mean in standard expressions?

A

Matches any character except the one in the brackets.
eg: [^m]ole = vole, hole, not mole

48
Q

What does {a,b} mean in standard expressions?

A

Matches the character any number of times.
eg: a{2,5} = aa,aaaa, not a

49
Q

What is a context-free language?

A

A method of describing the syntax of a language when the language is too complex for regular expressions.

50
Q

What is Backus-Naur Form (BNF)?

A

A formal notation describing the syntax of a language.

51
Q

How does BNF work?

A

Breaks down symbols until the terminal symbol is reached. (Cannot be broken down any more).

52
Q

What does <> mean in BNF?

A

Surrounds symbols or elements.

53
Q

What does ::= mean in BNF?

A

“is defined as”.

54
Q

What is recursion in BNF and give an example?

A

A method that allows a set to be concise while allowing an infinite number of combinations.

<digit> = 0|1|2|3|4|5|6|7|8|9
<integer> = <digit>|<digit><integer>
</integer></digit></digit></integer></digit>

55
Q

What are syntax diagrams?

A

A way of representing context-free languages.

56
Q

What does an oval represent in syntax diagrams?

A

A terminal element.

57
Q

What does an rectangle represent in syntax diagrams?

A

A non-terminal element.

58
Q

What is set building/comprehension?

A

The process of creating sets by describing them using notation, rather than listing.

59
Q

What does {} mean in terms of set comprehension?

A

Contains the contents of the set.

60
Q

What does | mean in terms of set comprehension?

A

“such that”

61
Q

What does ∊ mean in terms of set comprehension?

A

“is a member of”

62
Q

What does ^ mean in terms of set comprehension?

A

And

63
Q

What does Ø mean in terms of set comprehension?

A

Empty set.

64
Q

What are finite sets?

A

Sets that have cardinality, meaning it can be counted using natural numbers.

65
Q

What is the Cartesian product?

A

Combining elements of multiple sets to create a set of ordered pairs.
eg: A = {a,b} B = {1,2}
result = {(a,1), (a,2), (b,1), (b,2)}

66
Q

What is the union of sets?

A

A set of all elements in bot sets.

67
Q

What is the intersection of sets?

A

A set containing elements common in both sets.

68
Q

What is the difference of set A and B (A/B)?

A

A set of all the elements that are in set A but not in set B.

69
Q

What is a subset?

A

A set where all elements of one set are entirely contained within another.
A = B

70
Q

What is a proper subset?

A

One set entirely contained within another set, where the other set has additional element.

71
Q

What is an algorithm?

A

A set of instructions required to complete a particular problem.

72
Q

How is the efficiency of an algorithm determined?

A

How long it takes to run (time) and how much memory is required (space)?

73
Q

What is a function?

A

Relates an input to an output.

74
Q

What is the domain?

A

The set of values that can go into a function.

75
Q

What is a codomain?

A

A set of values that could be output from a function.

76
Q

What is the range?

A

The set of values actually produced by a function.

77
Q

What is Big O notation?

A

A method of describing the time and space complexity of an algorithm.

78
Q

What does Big O notation calculate?

A

The maximum amount of time an algorithm would take to complete.
How much time and space it takes to execute an algorithm as the input size increases.

79
Q

What is time and space complexity?

A

How much time and space an algorithm requires.

80
Q

What is the input size?

A

Whatever you’re asking an algorithm to work with?

81
Q

What is O(1)?

A

Constant time
An algorithm that executes in the same amount of time regardless of the input size.

82
Q

What is an example of O(1)?

A

Accessing an array, as accessed directly by referring to its position.

83
Q

What is O(N)?

A

Linear function
When the runtime of the algorithm will increase directly proportional to the input size.

84
Q

What is an example of O(N)?

A

Looping around a list.

85
Q

What is O(N²)?

A

Polynomial function
When the runtimes of the algorithm will increase proportionally to the square of the input size.

86
Q

What is an example of O(N²)?

A

Nested statements
Bubble sorts

87
Q

What is O(2ⁿ)?

A

Exponential function
When the runtime doubles with every additional unit increase in the input size.

88
Q

What is the problem with O(2ⁿ)?

A

It is an intractable problem, meaning it can’t be solved with a computer in a reasonable amount of time if the input size is large.

89
Q

What is O(logN)?

A

Logarithmic function

90
Q

What is an example of O(logN)?

A

Binary search O(log₂N)
As each subsequent split of the data takes less time as only half the data is being searched.

91
Q

What is Big O notation used for?

A

Find the most efficient solution to a problem.

92
Q

What is the order of efficiency with Big O notations?

A

O(1)
O(logN)
O(N)
O(N²)
O(2ⁿ)

93
Q

What is an tractable problem?

A

A problem that can be solved in an acceptable amount of time.

94
Q

What is an intractable problem?

A

A problem that cannot be solved in an acceptable time frame, but is theoretically possible to solve.

95
Q

What are heuristic algrithms?

A

Algorithms that provide and incomplete or approximate solution to intractable problems, buy ignoring certain elements or accepting a non-optimal solution.

96
Q

What is an unsolvable problem?

A

A problem that has been proven to not be solved on a computer.

97
Q

What is the Halting problem?

A

It is impossible to write a program that can work out whether another problem will halt given a particular input.

Computer Science (10 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions