Enter the matrix

Given the following definitions...

const
  SIZE = 5;
  type
  tMatrix = array [1..SIZE,1..SIZE] of integer;

  var
  A : tMatrix;
  temp,
  i,
  j : integer;

...and some code to read the matrix values from the command line...

{ read the matrix values for A: }
  for i := 1 to SIZE do
    for j := 1 to SIZE do
      readln (A[i,j]);

...which of the following code snippets transforms this matrix...

...into...

?

[A] begin
        for i := 1 to SIZE-1 do
          for j := i+1 to SIZE do
          begin
            temp := A[i,j];
            A[i,j] := A[j,i];
            A[j,i] := temp
          end
        end;

Outer for-loop i = 1 and inner for-loop j = 2, j = 3, j = 4 and j = 5

Outer for-loop i = 2 and inner for-loop j = 3, j = 4 and j = 5

Outer for-loop i = 3 and inner for-loop j = 4 and j = 5

Outer for-loop i = 4 inner for-loop j = 5

Done. Correct transformation.

[B] begin
        for i := 1 to SIZE do
          for j := 1 to i do
          begin
            temp := A[i,j];
            A[i,j] := A[j,i];
            A[j,i] := temp
          end
        end;

Outer for-loop i = 1, inner for-loop j = 1
Outer for-loop i = 2, inner for-loop j = 1 and j = 2
Outer for-loop i = 3, inner for-loop j = 1, j = 2 and j = 3
Outer for-loop i = 4, inner for-loop j = 1, j = 2, j = 3 and j = 4
Outer for-loop i = 5, inner for-loop j = 1, j = 2, j = 3, j = 4 and j = 5

This algorithm basically does the same as the algorithm of option A.
In addition it also touches the elements at position A[1, 1], A[2, 2], A[3, 3]... and replaces those elements with themselves.

Correct but slower than the algorithm of option A.

[C] begin
        for i := 1 to SIZE do
          for j := 1 to SIZE do
          begin
            temp := A[i,j];
            A[i,j] := A[j,i];
            A[j,i] := temp
          end
        end;

Looks similar to the algorithm of option B with one subtle difference:
"for j := 1 to SIZE do" instead of "for j := 1 to i do"

Outer for-loop i = 1, inner for-loop j = 1, j = 2, j = 3, j = 4 and j = 5
So far so good. All elements in the first row changed places with the elements in the first column.

Outer for-loop i = 2, inner for-loop j = 1, j = 2, j = 3, j = 4 and j = 5

That's where the algorithm fails. The algorithm already touched the element A[2, 1] to replace it with element A[1, 2]. Now it replaces those elements again.

[D] begin
        for i := 1 to SIZE do
          for j := 1 to SIZE-i do
          begin
            temp := A[i,j];
            A[i,j] := A[j,i];
            A[j,i] := temp
          end
        end;

Basically the same error as the algorithm of option C. Elements that already changed places, change places again.
In addition, "for j := 1 to SIZE-i do" causes the algorithm to touch less and less columns as the value of the row count i increases.

[E] begin
        for i := 1 to SIZE-1 do
          for j := i+1 to SIZE do
          begin
            temp := A[i,j];
             A[j,i] := A[i,j];
             A[j,i] := temp
           end
         end;

This one cannot work.
The assigned value of variable temp is A[i,j].
Next, the value of A[i,j] is assigned to A[j,i], which is the same value as temp.
In the end value of temp is assigned to A[j,i], a value it already holds.
A[i,j] never gets a new value though.

Out of bounds

 function max (
               ParField: tField;
               lowerBound, upperBound: tIndex): integer;
    var
      Value : integer;
      i : tIndex;
    begin
      Value := ParField[lowerBound];
      for i := lowerBound + 1 to upperBound do
        if ParField[i] > Value then
          Value := ParField[i];
      max := Value
    end; { max }

This function walks through a list of integers starting at and up to a given index and determines the largest number within that range.

Given the the following definitions...

const
BOUNDARY = 10;
type    
tIndex = 1..BOUNDARY;
tField = array [tIndex] of integer;
var
Field : tField;
w,
w1,
w2 : integer;

...which of the following code snippets (calling the function) will not violate the lists boundaries, regardless the lists actual integer values. For example, a violation would occur when trying to access the lists 12th element, as the list by definition only consists of ten slots.

[A] w := max (Field, Field[1], Field[BOUNDARY]);

The point to note here is "regardless the actual list values". The value of Field[1] can be anything, 1, 10, 1000...
Any value that is not within the range of 1..10 will cause a violation.

[B] w := max (Field, (BOUNDARY-1) div 2, (BOUNDARY-1) div 2);

The lower an upper bound are related to BOUNDARY and not to actual list values.
Accessing a list element at (BOUNDARY-1) div 2, which is 4, will do no harm.

[C] if max (Field, 1, (BOUNDARY-1) div 2) >
      max (Field, (BOUNDARY+1) div 2, BOUNDARY) then
          w := max (Field, 1, (BOUNDARY-1) div 2)
      else
          w := max (Field, (BOUNDARY +1) div 2, BOUNDARY);

max (Field, 1, (BOUNDARY-1) div 2) does not violate the lists boundaries.
Neither does max (Field, (BOUNDARY+1) div 2, BOUNDARY).
Regardless of the actual outcome of the > - comparison either
w := max (Field, 1, (BOUNDARY-1) div 2)
or
w := max (Field, (BOUNDARY +1) div 2, BOUNDARY)
will be executed.
As both function calls do not violate the lists boundaries, this option is valid.

[D] w := max (Feld, 1, GRENZE);
       if w <= GRENZE then
           write (max (Feld, w, w));

The upper bound is not an issue in this case but the lower bound is. In case the value of w is less than 1, the lists lower boundary is violated.

[E] w1 := max (Field, 1, GRENZE);
      w2 := max (Field, 4, GRENZE-1);
      if (0 < w2) and (w1 <= GRENZE) then
      begin
          w := max (Field, 2, GRENZE);
          w := max (Field, 1, w)
     end;

This one is OK as well.

w1 can be of any value. w2 as well.
But for the conditional statement to be true, w2 has to be greater than 0 and w1 has to be less than or equal to 10.
There is no way that max (Field, 2, GRENZE); results in a value w that violates the lists boundaries in the following statement w := max (Field, 1, w).
w1 is the lists largest integer (position 1 to 10).
w (position 2 to 10) can only be equal or less than w1.

What happens? From decimal to binary...

program WhatHappens(input, output);
var
    a, b, c: Integer;
begin
    b := 0;
    c := 1;
    readln(a);
    while a > 0 do
    begin
        b := b+c*(a mod 2);
        a := a div 2;
        c := c*10;
    end;
    writeln(b)
end.

This little program converts a decimal number to its binary representation.

Let's have a look at the algorithm.

An integer a is read from the command line.
Let's suppose the user entered the number 7.

Every iteration the value of the variable a is divided by two (7, 3, 1, 0) as long as it is greater than 0 and the value of c is incremented by ten.

What about b, the binary representation of the entered decimal number.

Asking Google how to convert a decimal number into its binary representation that's what I found:

"Converting decimal numbers to binaries is nearly as simple: just divide by 2. [...] To do this conversion, I need to divide repeatedly by 2, keeping track of the remainders as I go."

The given example converts decimal 357 into 101100101 binary:

357 / 2 = 178 (Remainder: 1)
178 / 2 = 89 (Remainder: 0)
89 / 2 = 44 (Remainder: 1)
44 / 2 = 22 (Remainder: 0)
22 / 2 = 11 (Remainder: 0)
11 / 2 = 5 (Remainder: 1)
5 / 2 = 2 (Remainder: 1)
2 / 2 = 1 (Remainder: 0)
1 / 2 = (Remainder: 1)

Written from bottom to top...

1 / 2 = (Remainder: 1)
2 / 2 = 1 (Remainder: 0)
5 / 2 = 2 (Remainder: 1)
11 / 2 = 5 (Remainder: 1)
22 / 2 = 11 (Remainder: 0)
44 / 2 = 22 (Remainder: 0)
89 / 2 = 44 (Remainder: 1)
178 / 2 = 89 (Remainder: 0)
357 / 2 = 178 (Remainder: 1)

...the "sum" of the remainders is the binary value 101100101 of 357.

This looks familiar to the given algorithm.

a is divided by two...check.
a mod 2 is the remainder...check.
b keeps track of the remainders...check.
c takes care of the position (1, 10, 100, 1000) within the remainder's "sum"...check.

Back to the conversion of decimal 7 to 111 binary:
First iteration: remainder is 1 (7 mod 2), times 1 (initial value of variable c), plus 0 (initial value of variable b); result 1
Second iteration: remainder is 1 (3 mod 2), times 10 (c got multiplied by 10), plus the remainder from iteration 1, which is 1; result 11
Third iteration: remainder is 1 (1 mod 2), times 100 (c got multiplied by 10 again), plus the remainder from iteration 2, which is 11; result 111

The value of b is therefore built starting with the last digit of the binary representation and then working its way left to the first digit.

Merge

Write a program, that merges two sorted fields (in ascending order) holding integer values.

Possible duplicates shall be part of the result set.
An algorithm has to be added to a given code frame.

This is the complete code:

And this is how the algorithm works:

Given three lists.
List one with five elements 1, 2, 4, 6 and 9.
List two with eight elements 1, 3, 5, 6, 7, 8, 9 and 10.
List three, the result list, with thirteen empty slots.

Each list has its own counter, starting at position 1.

We compare the first element in list one with the first element in list two.
In case the element of list one is less then element of list two, it is added to the result list. Otherwise the first element of list two is added.
1 (list one) < 1 (list two)? Nope. We add the value 1 of list two to the result list.

As we already dealt with the first element of list two, we increase the position counter of list two by 1.
As the results list now holds one element, we increase its position counter by 1 as well.
List one remains untouched.

Next we compare the first element of list one with the second element of list two.
1 < 3? Yes. The element of list one is added to the result list.

The result list now holds two elements (1 and 1),  again we increase its counter.
We increase the counter of list one as well.
The position counter of list two remains untouched this time.

We keep repeating this process until either list one or list two runs out of elements.
In our example list one is the first list to run out. 9 is the last value taken from the list.

The last step is to iterate over the remaining list and add its elements to the result list.

Largest number

Write a program Max, that determines and returns the largest number in a set of integer values entered by the user. 0 signals the end of the user's input.

There is more than one road that leads to rome...

Money split

Write a little Pascal program that reads an amount of money between 0 and 99 euro cents and splits this amount into parts as few as possible.

Fahrenheit to Celsius

A classic. Write a little Pascal program that reads Fahrenheit and writes Celsius.

Boolean statements

Given variables a, b, c, d, e, f and g of type integer.

Which of the following  expressions are equal to:

if (a < b) and (c < d) then

    e := f

else

    e := g;

Only in case a is less than b AND c is less than d, and only then, e takes the value of f. Otherwise e takes the value of g.

[A]

e := f;

if not (a < b) then

    e := g;

if not (c < d) then

    e := g;

This can be changed to...

if not (a < b) or not (c < d) then

    e := g

else

    e := f;

...or...

if (a >= b) or (c >= d) then

    e := g

else

    e := f;

...which is option [B].

f is assigned to e only in case a < b and c < d. Otherwise e gets the value of g.

Therefore equal to the given term.  

[B]

if (a >= b) or (c >= d) then

    e := g

else

    e := f;

See option [A].

[C]

e := g;

if a < b then

    e := f;

if c < d then

    e := f;

Not equal. f is assigned to e in case a is less than b OR c is less than d.

if (a < b) or (c < d) then

    e := f

else

    e := g;

[D]

if a < b then

    if c < d then

        e := f

    else

        e := g;

Not equal. What value is assigned to e in case a >= b?

[E]

e := g;

if not (a >= b) then

    e := f;

if c < d then

    e := f;

Not equal.

if not (a >= b) can be changed to if a < b.

e := g;

if a < b then

    e := f;

if c < d then

    e := f;

Same as option [C].

Data types and operators

Two variables given, b of type boolean and i of type integer. Which of the following statements are correct?

[A] b and (i > 0)

Correct.

[B] i > 0 and b 

"0 and b" binds before "i >". "and" requires operands of type boolean.
(i > 0) and b would be correct.

[C] i / 3

Correct. But why?
The standard operators to be used with integers are +, -, *, div and mod.

What about /, which is part of the operators to be used with the data type real?

It looks like the operator can be used with integers as well. 

Use operands of type integer with / and you will get a result of type real.

[D] (i > 0) or b = false

Correct. 

i > 0: boolean

(i > 0) or b: boolean

[E] i div 3.0

div requires operands of type integer.

Which of the following identifiers can be used as a variable name?

Which of the  following identifiers can be used as a variable name?

Letters:

A   B   C   D   E   F   G   H   I   J   K   L   M

N   O   P   Q   R   S   T   U   V   W   X   Y   Z

a   b   c   d   e   f   g   h   i   j   k   l   m

n   o   p   q   r   s   t   u   v   w   x   y   z

Digits:

0   1   2   3   4   5   6   7   8   9

[A] Sample_Program

Underscore is not a letter.

[B] Variable

Valid.

[C] <Counter>     

Identifiers must not contain any special symbols.

Special symbols:

+   -   *   /
.   ,   :   ;
=   <>   <   <=   >   >=
:=   ..   ^   '
(   )   [   ]   {   }

[D] TYPE

No reserved words.

Reserved words:
and   array   begin   case   const   div   do
downto   else   end   file   for   function
goto   if   in   label   mod   nil   not   of   or
packed   procedure   program   record   repeat
set   then   to   type   until   var   while   with

[E] über

Umlauts are not letters.

Open University Homework

I decided to put my open university homework online.

Working on the problem sets in solitary only takes me so far.

What I am expecting to get out of this regiment:

• gaining a deeper understanding of what I am doing here
• clearer and more focussed thought process to bring the mess in my head to "paper"
• nice notes for studying and revising

Regardless of the length or difficulty, each blog post will be dedicated to exactly one problem.

Otherwise I will end up with very long posts that do not have a common topic besides belonging to the same set of questions.