UIT2201: CS & the IT Revolution

Supplementary Help Exercises on Algorithms

What: More Exercises on Algorithms
Who: Meant for Beginners to Algorithms
When: As soon as possible
Where: Anywhere and anytime you have space

For those who are finding algorithms to be difficult, I am including more examples of algorithms for you to go through and learn --- much like any beginner learn through lots and lots of practice. I suggest that you try all of these exercises so that you will get the hang of it and you are comfortable with simple algorithms.

Alg-PP1: [Loop and Array]
Algorithm to read in a number N, and then read in the numbers A[1], A[2], ... , A[n] and print them out in a table. 

Algorithm NumReader-V1;
 1. Read in the number N;
 2. print " There are", N, " numbers";
 3. print " ------------------------"; 
 4. k <-- 1;
 5. repeat Steps 6 to 8 until (k > N)
 6.   read in the next number and store in A[k];
 7.   print k, A[k];
 8.   increase the value of k by 1;
 9. endrepeat
10. print " --- end of input ---"
11. stop;

Question PP1-1: This algorithm can be written in the more concise form of pseudo-code. Do it yourself first, before peeking at the answer --- here.

Below, I show some input and corresponding output of the algorithm.

  1. First Sample Input/Output:
    INPUT: 
    2  2201  160601

     ----> 
    OUTPUT:
 There are 2 numbers
 ------------------------
   1    2201
   2  160601
 --- end of input ---

  2. Second Sample Input/Output:
    INPUT: 
    4  123  -44  89  32

     ----> 
    OUTPUT:
 There are 4 numbers
 ------------------------
   1   123
   2   -44
   3    89
   4    32
 --- end of input ---

  3. Third Sample Input/Output:
    INPUT: 
    1  123 -44  89  32

     ----> 
    OUTPUT:
 There are 1 numbers
 ------------------------
   1   123
 --- end of input ---
    Remarks: Notice that the last three numbers are not read in since that is what the algorithm does --- it only reads in one of the numbers since N=1 (as specified by the first input).

Try these out YOURSELF NOW:

Question 2: What is the output if given the following input?
  1. 3 10000 -20 35
  2. 6 1 2 3 6 5 4
(Answer is here.)


Question 3: Notice that in the third example, the grammar of the output was not good --- "There are 1 numbers" is not good grammar. Can you use an appropriate conditional operation to get the algorithm to exhibit good grammar: Use "There is 1 number" when N=1 and use "There are x numbers" is x is larger than 1. Show the modified "smarter" algorithm.
(Answer is here.)

There are always many ways of achieving the same result.
Here is another version of the algorithm. This algorithm first reads in all the numbers and stored them into the array A. And then it prints them out. 

Algorithm NumReader-V2;
 1. Read in the number N;
 2. k <-- 1;
 3. repeat Steps 4 to 5 until (k > N)
 4.   read in the next number and store in A[k];
 5.   k <-- k + 1;
 6. endrepeat;
 7. print " There are", N, " numbers";
 8. k <-- 1;
 9. print " ------------------------"; 
10. repeat Steps 11 to 12 until (k >= N)
11.   print k, A[k];
12.   k <-- k + 1;
13. endrepeat
14. print " --- end of input ---"
15. stop;

Try these out YOURSELF NOW:
Question PP1-4: Convert the algorithm above to the more concise form of pseudo-code.
(Answer is here.)

Another change is to use a for-loop instead.
This make the code more compact because we don't have to increment k ourselves.
Incrementing of the variable k is done automagically by the for-loop. Ain't it cool? 

Algorithm NumReader-V3;
 1. Read in the number N;
 2. for k <-- 1 to N do
 3.   read ( A[k] );
 4. endfor;
 5. print " There are", N, " numbers";
 6. print " ------------------------"; 
 7. for k <-- 1 to N do
 8.   print k, A[k];
 9. endfor
10. print " --- end of input ---"
11. stop;

Question PP1-5: Modify the algorithm so that apart from printing the number, it also print out the square of the number.
(Answer is here.)

Alg-PP2: [Algorithm to zero-out an array]
Algorithm to zero-out an array A[1], A[2], ... , A[N]. Namely, we want to have A[1]=0, A[2]=0, ... , A[N]=0.
Useful operation to initialize an array. 

Algorithm ArrayInit-V1;
  Read in the number N;
  for k <-- 1 to N do
    A[k] <-- 0;
  endfor;
  stop;

Question PP2: Modify the algorithm so that we initialize arrays B and C so that for all B[k]=k, and C[k]=k*k. Namely, B[1]=1, B[2]=2, ... ,B[N]=N and C[1]=1, C[2]=4, C[3]=9, ... , C[N]=N*N.
(Answer is here.)

Alg-PP3: [Copying Arrays]
Algorithm to make a copy array A to another array D; and algorithm to copy an array A in reverse to get arrays R and S. 

Algorithm Copy-Array;
  for k <-- 1 to N do
    D[k] <-- A[k];
  endfor;
  stop;
        
Algorithm Copy-Array-Reverse;
  for k <-- 1 to N do
    R[k] <-- A[N+1-k];
    S[N+1-k] <-- A[k];
  endfor;
  stop;

Question PP3: You are given N=5, and array A given by [2, 4, 7, 3, 9], namely, A[1]=2, A[2]=4, A[3]=7, A[4]=3, and A[5]=9. What will the arrays D, R and S be after executing the algorithm?
(Answer is here.)

Alg-PP4: [Print an array in reverse order]
Algorithm to print out an array in reverse order, namely, A[N], A[N-1], ... , A[2], A[1]. (Assume that N has already been read in.) 

Algorithm Array-Reverse-Print;
  for k <-- 1 to N do
    Print k, N+1-k, A[N+1-k];
  endfor;
  stop;

Alg-PP5: [Count number of failures]
Given an array M[1],...,M[N] of course marks. Algorithm to count the number of failures. FailCount is the variable that stores the number of failures. 

Algorithm Count-Failure;
  FailCount <-- 0;
  for k <-- 1 to N do
    if (A[k] < 40) 
       then FailCount <-- FailCount + 1;
    endif;
  endfor;
  Print " There are ", N, " students altogether";
  Print " There are ", FailCount, " failures";
  stop;

Question PP5-1: What is the output of the algorithm given the following input? 

INPUT: 
  10   
  25 56 97 34 39
  70 82 56 54  3
(Answer is here.)

Question PP5-2: Modify the algorithm so that it will also count the number of students who receive an "A" in the course. We define an "A" grade to be those with 80 marks or more.
(Answer is here.)

Alg-PP6: [Pattern Matching Algorithm]
A pattern matching algorithm is described in [SG] and given in verbose (more long-winded) pseudo-code in Figure 2.12 (page 60) of [SG].

Question PP6-1: Rewrite the algorithm in the more concise form of pseudo-code.
(Answer is here.)

The pattern matching algorithm was also discussed and presented during the lectures. However, it separated the algorithm into two processes --

  1. a process that "slides" the pattern P along the text T (from left to right), and
  2. another process that does the detailed matching for any given "alignment" of the pattern P and the text T.
The algorithm for the first process can be given as follows: 
Algorithm Pattern-Matching-2;
  for k <-- 1 to (n-m+1) do
    Mismatch <-- CheckMismatch(P,T,k);
    if (Mismatch = "NO")
      Print "There is a match at position ", k ;
    endif;
  endfor
  stop;

Question PP6-2: Write the algorithm for the second process -- the of Checking Mismatch.
(Answer is here.)

Answers to Selected Questions:

Answer to Question 1:
The Algorithm NumReader-V1 re-written in more concise form of pseudo-code. I want to illustrate that writing in a more concise pseudo-code is not very difficult to do -- it is mostly straight-forward translation, except for the case of a loop in which case, you have to be more careful. But, it can be done easily with some practice. Do it YOURSELF a few times and you will get the hang of it. 

Algorithm NumReader-V1;
 1. Read (N);
 2. print " There are", N, " numbers";
 3. print " ------------------------"; 
 4. k <-- 1;
 5. repeat 
 6.   read (A[k]);
 7.   print k, A[k];
 8.   k <-- k + 1;
 9. until (k > N)
10. print " --- end of input ---"
11. stop;
Back to Question PP1-1

Answer to Question 2:
(a)
INPUT: 
    3 10000 -20 35    

 ----> 
OUTPUT:
 There are 3 numbers
 ------------------------    
   1   10000
   2     -20
   3      35
 --- end of input ---

(b)
INPUT: 
    6 1  2  3  6  5  4    

 ----> 
OUTPUT:
 There are 6 numbers
 ------------------------    
   1       1
   2       2
   3       3
   4       6
   5       5
   6       4
 --- end of input ---
Back to Question PP1-2

Answer to Question PP1-3:
Replace the line 2 with the following: 
 2. if (N=1) 
2a.   then print " There is", N, " number";
2b.   else print " There are", N, " numbers";
Back to Question PP1-3

Answer to Question PP1-4:
Actually, this is very easy if we use a repeat-until loop. 
Algorithm NumReader-V2-concise;
 1. Read ( N );
 2. k <-- 1;
 3. repeat
 4.   read ( A[k] );
 5.   k <-- k + 1;
 6. until (k > N);
 7. print " There are", N, " numbers";
 8. k <-- 1;
 9. print " ------------------------"; 
10. repeat
11.   print k, A[k];
12.   k <-- k + 1;
13. until (k >= N);
14. print " --- end of input ---"
15. stop;
Back to Question PP1-4

Answer to Question PP1-5:
Just modify the print statement --- the square of A[k] is just given by A[k]*A[k] or also by square(A[k]). 
Algorithm NumReader-V3;
 1. Read in the number N;
 2. for k <-- 1 to N do
 3.   read ( A[k] );
 4. endfor;
 5. print " There are", N, " numbers";
 6. print " ------------------------"; 
 7. for k <-- 1 to N do
 8.   print k, A[k], A[k]*A[k];
 9. endfor
10. print " --- end of input ---"
11. stop;
Back to Question PP1-5

Answer to Question PP2: 
Algorithm ArrayInit-V1;
  Read in the number N;
  for k <-- 1 to N do
    B[k] <-- k;
    C[k] <-- k*k;
  endfor;
  stop;

Back to Question PP2

Answer to Question PP3:
D will be the same as A. R and S are the reverse of A.

Back to Question PP3

Answer to Question PP5-1:
Make sure that you exercise the algorithm. You can also try more input/output until you fully understand this algorithm. 
INPUT: 
  10   
  25 56 97 34 39
  70 82 56 54  3

 ----> 
OUTPUT:
 There are 10 students altogether
 There are  4 failures

Back to Question PP5-1

Answer to Question PP5-2:
Have a new variable ACount that store the number of "A"'s. 
Algorithm Count-Failure;
  FailCount <-- 0;
  ACount    <-- 0;
  for k <-- 1 to N do
    if (A[k] < 40) 
       then FailCount <-- FailCount + 1;
    endif;
    if (A[k] >= 80) 
       then ACount <-- ACount + 1;
    endif;
  endfor;
  Print " There are ", N, " students altogether";
  Print " There are ", ACount, " with Grade A";
  Print " There are ", FailCount, " failures";
  stop;

Back to Question PP5-2

Answer to Question PP6-1: 
Algorithm Pattern-Matching;
  Read (n, m);
  Read (T[1], T[2], ... , T[n]);
  Read (P[1], P[2], ... , P[m]);
  k <-- 1;
  repeat until (k > (n-m+1))
    i <-- 1;
    Mismatch <-- "NO"
    repeat until (i>m) or (Mismatch="YES")
      if  (P[i] not equal to T[k+i-1])
        then Mismatch <-- "YES"
        else i <-- i+1;
      endif;
    endrepeat;
 
    if (Mismatch = "NO")
      Print "There is a match at position ", k ;
    endif;
    k <-- k + 1;
  endrepeat;
  stop;

Back to Question PP6-1

Answer to Question PP6-2:
This is also simple --- it is essentially abstracting out the process the checks for mismatch in Algorithm 2.12 --- namely the inner-loop. 
Algorithm CheckMismatch(P, T, k);
// Given a pattern P of length n, and 
//       a text T of lenght m, and they are
//       aligned at position k of the text T.
// To check for mismatch between 
//    P[1]<-->T[k], P[2]<-->T[k+1], ... , P[n]<-->T[k+n-1]
//
  i <-- 1;
  Mismatch <-- "NO"
  repeat until (i>m) or (Mismatch="YES")
    if  (P[i] not equal to T[k+i-1])
      then Mismatch <-- "YES"
      else i <-- i+1;
    endif;
  endrepeat;
  return Mismatch; 
end;

Back to Question PP6-2

UIT2201: CS & IT Revolution; (Fall 2003); A/P Leong HW