AAMU  CS  CMP507 Data Structure and Algorithm  Dr. Peter Wang  
Homework #4 Due: 2/23/98

1. What is a file ? 
   A collection of related records in which each record 
   contains related data fields.

2. Name two ways that a priority queue can be represented. 
   Unsorted array and sorted link list.
   
3. What is a file organization method ? 
   File organization method is the structure of the records
   in a file. There are sequential, direct and indexed methods
   to arrange related records in a file.
   
4. What is a file access method ? 
   File access method is a method to retrieve and store
   information from/to a file in the disk.  There are sequential
   access, direct access, indexed access, indexed sequential 
   methods.

5. What is big-endian byte ordering ? 
   Computer systems differ in whether multibyte quantities are
   stored least significant byte first or most significant byte 
   first. Big-endian refers to the scheme where the MSB is 
   stored in the lowest memory address.

6. What is a byte machine ? 
   A byte machine computer use the byte as the basic unit
   (addressable) of storage device.

7. What is an expression ? 
   An expression contains one or more constants, variables, and 
   functions which are combined by zero or more binary operators
   to yield a single value.

8. What is column major order ? 
   In a high level programming langauge compiler, the effective
   address of an element in an array is calculated by varying
   the layers of data structure. In the column major order 
   programming language such as FORTRAN, the right-most index
   varies first.
   Ex.  INTEGER dasim(10,20,30)
        The address of dasim(i,j,k) = base-address-of-dasim +
	( (i-1)*20*30 + (j-1)*30 + (k-1) ) * 4

9. What is an array ?
   An array contains a set of homogeneous related data items
   which share the same variable name and accessed and modified
   by using the array name and the index of its relative 
   position inside the array.
   An array is a data structure which contains ordered pair 
   of (value, index).

10. What is the character data representation ? 
    The bit patterns to represent the symbols of an encoding
    system in a computer system.
   
11. What is best fit ? 
    In the heap and dynamic memory allocation, we travel around
    the ring of free blocks starting at the begin of the free
    space, and attempt to find a block that is exact fit or
    a block which is most close to the size requested.

12. What is first fit ? 
    In the heap and dynamic memory allocation, we travel around
    the ring of free blocks starting at the begin of the free
    space, and attempt to find the first block that is big 
    enough to satisfy the requestd memory size.


13. Write a funtion in C for bubble sort ? 
    void bubblesort(int *array, int n)
    {
       int i,j,k, temp;
       for(i=0; i<n-1; i++)
         for(j=i+1; j<n; j++)
         {
            if(array[i] > array[j])
            {
		temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	    }
         }
     }

14. What is a compound statement ? 
    One or more statements enclosed inside a pair of 
    braces and to be treated as a single statment in
    the syntax rule of the programming language.

15. What is even parity, what is odd parity ? 
    The total number bits of ones including the parity 
    bit is even (odd) is called a even (odd) parity.

16. What is an internal sort, what is an external sort ? 
    Internal sort deal with sorting a data set by first
    load the whole file from disk into the main memory
    then sort them according the sorting algorithm.
    When the data set is too big to fit into the main 
    memory, the sorting process must use disk as 
    intermidiate storgae buffer. This is called the 
    external sort.

17. What is a hashing function ? 
    A hash function is a mapping that sends a key onto 
    the address of a table entry into the table.

18. Give the O-notation corresponding to the following 
    adjective names for various complexity classes:  
    constant , logarithm , linear , n log n , quadratic , 
    cubic , and exponential ? 
    O(1), O(logn), O(n), O(nlogn), O(n*n), O(n*n*n), O(2**n)

19. Given recurrence relations of binary search as 
    T(1) = a , T(n) = b + T(n/2), find the O-notation
    of binary search ? 
    T(n)   = b + T(n/2)
    T(n/2) = b + T(n/4)
	..
	..
    T(n/(2**(m-2))) = b + T(n/(2**(m-1)))
    T(n/(2**(m-1))) = b + T(n/(2**m))

    let n = 2**m, then m=log(n)
    T(n) = m*b + T(n/(2**m))
         = m*b + T(1)
         = m*b + a
         = blogn + a
    Therefore, O(T(n)) = O(logn).

    
20. Find 10 solutions of 8-queen problem.
 0	4	7	5	2	6	1	3	
 0	5	7	2	6	3	1	4	
 0	6	3	5	7	1	4	2	
 0	6	4	7	1	3	5	2	
 1	3	5	7	2	0	6	4	
 1	4	6	0	2	7	5	3	
 1	4	6	3	0	7	5	2	
 1	5	0	6	3	7	2	4	
 1	5	7	2	0	3	6	4	
 1	6	2	5	7	4	0	3