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.

Binary Search

This exercise is part of my open university homework.

Presented with a brief introduction to the workings of binary search and five code snippets using Pascal, I had to figure out which of these fragments are correct implementations of the given search algorithm.

Binary Search - You're doing it wrong...

Based on the description and after a quick visit to Youtube, I came up with the following idea on how binary search works:

I created a sorted list in ascending order containing 10 random elements: 1, 34, 45, 50, 51, 60, 71, 75, 84 and 99. My search value was 84.

I determined the lists middle element (<list size> div 2) which is 5, and compared its value (50) with my search value. As 84 is greater than 50, I discarded all elements in the lists lower half including 50.

Based on the remaining lists upper half (60, 71, 75, 84 and 99) I kept repeating this halving process until the lists middle element matched the search value.

It took four iterations to find the value 84.

I was fine with my understanding of the algorithm until I ran the first sample implementation using my above list and search value as inputs. Instead of four iterations the program completed the search process taking only three iterations.

This is the given code snippets which...

...I embedded in a little program frame...

...and added some output... 

I was stuck for a while until I realized my faulty assumption: Making the list smaller and smaller each iteration. Implementing this "algorithm", I would either have to remove the discarded elements form the list or copy the remaining elements into a new list.

As my exercise did not mention neither option, this meant back to the drawing board.

Binary Search - You're doing it right...

This image shows the workings of the code snippet:

The field size remains of constant length 10.
The first element is (upperBound + lowerBound) div 2, (10 + 1) div 2 = 5.
As the search value is neither located at position 1 to 5, the implementation increases the value of loverBound by 1, 5 + 1 = 6. Again it calculates (upperBound + lowerBound) div 2, (10 + 6) div 2 = 8.
The value of the eighth element is 75.  As the search element is neither located at position 1 to 8, again the value of lowerBound is incremented by 1, 8 + 1 = 9. (10 + 9) div 2 = 9. The value of the ninth list element is 84, which matches our search value. This makes 3 iterations total.

Having a better understanding of how binary search works, I had a look at the other code snippets.

To determine wether the sample code is a valid implementation of binary search, I have to check if

• searching is performed according to the given algorithm
• it terminates properly in case the list contains the search value
• it terminates properly in case the list does not contain the search value
• it works properly on a list with length n
• it works properly on a list with length n + 1

The good, the bad....

As this post already became rather lengthy, I will limit myself to one good and one bad example.

Let's see how the first code snippet (shown above) overall performs:

	Match	No match
length n	x	x
length n + 1	x	x

This makes it a proper implementation of the binary search algorithm.

The second sample...

...produces the following results embedded in my little program frame:

	Match	No match
length n	x	-
length n + 1	x	-

In case the list contains the search value, it's found.
But in case the list does not contain the search value, the program does not even terminate.
What's wrong here?

Let's take my list of ten elements (1, 34, 45, 50, 51, 60, 71, 75, 84 and 99) and a search value which is not part of the list, 86.

The first step calculates the lists middle, (0 + 10) div 2 = 5, and compares 86 with the value of the fifth list element, which is 51. So far so good.
Now as the search value is greater than the 51, the value of lowerBound is set to the value of middle, 5. The value of found is false.
The next iteration again calculates the middle (10 + 5) div 2 = 7 and compares 86 with 71. The value of lowerBound becomes 7, and the loop body gets executed another time.
(10 + 7) div 2 = 8. 86 > 75? Yes. lowerBound 8.
(10 + 8) div 2 = 9. 86 > 84? Yes, lowerBound 9.
(10 + 9) div 2 = 9. 86 > 84? Yes, lowerBound 9.
(10 + 9) div 2 = 9. 86 > 84? Yes...................
(10 + 9) div 2 = 9. 86 > ..........................
(10 + 9) div 2 =...............................
................................................
........................................
..............................
.......................
..................
............
........
....
..
.

In case of 16-bit, the largest value for an integer is 215-1=32,767....Wait, what?

2¹⁵-1=32,767...

I signed up for an open university course about Imperative Programming using Pascal. Lecture 1 introduces the integer data type.

"In case of 16-bit, the largest value for an integer is 2¹⁵-1=32,767 (maxint)."

"The range of possible integer values is [-maxint - 1, maxint]." 

No further explanation given. I picked a couple of programming language books more or less randomly from my bookshelf to check if any of those do a better job at clarifying the upper and lower bounds of a given data type:

The Java Tutorial - A Short Course on the Basics

"The byte data type is an 8-bit signed two's complement integer. It has a minimum value of -128 and a maximum value of 127 (inclusive)." 

Programming Ruby

"Integers within a certain range (normally - 2³⁰ to 2³⁰ - 1 or -2⁶² to 2⁶² - 1) are held internally in binary form...."

Head First C#

"int is commonly used for whole numbers. It holds numbers up to 2,147,483,647."

You get the idea. Introduce a datatype. Mention the upper an lower bounds. Read, forget, look up again if ever necessary. No deeper understanding gained.

"Objective-C Programming The Big Nerd Ranch Guide" does a slightly better job:

"An unsigned 8-bit number can hold any integer from 0 to 255. Why? 2⁸ = 265 possible numbers. And we choose to start at 0."

"A signed 64-bit number can hold any integer from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. One bit for the sign leaves 2⁶³ = 9,223,372,036,854,775,808. There is only one zero."

As Big Nerd Ranch's book goes a bit deeper on the subject on how he upper and lower bounds of a datatype are determined based on the number of bits, I assume that I am not the only one out there who doesn't get this right away. I had to explain this to myself...

One more bit...

Let's see. I start simple with a single bit. Its value can be either 0 or 1.
This makes room for two decimal numbers (0, 1).

Binary	Decimal
0	0
1	1

I add one more bit.
With two bits it's enough space for four decimal numbers (0...3).

Binary	Decimal
00	0
01	1
10	2
11	3

And one more bit.
Three bits can store up to eight decimal numbers (0...7).

Binary	Decimal
000	0
001	1
010	2
011	3
100	4
101	5
110	6
111	7

As every additional bit doubles the amount of numbers that can be stored, this is a 2ⁿ relation.
2 for the number of possible values a bit can hold (either 0 or 1), n for the amount of available bits.

Upper and lower bounds...

Back to the original Pascal language example. The upper bound for an integer was given as 32,767 (maxint) in the courseware, the lower bound as -32,768 (-maxint - 1). Where do these values come from?

So far I was only looking at positive values including zero. 16 bits would make 2¹⁶ = 65,536.

What about negative values? The binary system allows the representation of negative (and positive) numbers without requiring additional symbols like "+" or "-". Instead the highest bit is used to indicate wether the number is either a positive or negative one (signed). The value of the highest bit is 0? We are dealing with zero or a positive number. The value of the highest bit is 1? Must be a negative number.

Examples:

• 0000000000000001: positive number with value 1. 
• 1000000000000000: negative number with value -1. 

Because in case of negative numbers the value of the highest bit is always set to 1, we have fifteen (16 - 1) remaining slots to fill. 2¹⁵ = 32,768.

This would cover the range of 0 to -32,767. As by definition zero is part of the positive numbers, we have one additional slot and can go from -1 to -32,768 (-32,767 - 1), which makes -32,768 the lowest number possible (minimum).

Same for positive numbers. The highest bit is occupied by 0. Fifteen remaining slots to fill as well. 2¹⁵ = 32768. This covers the range of 0 to 32767. Therefore 32767 is the highest number possible (maximum) as we must include the zero.

Positive numbers:

Binary	Decimal
0000000000000000	0
0000000000000001	1
...	...
0111111111111110	32,766
0111111111111111	32,767

Negative numbers:

Binary	Decimal
1000000000000000	-1
1000000000000001	-2
...	...
1111111111111110	-32,767
1111111111111111	-32,768