[MUSIC] The second introductory lesson deals with the representation of algorithms. The specification of digital systems by means of algorithms is a central aspect of our course, and many times in order to define algorithms we will use sequences of instructions very similar to programming language instructions. So, if you already know some programming language such as C or Java the contents of this lesson will sound to you very familiar. An algorithm is a sequence of operations whose objective is the solution of some problem, for example a complex computation or the control of some process. For example, in the preceding lesson about numeration systems we described addition and difference algorithms with binary numbers. The result of an algorithm execution must be independent of the chosen type of algorithm representation. Some common representation methods are: natural language, flow diagrams, programming languages, and also something not so well defined called pseudocode. It is similar to a programming language but more informal. It uses a mix of natural language sentences, of programming language instructions, and also of some key words that define basic structures. Two important aspects of programming languages, and thus also of pseudocode are: the available operations and the control structures. Many times, all along our course, assignment instructions will be represented in this form, similar to an arrow. Given variables x, y and z, this kind of assignment means that x receives the value 15 and this one means that the current value of x is replaced by the result of computing 2x plus y plus z. This symbol corresponds to the simple "equal to" symbol in C. We use this other symbol because it is the signal assignment symbol in VHDL, the hardware description language used in this course. The comparison operators are the classical ones, smaller than, greater than, equal to, smaller than or equal to, greater than or equal to, and different from. Sometimes logical operators will be used. For example, within a condition we could write something like if x is even and x is greater than or equal to 8, then (execute) some operations. This means that x belongs to the set 8, 10, 12, 14, and so on. Another logic operator, apart from AND and OR is NOT. An example: "x is even" is the same as NOT "x is odd". The arithmetic operators are the classical ones: sum, difference, product and division. Now some comments about control structures. We will use selection or branching instructions such as this one. If some condition holds then the sequence of actions. The corresponding diagram is this one. Or, if some condition holds then the first sequence of actions, else another sequence of actions. Another example. This one: if a first condition holds, then some action or sequence of actions, else if the second condition holds, then another action or another sequence of actions. Another way to define the selections is the case statement. Assume that variable x can take four values called value1, value2, value3 and value4. Then sequences of actions can be selected in function of the value of x. In the case that x is equal to value1, then some action or some sequence of actions. In the case that x is equal to some value2 then another action and so on with value3 and value4. Let us see some examples. Assume that you must compute y equal to x divided by 2 but rounded, so that the result is an integer, and that you round towards 0. That means that if x is positive, then y will be the greatest integer smaller than or equal to x divided by 2. And if x is negative, then y is equal to the smallest integer greater than or equal to x divided by 2. I mean that if x is equal to 10 then y would be equal to 5. If it is equal to minus 10, minus 5. If x is equal to, let us say, 7, then y will be equal to 3. Observe that 3 is 7 minus 1 divided by 2. But if x is equal to minus 7, the result must be minus 3, and observe that -3 is -7 plus 11 divided by 2. So that the algorithm could be the following one: if x is even, then y is x divided by 2; else (so x is odd) and if furthermore x is negative, then (as in the second case) y must be equal to x plus 1 divided by 2; and in the third case, y will be equal to x minus 1 divided by 2. End if. This is a first example of an algorithm with some branching. Let us see a second example. Assume that x is a decimal digit, and that you want to generate the binary representation of x. Then a simple table could be defined as follows with a case statement: case x is, then all the cases are when 0 then y will be equal to 0000, when x is equal to 1 then y will be equal to 0001, and so on, up to when 9 then y will be equal to 1001, and that's it; end case. Another important type of control structure is Iteration. Here we see two examples: the While loop and the For loop. While loop, whose structure is: while some condition holds then execute the sequence of actions, and the diagram is this one. Another example, for - here is the name of some variable - in some range between min and max, then a loop that includes a set of instructions. Let us see an example: assume that you have defined previously. vector A, with let us say, 8 components, a(0), a(1), and so on up to a(7), and another vector x, also with 8 components or numbers, integers for example, and you want to compute y equal to a0 times x0, plus a1 times x1, plus ··· and so on up to a7 time x7. Then you could define the following algorithm: an accumulator variable acc, initially equal to 0 and then a loop for i in range 0 to 7. Loop, acc replaced by the previous value of acc plus the product ai times xi. And that's all; end loop. So, this algorithm computes this expression. A last type of language instruction that we will use in our course is the call to procedures. A procedure, also called a subroutine, is a piece of program, a sequence of instructions, with operations and control structures, that execute some algorithm. Then, a name and a set of parameters, are associated to every procedure, and a procedures can be called, one of several times, within the main program, and when called, values are given to each parameter. Let us see an example: assume that we want to compute z equal to a times the square root of x plus b times the square root of y. Then, first, we could define another algorithm that computes the square root of a number with an accuracy of n digits, for example, and encapsulate this algorithm within the procedure "square root". So we will define procedure "square root", with parameters x, y and n, is and then a set of instructions that compute y equal to the square root of x with n fractionary digits, and "end procedure" or "end square root". Then the main algorithm will be the following. Square root. We make a call to the square_root procedure, with parameters x, a new variable u, and, for example, 16. This will compute u equal to the square root of x with 16 fractionary digits. After we replace u by the product of a by u, so that u will be equal to a times the square root of x. After that we call, again, the square root procedure but in this case with other parameter (y,v,16) so that v now is equal to the square root of y with 16 fractionary digits. Next instruction: we substitute v by b times v, so that now v is equal to b times the square root of y, and finally we compute the sum of u and v. So, as you can see, we have called two times the procedure "square root". Summary: In this lesson we have presented an algorithm representation language: the pseudocode, and have define operations and control structures.
