upprevious
Up:assignments
 

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.
 


Malek Mouhoub 2001-01-17