:::::  Homework Assignment #4  :::::

Due Friday, December 4, 2009 by midnight! 

+5 extra credit if submitted on or before Wednesday, December 2.
+3 extra credit if submitted on Thursday, December 3.


*** All work has to be done individually! ***


1 written question and 1 programming question inside. 


Written question #1: Recursion

 Explain the similarity between recursive algorithms and the proof technique in math called mathematical induction. 
 

 As an example of proof by mathematical induction, we'll prove this statement: 

  "The sum of the first n positive odd integers is n-squared (n^2)."
   

  Proof:

   1. When n = 1, the sum of n positive odd integers is 1. So the statement is true. 

   2. Let's assume that when n = k, the sum of n positive odd integers is k^2. 
      (In other words, assume that the sum of the first k positive odd integers is indeed k^2, just like the original statement says). 

      When n = k+1, the sum of the first n odd integers is: 

            1 + 3 + 5 + ... + (2k-1) + (2(k+1)-1)
         =  (1 + 3 + 5 + ... + (2k-1)) + (2(k+1)-1)   // notice that 1 + 3 + 5 + .. + (2k-1) is, by our assumption above, equal to k^2.
         =  k^2 + (2(k+1)-1)
         =  k^2 + (2k + 2 - 1)
         =  k^2 + 2k + 1
         =  (k+1)^2

      So the statement is also true when n = k+1. 
      Therefore, we have proved the original statement that the sum of the first n positive odd integers is n-squared. 


 Grading: 20 points


Programming question #1: Stack 

 Intro:
  Stack is a data structure that shows last-in, first-out (LIFO) behavior. This means that the first element to go into the stack is the last one to come out of it. 

  As an analogy, think of a stack of plates. 
  When a person washes plates, the first one to be washed is placed at the bottom, the second one to be washed goes on top of the first one, and on and on. 
  Later, when the person wants to use one of those plates to serve cookies, he/she uses the plates at the top first. This plate was the one that was washed last. 

  Pictorially, plates a, b, c, d, e are washed in this order. Then the stack will look like:

                          e
                          d
                          c
                          b
                          a
                      ----------

  After all the washing is done, the plate that's used first is plate e. 
  This is last-in, first out (LIFO). 

  And the data structure that shows this behavior is called a stack. 

  There are two operations that can be done on a stack. 
    push: insert a new element into the stack. (= Placing a plate on top of the stack)
    pop: take out one element from the stack. (=Taking the top plate out of the stack)

  The picture of plates above shows the following operations:
    1. push(a)
    2. push(b)
    3. push(c)
    4. push(d)
    5. push(e)

  Now, if we pop, that is, 
    6. pop()

  Then we'll get plate e from the pop() operation and there will be only four plates left in the stack. 
  Another pop() operation will give us plate d, and there will be only three plates left in the stack. 


 Instructions:
  Implement a stack using:
     1. a linked list
     2. an array

  The following functions must be implemented:
     1. void pushX(char data);
     2. char data = popX();   
     3. char data = topX();  // Only returns data at the top of stack. Does not pop it out. 
     4. void printStackX();  // Print everything remaining in stack from top to bottom
     5. int isEmptyX();      // stack is empty? Return 1 if yes, 0 if no. 

  where X can be either L (Linked list) or A (Array). 
  For example, popL() is the pop operation for linked list and popA() is the pop operation for array.

  Use global pointer to node and and a global array. 

  Write all your code in stack.h. 
  And then test your code with main.c. 

 Grading:
  Your program will be graded out of 100 with the following breakdown:
  - Correctness (70 points) 
      The stack should be implemented correctly. 
      And it should compile!!!!!
      We will not accept any program that does not compile in CUNIX. 
      A program that compiles but is less complete is better than one that does not compile.

  - Elegance (10 points)
      Simple code is better than complex code. 
      Sometimes, complex code comes from the programmer not thinking clearly about the problem that the program is trying to solve. 
      Write simple, elegant code.

  - Format (10 points)
      Use indentation so that your code is readable.
      Your code should look neat.

  - Comments (10 points)
      Write comments liberally at the top of your code, and also inside the code.
   

What to submit:
  1) README file
    README file is a text file that contains your name, UNI, name and explanation of files that you're submitting, and your comments on your program. 
  2) Answer to written questions
    This should go in a separate text file with an extension .txt.
  3) Your source code file
    This is the stack.h file you'll submit as the programming part of your homework. 

 
How to submit:
  1) make a directory called homework4
  2) copy or move your README, written answer file, source code file to homework4.
  3) 'cd homework4' to get into that directory
        make sure you check that you're in homework4 by issuing a 'pwd' Unix command.
  4) Type '~jk2520/submit hwk4' in shell prompt.
     For example, this is what it'd look like with the CUNIX shell prompt, 
          $ ~jk2520/submit hwk4
 
     The submit script will ask some questions and let you submit homework.
     You will receive a confirmation email if the homework was submitted properly.