Fundamental Problems Flashcards
What are compiled languages?
The whole program is converted/compiled into machine code before being run, and only runs on a specific type of machine
What are interpreted languages?
An interpreter reads a small number of instructions at a time and translates them
Differences between compiled and interpreted languages
Compiled: Faster, code is analysed and optimised during compilation, avoids certain runtime errors
Interpreted: Better use of memory, easier to develop software with
How do bytecode languages such as Java work?
Programs are compiled into bytecode, which is higher level than machine code but still fast to interpret, and then translated by a virtual machine
Difference between syntax and semantics
Syntax is how a program is written, semantics is what it means
Denotational semantics
A program’s meaning is given mathematically as a suitable mathematical structure
Typical problems in Computer Science
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?
What is key to problems in Computer Science?
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.)
Important notions for solving problems
Computation (the machine that does the work)
Resources (time and memory taken)
Correctness (the quality and accuracy of the answer)
What is abstraction?
Hiding unnecessary information to make a problem easier to represent and solve
Abstraction vs models
Models have a time component
How would we abstract the internet?
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
Travelling salesman’s problem
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
Offline vs online problems
Offline = know all the data in advance
Online = data keeps arriving
Map colouring problem
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
Applications of colouring
Scheduling jobs onto a CPU
Register allocation
Radio frequency assignment
Draughts problem
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
Informal definition of a decision problem
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
Formal definition of a decision problem
Consists of a set of instances I, and a subset Y of yes-instances
The no instances are I \ Y
How would we abstract the map-colouring problem?
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 can the scheduling, register allocation and radio frequency assignment problems be represented as graph colouring problems?
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.
Definition of a search problem
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
Solving a search problem
For an instance x in I, find a solution y in J such that (x, y) is in R, otherwise answer “no”
Decision problem vs search problem
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.
Optimisation problems
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
What is a greedy algorithm?
One that makes the locally best/most optimal choice at each stage
Greedily colouring graphs by hand
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
Non-greedy 4-colouring
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.
Euclid’s algorithm
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
Formal methods vs software testing
Mathematically proving algorithms correct vs systematically trying many different types/groups of inputs until you’re confident the algorithm is correct
Layers of abstractions in modern computer systems
Applications, algorithm, programming language, operating system, ISA, microarchitecture, gates/register level transfer, circuits, devices, physics
Programming language vs algorithms
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.
Imperative programming languages
Python, C, C++, Java
Statements change a program’s state, by changing values in memory
Declarative languages (functional)
Programs are defined as mathematical functions
Declarative languages (logic-based)
e.g. Prolog
Programs specify a logical solution
Data-oriented languages
Programs work with data through manipulating and searching relations (tables)
Scripting languages
Designed to automate frequently-performed tasks that involve calling or passing commands to external programs
Assembly languages
Low-level languages providing the interface between machine code and a high-level programming language
Concurrent languages
Provide facilities for concurrency (different threads, processes)
Dataflow languages
Program specified by flows of data (visual)
Fourth-generation languages
High-level languages built around databases
List-based languages
Languages built around the list data structure (popular in the field of AI)
What drives programming language design?
Productivity: Developing with Python is quicker than using C or C++
Security
Execution speed
Reliability: features to enhance error correction
What attributes should programming languages have?
Easy to use, read, write, understand
Support abstraction
Support testing and debugging
Be inexpensive to maintain and use
Problems with informal semantic understanding
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?
Denotational semantics
A program’s meaning is given mathematically as a mathematical structure such as a function or partial function
Operational semantics (for languages like Python)
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)
Axiomatic semantics (for logic-based languages)
A program’s meaning is given indirectly in terms of a collection of logical properties it satisfies and how those properties are maintained
Compiled languages
All of the program is compiled into machine code to be run on a specific machine
Interpreted languages
Only one instruction at a time is translated into machine code, and this happens while the program is running
Compiled vs interpreted languages
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)
What is bytecode?
Java programs are compiled into bytecode (intermediate code), and then translated by the Java Virtual Machine
Just-In-Time compilation
Programs only “semi-compile”, often into bytecode, and are then fully compiled into machine code when run, optimising the use of run-time libraries
What does the lexical analyser do?
Reads strings of symbols and converts them into tokens
This can account for more than 50% of the compile time.
What does the syntax analyser/parser do?
Turns the token stream into a syntax tree (optimisation tends to happen here)
What happens in the translation phase (for languages like Java)?
The tree is flattened into a sequence of intermediate code (e.g. Java bytecode)
What happens during the code generation phase?
The tree (or intermediate code) is converted into assembly (optimisation tends to happen here)
What counts as a regular expression over an alphabet consisting of the symbols (a, b, c)
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)
What does a regular expression do?
Denotes a set of strings over an alphabet
Regular expression syntax
| = or
= or
* = zero or more
+ = one or more
What is a finite state machine
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
