Brainscape's Knowledge GenomeTM

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


See full index

Computational Thinking > Fundamental Problems > Flashcards

Fundamental Problems Flashcards

1
Q

What are compiled languages?

A

The whole program is converted/compiled into machine code before being run, and only runs on a specific type of machine

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

What are interpreted languages?

A

An interpreter reads a small number of instructions at a time and translates them

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

Differences between compiled and interpreted languages

A

Compiled: Faster, code is analysed and optimised during compilation, avoids certain runtime errors
Interpreted: Better use of memory, easier to develop software with

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

How do bytecode languages such as Java work?

A

Programs are compiled into bytecode, which is higher level than machine code but still fast to interpret, and then translated by a virtual machine

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

Difference between syntax and semantics

A

Syntax is how a program is written, semantics is what it means

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

Denotational semantics

A

A program’s meaning is given mathematically as a suitable mathematical structure

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

Typical problems in Computer Science

A

How can we write programs that don’t have bugs?
How do we store things and find things?
Is P equal to NP?
How do we make computers easily programmable?

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

What is key to problems in Computer Science?

A

Solutions to problems are constructive, we want methodologies (algorithms) that are general (for all inputs)
We want to be able to repeatedly apply solutions
The concern with measuring the difficulty of solving problems (big O etc.)

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

Important notions for solving problems

A

Computation (the machine that does the work)
Resources (time and memory taken)
Correctness (the quality and accuracy of the answer)

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

What is abstraction?

A

Hiding unnecessary information to make a problem easier to represent and solve

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

Abstraction vs models

A

Models have a time component

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

How would we abstract the internet?

A

As a collection of nodes, connected by channels along which they can send and receive messages
We can also associate a time with each channel

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

Travelling salesman’s problem

A

Calculating the shortest tour of a given collection of cities and finishing where you started
Core information: number of cities, start city, distances between cities

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

Offline vs online problems

A

Offline = know all the data in advance
Online = data keeps arriving

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

Map colouring problem

A

You have a plane map of regions, which either share a border, meet at a point, or don’t share a border
Can you colour the regions of the map with 3 colours so that if any two regions touch then they must be coloured differently

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

Applications of colouring

A

Scheduling jobs onto a CPU
Register allocation
Radio frequency assignment

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

Draughts problem

A

n by n board
Given a legal position of white and black checkers where it’s white’s turn, does black have a winning strategy

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

Informal definition of a decision problem

A

Consist of a set of instances
Each instance either corresponds to the answer “yes” or the answer “no”, and it’s our job to decide which one
We solve a decision problem by coming up with an algorithm to determine whether a given instances is a yes-instance or not

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

Formal definition of a decision problem

A

Consists of a set of instances I, and a subset Y of yes-instances
The no instances are I \ Y

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

How would we abstract the map-colouring problem?

A

Represent an instance of the problem as a graph G = (V, E) where V is a set of vertices (one for each region), and E is a set of pairs of vertices
(u, v) is only in E if region u touches region v
The problem is solved when each vertex in V is coloured and no pair in E contains two vertices of the same colour

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

How can the scheduling, register allocation and radio frequency assignment problems be represented as graph colouring problems?

A

If two tasks depend on each other and can’t run at the same time, represent them in a graph as nodes with an edge joining them and then colour the graph. Only tasks with the same colour can run at the same time.

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

Definition of a search problem

A

Consists of a set of instances I, set of solutions J, and a binary search relation that maps one instance to one solution. There can be any number of solutions corresponding to an instance

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

Solving a search problem

A

For an instance x in I, find a solution y in J such that (x, y) is in R, otherwise answer “no”

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

Decision problem vs search problem

A

For any decision problem, there is usually a search problem. For example, the search problem corresponding to the 3-colouring problem is actually finding a valid colouring.
There is always a decision problem corresponding to a search problem. The yes-instances are the instances which have a solution.

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

Optimisation problems

A

For every instance x in I, there is a set of feasible solutions f(x)
For every y in f(x) there is a value v(x, y) giving the measure of the solution
The goal is to find either the minimum or maximum v

26
Q

What is a greedy algorithm?

A

One that makes the locally best/most optimal choice at each stage

26
Q

Greedily colouring graphs by hand

A

Ranking colours from lowest to highest, and then going through the vertices in order, choosing the lowest colour possible. For every graph, there exists a way to number the vertices so that greedy colouring gives you the optimal result

27
Q

Non-greedy 4-colouring

A

Let v be a node with less than 4 edges. The graph can be 4-coloured if and only if the graph without v and its edges can be 4-coloured. Remove all the (edges of) vertices with less than 4 edges until you’re left with 4 vertices, which can trivially be coloured. You can now re-add all the vertices, and colouring them is now easy.

28
Q

Euclid’s algorithm

A

Calculates the greatest common factor of two integers m and n
if n == 0, output m
else:
set m’ = n and n’ = m mod n
set m = m’ and n = n’ and repeat the algorithm

29
Q

Formal methods vs software testing

A

Mathematically proving algorithms correct vs systematically trying many different types/groups of inputs until you’re confident the algorithm is correct

30
Q

Layers of abstractions in modern computer systems

A

Applications, algorithm, programming language, operating system, ISA, microarchitecture, gates/register level transfer, circuits, devices, physics

31
Q

Programming language vs algorithms

A

A program is written in a concrete, explicitly defined programming language, while algorithms have an infinite number of possible implementations as programs. Programming languages provide a means for translating an algorithm into a form suitable for execution by a computer.

32
Q

Imperative programming languages

A

Python, C, C++, Java
Statements change a program’s state, by changing values in memory

33
Q

Declarative languages (functional)

A

Programs are defined as mathematical functions

34
Q

Declarative languages (logic-based)

A

e.g. Prolog
Programs specify a logical solution

35
Q

Data-oriented languages

A

Programs work with data through manipulating and searching relations (tables)

36
Q

Scripting languages

A

Designed to automate frequently-performed tasks that involve calling or passing commands to external programs

37
Q

Assembly languages

A

Low-level languages providing the interface between machine code and a high-level programming language

38
Q

Concurrent languages

A

Provide facilities for concurrency (different threads, processes)

39
Q

Dataflow languages

A

Program specified by flows of data (visual)

40
Q

Fourth-generation languages

A

High-level languages built around databases

41
Q

List-based languages

A

Languages built around the list data structure (popular in the field of AI)

42
Q

What drives programming language design?

A

Productivity: Developing with Python is quicker than using C or C++
Security
Execution speed
Reliability: features to enhance error correction

43
Q

What attributes should programming languages have?

A

Easy to use, read, write, understand
Support abstraction
Support testing and debugging
Be inexpensive to maintain and use

44
Q

Problems with informal semantic understanding

A

How can we be sure that the program actually does what the programmer thinks it does?
How can we prove that the program does what it’s meant to do?
How can I be sure that my program executes identically when I run it on different machines?

45
Q

Denotational semantics

A

A program’s meaning is given mathematically as a mathematical structure such as a function or partial function

46
Q

Operational semantics (for languages like Python)

A

A program’s meaning is given in terms of the steps of a computation the program makes when it runs (e.g. changes in variables and memory)

47
Q

Axiomatic semantics (for logic-based languages)

A

A program’s meaning is given indirectly in terms of a collection of logical properties it satisfies and how those properties are maintained

48
Q

Compiled languages

A

All of the program is compiled into machine code to be run on a specific machine

49
Q

Interpreted languages

A

Only one instruction at a time is translated into machine code, and this happens while the program is running

50
Q

Compiled vs interpreted languages

A

Compiled programs: faster (time is spent optimising), avoids some runtime errors
Interpreted programs: Facilitate speed of development, tend to use memory better (less optimised for memory usage but the program doesn’t need to be stored in memory)

51
Q

What is bytecode?

A

Java programs are compiled into bytecode (intermediate code), and then translated by the Java Virtual Machine

52
Q

Just-In-Time compilation

A

Programs only “semi-compile”, often into bytecode, and are then fully compiled into machine code when run, optimising the use of run-time libraries

53
Q

What does the lexical analyser do?

A

Reads strings of symbols and converts them into tokens
This can account for more than 50% of the compile time.

54
Q

What does the syntax analyser/parser do?

A

Turns the token stream into a syntax tree (optimisation tends to happen here)

55
Q

What happens in the translation phase (for languages like Java)?

A

The tree is flattened into a sequence of intermediate code (e.g. Java bytecode)

56
Q

What happens during the code generation phase?

A

The tree (or intermediate code) is converted into assembly (optimisation tends to happen here)

57
Q

What counts as a regular expression over an alphabet consisting of the symbols (a, b, c)

A

The symbols, a, b or c by themselves
The empty set and the empty character
If i and j are regular expressions then so are:
- ij
- (i+j) (i or j)
- (i*) (zero or more)

58
Q

What does a regular expression do?

A

Denotes a set of strings over an alphabet

59
Q

Regular expression syntax

A

| = or

= or
* = zero or more
+ = one or more

60
Q

What is a finite state machine

A

A construct which has:
- A finite alphabet
- A finite set of states, with an initial state and final states
- Transition functions in the form q1 = delta(q0, a), which means that if you input “a” at q0 then you change state to q1

A finite state machine accepts a string when the sequence of states ends in a final state
A set of strings is denoted by a regular expression if and only if there’s a finite state machine that accepts it

Computational Thinking (4 decks)

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