Programming Excercises

Here is the programming practice excercises. Write Java programs to do the following tasks. Where an array is the array of integer of size N (index 0.. N-1) with values range 1..m (all positive). The questions are arranged from easy to more difficult. If you are diligent try to do them with recursion.

1. Find the maximum value in the array.
2. Find the second maximum value in the array.
3. Reverse all elements in the array, for example, if the array has {1,2,3,4,5} reverse it becomes {5,4,3,2,1}.
4. Count the number of one in the array.
5. Find two numbers that sum up to k in the array.

A list is has the list data structure defined in the class. Assuming that you have all functions defined in do-list.txt available.

6. What is the last number in the list?
7. Copy a list.
8. Calculate the Fibonacci number.
9. Calculate the Factorial number.
10. Change a triangle into a square.

Here is the explanation (no code provided). Let the array's name be "ax" and N1 = N-1.

1. This is a simple "loop". Pick the first one ax[0] to be the first max. You iterate from index 1 to N1. Compare each one to max. If it is larger, swap it with the max.
2. Find max in the array, keeping track where (what index) it is. Zero the max element then find the max again.
3. I suggest two methods:
3.1 One easy way is to use a second array as a temporary place storing elements from the original array.
      First, copy to the temp from back to front. The temp now is the reverse of the original.
      Copy the temp back to the original in order.
3.2 Not using "temp". To do it "in place", assume the size of array is even (we will deal with the odd case later).
     Divide the array into two subarrays, called them A and B.
     Swap A[first] with B[last] do it until A[last] with B[first].
     If size of the array is odd, do the same but leave the middle element alone.
4. This is similar to 1. Using "loop" keep a count beginning with 0. If the value of the element is one, increment the counter.
5. This is a very general form of many problems you will find in writing a computer program to do some search. Making "a pair" of numbers from a set of numbers and check whether the pair has the desired property.
     Using two loops, the first loop (outter) picks the first number, let's call it "a".
     The second loop (inner) picks the second number, "b".
     For each "a" we get a "b" which range over every numbers of the set.
     You can check the proprety of the pair "a, b".
6. Walking into the list, at each node we get the number. We know it is the last data item when its link is zero.
7. I suggest two methods:
7.1 To copy a list.
         Collect numbers from the list (first to last) into an array.
         Make a list from that array using "insert" from last to first (because we can access that array in any order).
7.2 Walk into the list. See a node one-by-one.
          At each node get a number. Make this number a new node.
          "Append" this new node to the new list.
          How to "append"
              Keep a "pointer" to the last node of the new list.
              Set the link of the last node to the new node.
8. The Fibonacci series are defined by the following formula:
       fib(n) = 1                      if n <= 2
              = fib(n-1) + fib(n-2)    otherwise
where 1 <= n
This is the series:
    n          1 2 3 4 5 6 7 . . .
    fib(n)     1 1 2 3 5 8 13 . . .
This series has many occurrence in nature (such as the arrangement of the seed of the sunflower).
   An efficient way to calcuate it is to use iteration with two variables holding fib(n-1) and fib(n-2). We use F1 (fib(n-1)) and F2 (fib(n-2)). Using the following formula:
    F_t = F1_t-1 + F2_t-1       where F_t is F at the iteration t.
Begining with F1= 1, F2 = 1 and t = 3..n.
9. A factorial number is defined by 1 * 2 * 3 * .... n
      fac(n) = 1              if n = 0
              = n * fac(n-1)   otherwise
A direct implementation is to write a recursive program from the definition. Another way is to use iteration. Keep fac(n-1) in a variable. Beginning with F = 1
      for i = 1 to n
        F = F * i
10.   Think of a triangle consisted of "star" forming the following shape:

*
**
***
****

The triangle of size n, at the base it has n "stars", the top has one star. Using all these stars to build a square (as near square as possible). What will be the size of the square?

***
***
***
*

We build the square like this:
1) place the first star in a corner (say top left). This is the square 1 x 1
2) the subsequent placement will increase the size of square to n + 1. We build it layer-by-layer, increase the size one step-by-step. Here is the partial sequence of building a square (the number shows the order of placement of stars).
1 4 9
2 3 8
5 6 7
10 . . .

The following steps will change a triangle into a near perfect square:
   Count how many stars are there in the triangle. It is k = 1 + 2 + 3 + .. n
   Use k to build a square:
      Each "layer" consists of width + (height) "stars", n + (n-1), for exampley, layer 2 consists of {2,3,4} = 2 + 1 = 3 stars.
      1 4
   2 3
Using loop to build up the square layer-by-layer, keep tracking of how many stars have been used. Stop when run out of stars.

End