Assignment   2     SOLN

The   goal   of   this   assignment   is   to   become   comfortable   using   the   basic   Array   and   ArrayList   data    structures   and   to   gain   some   exposure   to   sparse   arrays.     A   sparse   array   is   a   data   structure   that    does   not   require   any   memory   to   represent   an   entry   with   the   value   0,   which   is   useful   for   low-­‐ density   data.     We’ll   run   a   simple   algorithm   on   the   two   array   types   as   a   quantitative   experiment    to   compare   the   execution   times   of   the   two   implementations.      For   example,   a   dense   array   might   look   like:    [   1,   10,   15,   0,   0,   2,   0,   7,   43,   0,   12,   0,   0   ]    The   corresponding   sparse   array,   containing   all   data   necessary   to   expand   back   to   the   sparse    representation,   night   look   like:    [   [0,   1],   [1,   10],   [2,   15],   [5,   2],   [7,   7],   [8,   43],   [10,   12]   ]   

1.   [10]   Write   a   Java   program   that   first   prompts   the   user   for   an   integer   array   length   and   a    double-­‐precision   array   density.     You   will   use   these   values   to   create   the   arrays   for   the    experiment   (see   parts   2   and   3   below).     For   example,   if   the   user   enters   an   array   length   of   100    and   a   density   of   0.1,   your   program   will   create   arrays   of   length   100   with   on   average   of   10    random   non-­‐zero   entries.     Catch   any   exceptions   due   to   the   user   entering   unparsable   input   and    prompt   them   to   reenter   the   value(s).   

2.   [20]   Write   a   function   which   takes   an   integer   length   and   an   array   density   of   type   double   as    arguments   and   returns   a   new   array   of   type   int   representing   a   dense   array.     For   each   entry   in    the   array,   compare   the   density   with   a   random   number   on   the   range   [0.0,   1.0)   (i.e.,   0.0   up   to,    but   not   including,   1.0)   to   determine   whether   or   not   the   entry   should   be   0   (hint:   see   the    java.util.Random   class).     If   the   entry   should   be   0,   simply   populate   the   entry   as   such.     If   the   entry    should   be   non-­‐zero,   populate   it   with   a   random   integer   on   the   range   [1,   1000000]   (i.e.,   1    through   1   million).   

3.   [20]   Write   a   function   which   takes   an   integer   length   and   an   array   density   of   type   double   as    arguments   and   returns   a   new   ArrayList   representing   a   sparse   array.     As   above,   use   the   density    to   determine   whether   or   not   each   entry   should   be   0.   If   the   entry   should   be   0,   simply   do   nothing    (i.e.,   don’t   add   it   to   the   ArrayList).     If   the   entry   should   be   non-­‐zero,   store   its   index   and   value    (also   on   the   range   [1,   1000000])   in   the   ArrayList   (hint:   you   may   want   to   use   an   ArrayList   of   type    int[]   –   note   that   this   is   not   the   most   elegant   solution   but   we   have   not   yet   covered   objects   in    Java).     In   this   way,   the   returned   ArrayList   will   only   require   enough   memory   to   hold   the   non-­‐zero    elements   and   could   be   expanded   back   to   dense   form   if   necessary.

   4.   [20]   Write   a   function   which   takes   an   int   array   as   an   argument   and   prints   the   max   value   in   the    array,   along   with   the   index   of   that   value   in   the   array.   

5.   [20]   Write   a   function   which   takes   an   ArrayList   as   an   argument   and   prints   the   max   value   in   the    array,   along   with   the   original   index   of   that   value   in   the   array   (i.e.,   the   index   that   you   stored   in    part   3).   

6.   [10]   Use   the   System.nanoTime()   method   to   record   the   amount   of   time   taken   to   run   each   of    the   above   functions   (i.e.,   steps   2-­‐5   above).     Print   your   timing   results.     Spend   some   time   trying    different   combinations   of   inputs   and   write   your   findings   in   the   comments   of   your   code.     Which    implementation   is   faster   for   various   cases?     Your   output   should   look   something   like:    Please array length:  1000000 Enter density: 0.01 createDenseArray() length: 1000000 time: 39323000 createSparseArray() length: 10143 time: 28992000 findMax (array): 999990 at: 677720 dense findMax() time: 4083000 findMax (list): 999908 at: 494143 sparse findMax() time: 1793000 Zip   the   Assignment2   folder   in   your   Eclipse   workspace   directory   and   upload   the   .zip   file   to    Blackboard   (see   Assignment   2   assignment   in   Assignments   area).
Powered by