AAMU Math&CIS CMP507 Data Structure & Algorithm  Dr. Peter Wang
Homework #3 Due: 2/16/98

1. List ten difference types of data structures in levels of data abstraction.
   Array, record, queue, stack, set, tree, graph, list, 
   parallel array, and string.

2. What is the lifetime of dynamically allocated storage ?
   Start from the point it is created, untill the program
   terminated.

3. What consists of a software system ?
   Domain knowledge and programs.

4. What consists of a program ?
   Data structure and algorithm.

5. What is the main idea in computer science ?
   Learn the skills to solve the real world problem.

6. What is an anonymous variable ?
   The block of storage that pointers refer to are 
   created dynamically during the running of the 
   program and can be thought of as annoymous variables.

7. Write a C function to display the nodes of a linked list.
   void display(Nodeptr curptr)
   {
	while(curptr)
	{
		printf("%d %s\n",curptr->intv,curptr->stringv);
		curptr = curptr ->next;
	}
   }

8. What is top-down programming using stepwise refinement ?
   We start with the top level goal for  what the program 
   suppose to accomplish, we decompose the problem into 
   subproblems and with a series of stepwise decompositions,
   more detail level of the problem was designed. This 
   process is repeated until all the subproblems are simple
   enough to have simple solutions.

9. Write a recursive sum of squares in C.
   int sum(int n)
   {
	if(n==1) return 1;
	return (sum(n-1)+n*n);
   }


10. Write a recursive fibonacci in C.
    int fibonacci(int n)
    {
      if(n==1) return 0;
      if(n==2) return 1;
      return (finbonacci(n-2)+fibonacci(n-2));
    }

11. Write a recursive factorial in C.
    int factorial(int n)
    {
      if(n==1) return 1;
      return (n*factorial(n-1));
    }

12. What is the base case in a recursive program ?
    Base case is the situation which has simple solution
    for the subproblem. So, a simple value is return 
    instead of going on endless splitting problems
    into subproblems.

13. Given C(n,0)=1, C(n,n)=1, write a recursive 
    function for C(n,k) in C.
    int combination(int n, int m)
    {
      if(m==0 || n==m) return 1;
      return (combination(n-1,m)+combination(n-1,m-1));
    }

14. What is an infinite regress ?
    An infinite regress is somewhat analogous to the 
    endless loop in an iterative program.
    It occurs when a recursive program calls itself 
    endlessly and never encounter a base case that 
    force it to stop its execution.

15. Write a recursive function for Towers of Hanoi in C.
    void movetowers(int n, int start, int finish, int spare)
    {
      if(n==1) printf("Move a disk from peg %d to peg %d\n",start,finish);
      else {
	movetowers(n-1,start,spare,finish);
	printf("Move a disk from peg %d to peg %d",start,finish);
	movetowers(n-1,spare,finish, start);
      }
     }

16. What is information hiding ?
    A module is a unit of a software system that package
    together a collection of objects and that carefully 
    controls what external users of the module can see 
    and use. In this way, modules can protect their 
    internal mechanisms from external tampering. 
    This is called information hiding.

17. What is the interface file of a module ?
    The interface file of a module defines the data types
    and the function prototypes of the module.

18. What is the implementation file of a module ?
    The implementation file of a module defines the functions
    used in the module.

19. What is a priority queue (PQ)?
    A priority queue is an abstracted data structure which 
    act as a container that holds some prioritized items.
    A priority queue is a finite collection of items 
    for which the following operations are defined:
    a. initialize the priority to the empty PQ.
    b. Determine whether or not the PQ is empty.
    c. Determine whether or not the PQ is full.
    d. Insert a new item into the PQ.
    e. Remove from the PQ an item if the PQ is not empty.

20. Name two ways that a priority queue can be represented, and
    sketch the main ideas of how each representation works.
    A. An unsorted array of items.
       To insert a new item, we simply add it at the end of the PQ.
       To remove an item from PQ, we need to search the one with highest
       priority and delete it from PQ, then the last item is move to
       the empty slot. A counter is maintained to check for the emptyness
       and fullness of the PQ.
    B. Sorted link list.
       The items are inserted into the PQ in the decending order of 
       their opriority. To remove an item from the PQ, simply remove 
       the first element from the PQ. A counter is maintained to test
       the emptyness and fullness of the PQ.


  ^^^^ I will try to do HW4 tomorrow if time permits ^^^^