Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

computational thinking > topic 2 - fundamental problems > Flashcards

topic 2 - fundamental problems Flashcards

(103 cards)

Start Studying
1
Q

what is computer science?

A

Computer Science is the study of computers and what they can do;the inherent powers and limitations of abstract computers; the design, char-acteristics and use of real computers; and the applications of computers tosolve problems

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

what is the difference between computer sciences and other sciences?

A

Problems in Computer Science are primarily about the repeated journey towards some goal, rather than just establishing a goal in isolation.

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

/what are key to the problems in computer science?

A

the constructive nature of their solutions; the repeated application of these solutions; and the concern with and measurement of the difficulty of solving problems

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

what are essential notions for finding solutions giving an example for each relating to a travelling salesman?

A
  • computation (the salesman’s machine);* resource (the time taken); and* correctness (the quality of the solution)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

how does the idea of abstraction of real world problems cause issues?

A

in order for a computer to solve a solution to a problem, the problem must be astracted so it shares the main characteristics however not completely identical to the real issue.

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

what is abstraction focused on in computer science?

A

with ‘information hiding’ than with ‘information neglect’

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

what are the essential qualities of the abstraction to solve a problem?

A

these abstractions need to be represented and manipulated within a computer program; and* these abstractions mirror reality sufficiently closely so that any conclusions reached (by the computer) remain valid as regards the real-world problem

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

what is the trade off when it comes to abstracting?

A

A trade-off arises between the quality of the solution and the general cost of getting the solution

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

how do you abstact a problem?

A

start with a base issue and then develop nessecary additions in order to be more accurate to true issue. for example the travelling sales man problem you may at first only look at the distances between citys then you may take into account the speed limits of the roads which will affect time taken to travel and then you can take into account the level of trafffic and so on

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

what is the features of a decision problem?

A

they consist of a set of instances and a subset of I which is a yes instance ’,with it being our job to decide upon the answer correctly.

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

how do you solve a desicion problem?

A

In order to solve a decision problem, we need to decide (using somealgorithm or program) whether any given instance is or is not a yes-instance

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

how would you represent in a graph a map colouring problem where there is only three colours and they cannot touch a state with the same colour?

A

represent the important information on a graph with nodes respresenting all the states and then join lines called edges between the nodes that are touching. the graph has the function G= (V, E) where V is a vertex (node) and E is set of edges

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

what was the first substantial theorem to be proved using a computer?

A

the four colour theorem which says every map can be coloured using 4 colours

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

how do you sort a list using lexicographic ordering?

A

we compare two lists by working down the lists entry by entry until two corresponding entries differ;* the list with the least entry (we assume that there is some ordering on the entries) is deemed to be the least of the two lists;* if we never find two different corresponding entries but run out of one of the lists then this shortest list is the least list (note that in this case ,the shorter list is a prefix of the longer one)

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

how would you abstract the question” Can you find a route from the start town to the end town, composed of interim routes from town to town, but so as to avoid motorways?” and what are the pros and cons?

A

you can abstract it two ways —-a graph G = (V, E) where the vertices correspond to towns and an edge(u, v) to the existence of a route from town u to town v avoiding any other town; together with* a list of edges corresponding to the (direct town-to-town) routes that are motorways; and* the start and end towns.—– or just as towns as the nodes and the various roads that are not motorways will be the edges. first is worst for information storage however is better if you want to make adjustments in future

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

what does a search problem consist off?

A

a set of instances I;* a set of solutions J; and* a binary search relation R ⊆ I × J

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

what is a binary search relation?

A

Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found.

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

why do you have to abstract both instances and the solution for a search problem?

A

we have to abstract solutions so that a solution returned from our computation corresponds to a solution of the underlying real-world (search) problem

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

what is the relationship between search problems and decision problems?

A

It is almost always the case that corresponding to any decision problem, there is a search problem and vice versa. as a search problem aims to find a solution rather than just prove there is one. and a decision problem will have the same set of instances as the search problem and the yes instance is when x is an instance and there is a corresponding to solution that matches x

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

what does an optimasation problem consist of ?

A

it consists of a set of instances I;* for every instance x ∈ I, there is a set of feasible solutions f (x);* for every instance x ∈ I and for every feasible solution y ∈ f (x), there is a value v(x, y) ∈ N = {0, 1, 2, . . .} giving the measure of the feasible solution y for the instance x; and* there is a goal which is either min or max .

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

what are the three outcomes of a maximisation optimisation problem?

A

Ideally you want to find a maximum however it may be the case that there are no feasible solutions for an instance; or for a maximization problem, there are feasible solutions of increasingly large measure. in both of the last two cases this should be signalled

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

how can you decide whether a graph can be coloured by hand?

A

you will need to develop a systematic procedure/ algorithm so that if the answer is yes you will be able to draw it by hand and if the answer is no then there still might be a possibility that it can be drawn by hand ie a false negative.

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

what is an effective procedure to solve a solution?

A

an effective procedure is one that is easy to implement and also gives back as few false errors as possible

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

what is the optimal solution to the colouring of a graph problem?

A

it is optimal when you can colour a graph with as few colours as possible and the solution is proper ie no same colours are touching

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
how can you solve the graph colouring problem using a greedy algorithm?
you number each verticie and number each colour in increasing order. you begin by colouring verticie 1 by colour 1 and then move to colour verticie two. if the verticie is touching an already coloured verticie it will use the lowest order colour. this process wil continue until all verticies are coloured.
26
why is it called a greedy algorithm?
it is called a greedy algorithm due to the fact that it works through greedily choosing the best thing to do for that one verticie
27
what are the issues with a greedy algorithm?
it isnt that sophisticated so as a result a lot more false negatives arise. also the efficency of the algorithm in finding the solution will depend heavily on how the verticies are ordered
28
what is the rule about greedy algorithms and the optimal solution?
for every graph, there always exists an ordering of the vertices so that greedily colouring the vertices yields a colouring using as few colours as possible
29
what is the most effective way to solve the 4 colour map problem?
suppose there was a vertex with strictly less neighbours then 4 in the graph G. if you remove this vertex and all its incident edges with other vertex then you will be left with graph G1. if G1 can be 4 coloured then so must G. if G1 has any vertex with less than 4 neighbours then you can remove that vertex to get G2 and so on to find G3, G4 etc. you will eventually not be able to remove any more vertex so if this final shape can be 4 coloured then the whole graph G can be 4 coloured solving the problem.
30
how can you abstract the sports day problem as a graph?
The sports day problem can be abstracted as a graph G = (V, E): vertices of V consist of the different events; and there is an edge (u, v) ∈ E if there is some athlete who wishes to participate in both the event corresponding to vertex u and the event corresponding to vertex v.
31
what is an independet set ?
An independent set U in a graph G = (V, E) is a subset U ⊆ V of vertices so that no vertex in U is joined by an edge to any other vertex of U .
32
what is a maximum independent set?
A maximum independent set in G is an independent set of the greatest size possible.
33
what is a maximal independent set?
an independent set that is not contained in any other independent set (but where there might be a totally different independent set that contains more vertices).
34
how can you solve the sports day problem?
We chose a vertex v of our graph of smallest degree (that is, with the fewest number of neighbours and we break ties arbitrarily) and add itto our independent set I. We remove v (and its incident edges) as well as all neighbours of v (and their incident edges) from our graph and repeat (with our new, smaller graph). this will provide us with a large independent set as we are repeatedly removing as small a neighbour of vertices as possible each time.
35
provide a method to solve the Travelling salesperson problem?
Start at some city. Iteratively move to the nearest city (breaking ties arbitrarily). Output the tour obtained.
36
what is a programming language
A programming language essentially provides a means for transforming an algorithm into a form suitable for execution by a computer; or, more precisely, into a program that can then be transformed (trivially) into a form suitable for execution by a computer.
37
what are typical concepts associated with algorithms
an algorithm works on some input. an algorithm produces some output; the steps of an algorithm are precisely stated; and an algorithm can be applied generally to a variety of inputs.
38
an algorithm is a computer program, yes or no?
no, A computer program is some-thing written in a (concrete and explicitly defined) programming language, and an algorithm can have many different implementations as a program(even within the same programming language!)
39
why can you not provide a formal definition for an algorithm?
if we can formally define an algorithm then what we have is a programming language; yet, an algorithm is supposed to be different from a program
40
what are the two phases to converting an algorithm into something that the computer can execute?
the first phase is describing (that is, implementing)the (‘ghostly’) algorithm using a programming language; and the second is converting the resulting program into something that is machine-executable
41
what is the whole point of having different programming languages?
The whole point of having all these different programming languages is so as to make the first phase as satisfactory as possible for different programmers working in different environment
42
what are examples of imperative ( also known as procedural ) programs?
python, C, C++, Java
43
what are imperative programs characterized by?
Imperative programs are characterized by their use of programming instructions to explicitly change a program’s state; that is, the current status of entities within the program, such as variables (more precisely, the state is given by the different values held in the different memory locations).
44
what is the easiest programming parigm for a computer to transform and execute and why?
an imperative program because it is the closest to the abstraction of computer hardware as a bunch of memory locations the values of which are explicitily manipulated by the CPU
45
what are declaritive programs?
decractive programs are programs which say what rather than how. they come in many forms: functional and logic
46
what is a functional declarative program?
functional programs are defined as a collections of mathematical functions and computations is undertaken by composing these functions together.
47
what is the difference between functional programs and imperative programs?
Unlike imperative programming languages, there is no notion of ‘state’ in a functional program, with the flow of control (which in an imperative program comes about by using, for example, if-statements and while-loops) being determined by function composition
48
what is a logic program?
Logic programs specify a ‘logical solution’ (using the reasoning incumbent within some logic); that is, a logic program generally consists of a set of axioms and a goal statement, along with some rules of inference.
49
what is the purpose of the rules of inference in a logic program?
The rules of inference are applied to determine whether the axioms are sufficient to ensure the truth of the goal statement.
50
what is a data orientated program?
programs that work with data through manipulation and searching relations (tables)
51
what is a scripting program?
Scripting programs are designed to automate frequently used tasks that involve calling or passing commands to external programs. They are designed for ‘gluing’ existing programs together.
52
what is the assembly programming language?
a low level language that provides the interface between machine code and a high level programming language.
53
what is a concurrent programming language?
they provide facillities for concurrency ( threads, processes); may be message passing or shared memory
54
what is a data flow programming language?
the programs are specified by flows of data which are usually visual
55
what are fourth generation programming languages?
high level languages built around databases usually used commercially
56
what are list based programming languages?
built around the list data structure and is popular with artificial intelligence
57
what are visual based programming languages?
Visual languages allow the user to specify programs using visual representations rather than by providing textual instructions; as such, dataflow programming languages are special cases.
58
what are the 6 main drivers for more programming languages?
productivity, reliability, security, execution speed, curiosity, style
59
why is productivity a driver for more programming languages?
old programming languages such as C++ are very detailed and require large amounts of code and so there are lots of expenses in developing and maintaining systems built with that code. newer scripting programming languages such as python speed up that software development with reduced response times and costs and supported fast user interface development
60
why is reliability a driver for more programming languages?
Some programming languages have features so that programs written in that language will be more reliable. Some of these features might involve: type checking, where we try to ensure that, for example, comparisons of two different types of values in a program execution, say a number and a letter of the alphabet, do not arise; and exception handling, which is the ability to deal with errors that arise during a program’s execution. Some programming languages allow for aliasing which is the ability to use different names to reference the same memory location. Aliasing can be a very dangerous feature as programmers often forget that the value of a variable has changed even though the variable itself has not been touched
61
why is security a driver for more computer programming languages?
The Internet has raised the question of whether we can trust our programming languages. this is due to the fact that by visiting a web page you execute the code on your own machine which could allow a malicous programmer to breach your security
62
why is execution speed a driver for more computer programming languages
imperative programming languages are closely tied to our abstraction of computer hardware as a bunch of memory locations the values of which are explicitly manipulated by the CPU. Such imperative programming languages will not really be usable on a parallel computer (such as a multi-core or GPGPU machine) and consequently we will not achieve the increases in execution speed promised by parallel computing.
63
why is curiosity a driver for more computer programming languages?
Computer Scientists will never stop having ideas about how things might be done differently. As soon as someone describes some algorithm in a different way, out come the programming language designers to build a new programming language!
64
why is style a driver for more computer programming languages?
As they say: ‘Beauty is in the eye of the beholder ’, and this applies equally to programming languages! people want to be different to other programmers
65
what are the general principles that any half decent programming language should adhere to?
be easy to use, with its programs easy to read, write and understand; support ‘abstraction’ so that adding new features and concepts should be possible; support testing, debugging and program verification (that is, proving that programs are correct; more of this later); and be inexpensive to use, in terms of execution time, memory usage and maintenance costs.
66
what does every programming language include?
a syntax and a semantics
67
what is a syntax
the rules that govern what makes a program legitimately written
68
what is semantics?
the rules that govern what a program 'means'
69
why do the semantics need to be precisily defined ?
the semantics of a programming language should be precisely defined so that we are left in no doubt as to what a program will do when it is executed.
70
why do the syntax need to be precisily defined?
The syntax of a programming language should be precisely defined so that as to what constitutes a legal program is unequivocal. ( the computer algorithm will decide what programs make sense)
71
does every programming language have a formal syntax?
yes
72
does every programming language have a formal semantics?
no
73
how should we interpret the word precise?
it should be interpretated as mathematically formal
74
what are the three different types of formal semantics?
denotational semantics, operational semantics, axiomatic semantics
75
what is denotational semantics?
a program’s meaning is given mathematically as a suitable mathematical structure (such as a function or a partial function), and these mathematical structures should be compos-able so that the denotations of parts of programs can be assembled to obtain a denotation of the program itself;
76
what is operational semantics?
a program’s meaning is given in terms of the individual steps of a computation the program makes when it executes; for example, each individual step might be described according to how the program’s state changes;
77
what is axiomatic semantics?
a program’s meaning is given indirectly in terms of a collection of logical properties it satisfies, and how these properties are maintained during or after execution.
78
why is there increasing demands for more formal semantics?
as computers become more pervasive and are used in more and more safety critical applications, there are more demands placed upon programming languages to write safety criticial programs with these demands relating to their formal semantics. In Computer Science, informality leads to ambiguity which leads to divergence which leads to errors!
79
what are the two essential mechanisms for moving from high level programs to machine code?
the compiler and the interpreter
80
why is the compiler an essential mechanism for moving from high level programs to machine code?
A compiler transforms the high-level program to machine code for execution by the CPU. the compilers are specific to certain type of CPU.
81
why is the interpreter an essential mechanism for moving from high level programs to machine code?
An interpreter translates one instruction (or possibly a small number of instructions) of the high-level program at a time, as it is needed, with the translations interspersed with the activity of the program itself.
82
what programming languages use compilers?`
C, C++ have their programs compiled directly to machine code
83
what programming languages use interpreters?
The programming languages Python, Ruby and Javascript, forexample, all have their programs translated.
84
what are the trade offs that relate to time whether using compilation or interpretation is preferable?
Compiled programs tend to run faster as the execution of the resulting compiled program (machine code) isn’t interspersed with compilation activity.
85
what are the trade offs that relate to optimisation whether using compilation or interpretation is preferable?
Compilation spends time optimising so as to enhance performance. This isn’t possible with interpretation where the high-level program is handled piecemeal (in an unsystematic way, through partial measures taken over a period of time.)
86
what are the trade offs that relate to correcteness whether using compilation or interpretation is preferrable?
Compilation spends time analysing so as to search for bugs and elim-inate certain run-time errors. Again, this isn’t possible with interpre-tation where the high-level program is handled piecemeal. (in an unsystematic way, through partial measures taken over a period of time.)
87
what are the trade offs that relate to memory whether using compilation or interpretation is preferrable?
Interpreted programs tend to use memory better. To see why this might be the case, imagine compiling a large program. You would need enough (fast) memory to store the whole compiled program. However, if the instructions of the high-level program are handled one by one then you only need enough memory to store (the translations of) a small number of instructions.
88
what are the trade offs that relate to facilitating development whether using compilation or interpretation is prefferable?
Interpreted programs facilitate development in that as a program is developed, it is executed and bugs are unearthed with the code then being rewritten (in sometimes what can seem a never-ending cycle!). If a program has to be compiled each time it is to be executed then the compilation time can mount up. Interpretation is (pretty much) free from this compilation time.
89
what are the trade offs that relate to facilitating development whether using compilation or interpretation is preferable?
Interpreted programs facilitate development in that as a program is developed, it is executed and bugs are unearthed with the code then being rewritten (in sometimes what can seem a never-ending cycle!). If a program has to be compiled each time it is to be executed then the compilation time can mount up. Interpretation is (pretty much) free from this compilation time.
90
what is dynamic compiling?
Dynamic (just-in-time) compilation is when some of the operations within the compilation of the source program (like optimisation) are postponed until the initial stages of execution have been completed.
91
what is a negative of using dynamic compiling?
it increases initial execution time
92
what does a lexical analyser do?
A lexical analyser reads a high-level program as a string of symbols and converts it into basic syntactic components, i.e., tokens in a token stream (it recognises, for example, reserved words from the program-ming language and other basic symbols)
93
what does a syntax analyser do?
A syntax analyser (or parser) recognises the syntactic structure of the token stream and this results in a parse tree (or a syntax tree). This parse tree often contains redundant information and is simplified; it is also used by the compiler to undertake various analysis operations (like type-checking).
94
what occurs in the translation phase?
A translation phase flattens the (modified, simplified and optimised) parse tree into a linear sequence of intermediate code.
95
what occurs in the code generation phase?
A code generation phase converts the intermediate code into assembly (and then on to machine code). every type of processor has its own assembly language and machine code.
96
how much of the compiling time is taken up by the lexical anaylsis and why?
the lexical analysis phase can account for more than 50% of compile time, for character handling can be expensive and there is a large number of characters in a program in comparison to tokens.
97
what is a regular expression defined as?
any a (letter)∈ Σ(alphabet) is a regular expression; * ∅(empty set) and (empty character) are special regular expressions; and * if ω and ω′ are regular expressions then so are: – (ωω′) – (ω | ω′) (| is also written + or ∪ or ∨) – (ω∗).
98
what set of strings does every regular expression denote a set of strings?
a(letter), ∅(empty set) and  (empty character) denote the sets of strings {a}, {} (the empty set of strings)and {} (the set containing just the empty string ), respectively; and * if ω and ω′ denote the sets of strings R and S then: – (ωω′) denotes {xy : x ∈ R, y ∈ S}(the string xy is the string x concatenated with the string y) – (ω | ω′) denotes R ∪ S – (ω∗) denotes {x1x2 . . . xn : n ≥ 0, x1, x2, . . . , xn ∈ R}(∗ is called Kleene iteration; note that the set denoted by (ω∗)always includes the empty string : put n = 0 into the definition
99
what is the method of defining regular expressions?
Our methods of defining regular expressions and defining the sets of strings denoted by regular expressions are both recursive; that is, we define something ‘in terms of itself’.
100
how do you define a finite state machine?
M = (Σ, Q, δ : Q × Σ → Q, q0 ∈ Q, F ) where: * Σ is some finite alphabet; * Q is some finite set of states with initial state q0 and set of final states F ⊆ (subset of) Q; and * δ : Q × Σ → Q is the transition function.
101
how does a finite state machine work?
you input a string into the finite state machine, if the finite state machine is in a particular state and given a particular character you should change state. if we finish in one of the final states then it is accepted if not it is rejected.
102
what is the theorem that relates to finite state machines?
A set of strings is represented by a regular expression if, and only if, it is accepted by a finite state machine (such sets of strings are called the regular languages.
103
what is the primarily goal of syntax anaylsis?
Our primary goal is to take such a token stream and decide whether it corresponds to a legitimate program or not, so that if it does then we’ll transform it into machine code (possibly with some useful optimisations).

computational thinking (5 decks)

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