## Footnotes: Computer science

### Instance of a problem

An instance of a computational problem is a particular case of the problem, with specific values of the parameters (i.e., input data) of the problem.  Each set of values of the parameters defines an instance.

Consider, for example, the following problem: given numbers a, b, and c, find a number x such that ax2 + bx + c = 0.  (The numbers a, b, and c are the parameters of the problem.)  One instance of this problem consists of finding x such that 1x2 + 1x − 2 = 0.  Another instance consists of finding x such that 1x2 − 2x + 1 = 0.  Yet another instance asks for x such that 123x2 − 456x + 789 = 0.

### Solution of an instance of a problem

A solution of an instance of a computational problem is any object that satisfies the statement of the problem instance. Take, for example, the problem in the previous note; then

• the number 1 is a solution of the instance (a = 1, b = 1, c = −2) of the problem; another solution of the same instance is the number −2;
• the number 1 is the only solution of the instance (a = 1, b = −2, c = 1) of the problem;
• the instance (a = 1, b = 0, c = 1) of the problem has no solution at all (assuming that the problem requires x to be real).

A solution of a problem is an algorithm that solves the problem. In other words, for any values of the parameters, the algorithm produces a solution of the corresponding instance (or signals that the instance has no solution).  For the problem stated above, an algorithm can be summarized by the formula (−b ± √b² − 4ac) / 2a.

### Correct algorithm

An algorithm is correct if it solves the problem that it is supposed to solve.

### Elegant algorithm

Elegant is more or less the same as simple, clean, beautiful, economical.  An elegant algorithm (or program) has no superfluous code and no unnecessary variables.  An elegant algorithm does not treat special instances of the problem in separate.

A very clever, intricate, convoluted, tangled, ugly algorithm is inelegant.

Experience shows that elegante algorithms tend to be efficient, and efficient algorithms are usually elegant.  In addition, elegant iterative processes have simpler invariants.

### Efficient algorithm

An algorithm is efficient if does not waste time.  Roughly speaking, an algorithm is efficient if it is faster than others algorithms for the same problem.

Though this definition is adequate for informal use, it hides some difficulties:

1. The expression faster than others should include not only the already known algorithms for the problem, but also the ones not yet discovered.
2. Given two algorithms for the same problem, one can be faster than the other for some instances of the problem and slower for other instances. To characterize efficiency, the larger instances are the most relevant.
3. Other computational resources besides time (such as memory space, for example) could be taken into account to define efficiency.

We could say, very roughly, that to be efficient is to do more with less.

The following definitions refer to the time consumption (i.e., the response time) of algorithms.  In all the definitions,  n  is the size of an instance of the problem that the algorithm solves, i.e., n is the size of the input to the algorithm.  (If the input is a graph, for example, then n is the the number of vertices plus the number of edges of the graph.)

An algorithm is

1. constant if its time consumption does not depend on n,
2. logarithmic if it consumes time proportional to  log n,
3. linear if it consumes time proportional to  n,
4. linearithmic (or n-log-n) if it consumes time proportional to  n log n,
5. quadratic if it consumes time proportional to  n²,
6. cubic if it consumes time proportional to  n³,
7. exponential if it consumes time proportional to  cn, where c is a constant (like 2, for example).

These terms refer, usually, to the time consumption in the worst case.

### Data types

A data type is a set of values equipped with a set of operations. Some operations transform values into other values; others associate numbers to values or sets of values.  Here are some basic data types:

• The set of values of type  int  is  INT_MIN, … , −2, −1, 0, 1, 2, … , INT_MAX.   The values of the constants INT_MIN and INT_MAX are set in the limits.h library interface.

The operations on these values are the comparisons  ( <, <=, ==, >>= )  and the arithmetic operations  ( +, -, */ ).  Each arithmetic operation receives two ints and returns an int. The definitions of these operations are a little different from the ones used in mathematics, since we can have overflow in some cases and truncation in others.  For example, the value of  9 / 2  is 4 (not 4.5).  Another example: if INT_MIN and INT_MAX are −32768 and +32767 then  32767 + 1  is −32768, not 32768.

• The set of values of type  char  is  −128, −127, … , +126, +127.

The usual operations on these values are indicated by  <, <=, ==, >, >=, + and -.  In an ideal implementation of the data type, the value of the expression  127 + 2  would be  −127  rather than  129.  In C, however, the value of the expression x + y below is 129, since the expression is evaluated in int arithmetic.

```char x, y, z;
x = 127;  y = 2;
z = x + y; // the value of z is -127
```
• The set of values of the type  unsigned char  is  0, 1, … , 254, 255.
• The set of values of type  double  (that corresponds to the real numbers) is more difficult to describe.

You can define your own data types using typedef.  The following data type, for example, is a useful representation of boolean values:

```typedef enum {FALSE, TRUE} boolean;
```

(An alternative data type is defined in the stdbool.h interface.)   Another useful data type is  string  (a sequence of bytes):

```typedef char *string;
```

Here is a more specialized example: the data type  point  represents the coordinates of a point on the plane:

```typedef struct {
double x;
double y;
} point;
```

The operations on values of this type are derived from the operations on doubles. You can also add your own operations, like the operation that produces the Euclidean distance between two points, for example.

### Real numbers and real numbers

Computers are not aware of real numbers in the mathematical sense. Computers only know a small set of rational numbers.

The world of computing calls reals the numbers of type float and double  (such as 0.31415926×101), represented in floating point notation. All these numbers are rational.

### Priority queue

A priority queue is any data type equipped with two operations:

• remove an element of largest value;

It is easy to implement a priority queue in such a way than one of the operations is fast.  It is more challenging to come up with an implementation in which both operations are fast.

The definition just given is that of a max priority queue. It is not difficult to adapt the definition to that of a min priority queue.

### Heap

Do not mistake the heap data structure with the area of the computer memory used for dynamic memory allocation.  The two concepts are independent.

### Binary, octal, and hexadecimal notations

Natural numbers can be written in binary (base 2) notation, octal (base 8) notation, decimal (base 10) notation, and hexadecimal (base 16) notation.

In binary notation, the digits are 0 and 1.  In octal notation, the digits are 0 1 .. 7.  In decimal, the digits are 0 1 .. 9. And in hexadecimal, the digits are 0 1 .. 9 A B .. F.

For example, the number seventy-nine is represented by  79  in decimal notation since seventy-nine is 7×10 + 9.  The same number is represented by  1001111  in binary notation, since seventy-nine is equal to 1×26 + 1×23 + 1×22 + 1×21 + 1×20.  The same number is represented by  117  in octal notation (since seventy-nine is equal to 1×8² + 1×8¹ + 7), and by  4F  in hexadecimal notation (since seventy-nine is equal to 4×16¹ + F).

The C language uses the following convention:

• in decimal notation, the first digit is different from 0,
• in octal notation, the first digit is 0,
• in binary notation, the first two characters are 0b,
• in hexadecimal notation, the first two characters are 0x.

For example,  0117  is the octal representation and  0x4F  is the hexadecimal representation of seventy-nine.

### Letters with diacritical marks

Diacritics are the marks over letters (like á, ã, é, ñ, etc.) and the cedilla under a c.

The C99 standard of the C language allows letters with diacritics in names of variables and functions.  But the letters with diacritics must be represented (in the source file of your program) by means of its Unicode numbers. For example, if you wish the name of a variable to be piñacolada, you must type pi\u00F1acolada.  This complication makes the resource somewhat useless in practice…

In the case of character constants, however, the things are more friendly: letters with diacritics can be typed in directly (provided your languages environment is appropriate).  For example,

```int pinacolada = 0; // piñacolada
char message[14] = "values in €";
printf( "%s\n", message);
```

produces

```values in €
```

(Note that the string "values in €" occupies 14 bytes since uses 3 bytes in UTF-8 encoding.)

### ISO-LATIN-1 table

Until about 2004, the bytes 10000000 to 11111111 were used to represent letters with diacritics and some others characters.  This correspondence is defined by the ISO-LATIN-1 table, also known as ISO-8859-1 table.

With the popularization of the UTF-8 code, the ISO-LATIN-1 table was deprecated. Hence, the bytes whose first bit is 1 (unsigned chars 128 to 255) no longer represent characters.

### The structure of the UTF-8 code

The UTF-8 code represents each character by a sequence of 1 to 4 bytes.  The coding scheme was carefully designed to allow for the unambiguous decoding of a sequence of bytes and to be compatible with the ASCII code.

The first 128 characters on the Unicode list (numbers U+0000 to U+007F) are represented by 1 byte each.  The 1920 next characters (numbers U+0080 to U+07FF) are encoded in 2 bytes.  And so on.

The table below shows the UTF-8 code structure. In the left column, we have the intervals of Unicode numbers, in hexadecimal notation. In the right column, in binary notation, the intervals of the corresponding code bytes:

```Unicode numbers      byte 1   byte 2   byte 3   byte 4

00000000 .. 0000007F 0xxxxxxx
00000080 .. 000007FF 110xxxxx 10xxxxxx
00000800 .. 0000FFFF 1110xxxx 10xxxxxx 10xxxxxx
00010000 .. 0010FFFF 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
```

Now, the same table written in decimal notation:

```       0 .. 127      000..127
128 .. 2047     192..223 128..191
2048 .. 65535    224..239 128..191 128..191
65536 .. 1114111  240..247 128..191 128..191 128..191
```

Finally, the same table written in hexadecimal notation:

```       0 .. 7F       00..7F
80 .. 7FF      C0..DF   80..BF
800 .. FFFF     E0..EF   80..BF   80..BF
10000 .. 10FFFF   F0..F7   80..BF   80..BF   80..BF
```

### Well-formed expression of parentheses and brackets

First, a very rough draft of the algorithm:

```// This function decides whether a string s contains a
// well-formed sequence of parentheses and brackets.

wellformed (string s) {
for each element c of s do {
if c ≡ ')' then
if top of stack has '(' then
pop stack
else if c ≡ ']' then
if top of stack has '[' then
pop stack
else push c on stack
}
if stack empty
then return yes
else return no
}
```

Now, a draft that is closer to actual code:

```wellformed (string s) {
allocate space for a stack of bytes
for each byte c in s do {
if c ≡ ')' then
if stack nonempty and top of stack is '(' then
pop
else return no
else if c ≡ ']' then
if stack nonempty and top of stack is '[' then
pop
else return no
else push c
}
if stack empty
then return yes
else return no
}
```

### Transforming an infix expression into postfix

Here is a rough pseudocode draft in of the infixToPostfix function:

```// This function receives an infix expression inf
// and returns the corresponding postfix expression.

infixToPostfix (string inf) {
for each character c of inf do {
depending on the value of c
push c onto stack
or add c to the postfix expression
or transfer characters from stack to postfix
}
add '\0' to the postfix expression
return postfix
}
```

Now, a more precise and complete draft:

```infixToPostfix (string inf) {
allocate space for postfix string post
allocate space for stack of bytes
// first byte of inf is a '('
push first byte of inf onto stack
for each byte c of inf do {
if c ≡ '(' then
push c
else if c ≡ ')' then
while top of stack is different from '('
pop x
put x in post
pop x
else if c is '+' or '-' then
while top of stack is different from '('
pop x
put x in post
push c
else if c is '*' or '/' then
while top of stack is neither '(' nor '+' nor '-'
pop x
put x in post
push c
else
put c in post
}
put '\0' in post
return post
}
```

### Distances between cities

Here is um draft of the distances algorithm:

```// Receives matrix A of interconnections
// between 6 cities. Returns array d such that
// d[i] is the distance from city c to city i.

distances (matrix A[0..5][0..5], int c) {
d[c] = 0
put c into the queue

while queue is not empty {
let i be the first city in the queue
for each neighbor j of i do
if d[j] not yet defined then
d[j] = d[i] + 1
put j into queue
remove i from queue
}

return d
}
```

### Sieve for the Heapsort algorithm

Here is a draft, in pseudocode, of the sieve function:

```sieve (array v[1..m]) {
p = 1
while 2p ≤ m do
let c be the most valuable child of p
if v[p] ≥ v[c] then stop
else interchange v[p] and v[c]
else p = c   // p moves down the heap
}
```

### Heapsort

Here is a draft, in pseudocode, of the heapsort function:

```// Rearranges v[1..n] in increasing order.

heapsort (v[1..n]) {
transform v[1..n] into a heap
for m = n, n−1, ... , 2 do
interchange v[1] and v[m]
sieve (v[1..m-1])
}
```

### Problem solving

Problem-solving skills are almost unanimously
the most important qualification
that employers look for […]
more than programming languages proficiency,
debugging, and system design.

What should you do when you need to invent an algorithm for a new computational problem?

1. Before trying to solve the problem, understand very well the nature of the data for the problem.  Does the data consist of a list of numbers? a single number? a sequence of characters? a graph? a matrix?  Are the numbers integer or fractional? are they all positive? are they pairwise distinct or there may be repetitions?
2. Understand very well the nature of the solutions of the instances of the problem.  Does a solution consist of a single number? a list of numbers? a matrix? a list of characters? a graph?  Does every instance of the problem have a solution?
3. Spend all the time you need to understand the relation between the data and a solution of the corresponding instance.  You must be able to describe an algorithm that receives the data together with a candidate solution and decides whether the candidate is indeed a solution.

To properly understand the problem, write its statement on a piece of papel, draw a diagram, explain the problem to a colleague.  Try to solve some simple instances of the problem. Try to solve extreme instances, like the very small and the ones that have no solution.

4. Resist the temptation to begin writing code immediately. Do a little bit of planning before you start to program.  If you start programming too soon, you may not seeing the forest for the trees.

(This note was inspired in the article How to think like a programmer — lessons in problem solving, by Richard Reis.)