CS 4625 Spring 2001
Assignment 1

Handed out: Thurs, Jan 18
Due: Thurs, Feb 01
Total Marks: [100]

Problem 1 [20]: Rank the following functions by order of growth; that is, find an arrangement $g_1, g_2, \ldots , g_{25}$ of the functions satisfying$g_1 = \Omega (g_2)$,$g_2 = \Omega (g_3)$,$\ldots,$$g_{24} = \Omega (g_{25})$. Partition your list into equivalence classes such that$f(n)$ and $g(n)$ are in the same class if and only if$f(n) = \Theta (g(n))$.
 
 
 

$(3/2)^n$	$(\sqrt{2})^{\mbox{lg }n}$	$\mbox{lg}^* n$	$n^2$	$(\mbox{lg } n)!$
$n^3$	$\mbox{lg}^2 n$	$\mbox{lg } (n!)$	$2^{2^n}$	$n^{1/ \mbox{lg }n}$
$\mbox{lg lg }n$	$n \cdot 2^n$	$n^{\mbox{lg lg }n}$	$\mbox{ln }n$	$2^n$
$2^{\mbox{lg }n}$	$(\mbox{lg n})^{\mbox{lg n}}$	$4^{\mbox{lg } n}$	$(n+1)!$	$\sqrt{\mbox{lg } n}$
$n!$	$2^{\sqrt{2 \mbox{ lg } n}}$	$n$	$n \mbox{ lg } n$	$1$

Note :  lg* n = lg lg ... lg n
 

Problem 2 [20]: Do Problem 4-1 on page 72.
 

Problem 3 [30]: Do Problem 1-2 page 17
 

Coding problem [30]: Code the merge sort algorithm as indicated in problem 3.
 

Hand_In of coding problem :

  1/ create a directory named "assign1"

 2/ move all files required by the assignment to the directory "assign1" i.e :

         If you are submiting a single file :

              program1.cpp

         If you are submiting more than one file :

              README (file expalaining the compilation and execution of your program including the
              format of input and other details)
              headers (.h)
              implementations (.cc , .cpp...etc)
              the Makefile :

                  should be named "makefile"

              the generated executable should be named : "assign1"

              you can give any name to your source files. The marker will only have to execute  "make" to
              compile your program and "assign1" to execute it.

3/  tar your directory

        tar cf assign1.tar assign1

4/ compress the result with gzip

        gzip assign1.tar

5/ The result will be a file named :

      assign1.tar.gz

6/ Execute the following script :

     /home/4625/assignments/a1_4625_submit

7/ Check(read the message) mentioning that the script has found your file

8/ Ignore the error message about uuencode !

9/ The marker will send you an e-mail confirming the reception
   of your files.