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 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 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 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;

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 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 2

Answer to Question 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 3

Answer to Question 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 4

Answer to Question 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 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

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