CS1134- Homework 3 Solved

Question      1:        

Consider the following two implementations of a function that if given a list, lst, create and return a new list containing the elements of lst in reverse order.


def reverse1(lst):     rev_lst = []     i = 0     while(i < len(lst)):         rev_lst.insert(0, lst[i])

        i += 1     return rev_lst

  def reverse2(lst):     rev_lst = []     i = len(lst) - 1     while (i = 0):

        rev_lst.append(lst[i])

        i -= 1     return rev_lst


If lst is a list of n integers,

1.    What is the worst case running time of reverse1(lst)? Explain of your answer.  

2.    What is the worst case running time of reverse2(lst)? Explain of your answer.



Question      2:        

Consider       the      implementation         we       made   in         class    for       ArrayList,  and      its        extensions      you      did      in           the      lab.     

In       this      question,        we       will      add      two     more   methods         to         this      class:   the      insert          method           and           the      pop     method.          For      this      question,        please submit the      modified         ArrayList  class.  

a)  Implement           the      method           insert(self, index, val)  that     inserts val     before index            (shifting          the      elements        to         make   room   for       val).  
         

For example,         your    implementation         should follow the      behavior         below:

arr_lst = ArrayList() for i in range(1, 4+1):

...    arr_lst.append(i)

arr_lst.insert(2, 30)

arr_lst

[1, 2, 30, 3, 4]

Notes:                  

1.  Make    sure    to         double the      capacity          of         the      array,  if          there   is         no        room   for       an        additional  element.        

2.  Your     function          should raise    an IndexError exception in any case the index

(positive or negative) is out of range. 

     

b) Implement           the      method           pop(self),  that     removes         the      last      element          from    the      list.      The      pop     method           should return the      element          removed         from    the      list,      and      put      None  in         its      place   in         the      array.  If         pop     was     called  on        an        empty list,      an        IndexError            exception      should be        raised.

In  order  to         maintain         the      linear  memory          usage  of         the      list       data     structure,       and      its        efficient      amortized      performance, we       use      the      following        shrinking        strategy:         When  the      number          of      elements        in         the      list       goes    strictly            below  a          quarter           of         the      array’s capacity,         we      shrink its        capacity          by        half.                

For example,         your    implementation         should follow the      behavior         below:

arr_lst = ArrayList() for i in range(1, 5+1):

...    arr_lst.append(i)

arr_lst.pop()

5

arr_lst.pop()

4

arr_lst.pop()

3

arr_lst.pop()

2

arr_lst

[1]

Note:         After   the      executing       the      code    above, the      capacity          of         the      array   in         ArrayList  will      be      4.        

                     

c)    Extra        Credit  (You    don’t   need    to         submit):          The     extending       and      shrinking        strategies       we       use      in     our      ArrayList  implementation         (doubling       the      capacity          of         the      array   each    time    there   is         no     room   to         add      an        element,         and      shrinking        the      capacity          of         the      array   by        a          factor  of     2          each    time    the      number          of         elements        is         less      than    a          quarter           of         the      array’s     capacity),       guarantees     two     important       things:

i.    In           any      given   time,   the      memory          used    to         store   the      elements        is         linear. That    is,        if         

there are      n          elements        in         the      array,  then:   𝑛 ≤ (𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦            𝑜𝑓        𝑡ℎ𝑒      𝑎𝑟𝑟𝑎𝑦) ≤ 4𝑛. 

ii.  Any        sequence        of         n          append          and/or            pop     operations      on        an        initially           empty   ArrayList  object, takes   O(n)    time.  

   

Proving   these   properties      is         out      of         the      scope  of         this      assignment,    but      we       will      show   two    supporting     insights:         

1.     Show that     the      following        series  of         2n        operations      takes   O(n)    time:   n          append          operations      on          an        initially           empty array,  followed         by        n          pop     operations.    

2.     Consider       a          variant            to         our      shrinking        strategy,         in         which  an        array   of         capacity          N,          is         resized            to         capacity          precisely         that     of         the      number          of         elements,        any          time    the      number          of         elements        in         the      array   goes    strictly            below  N/2.    

Show that     there   exists  a          sequence        of         n          append          and/or            pop     operations      on        an          initially           empty ArrayList  object, that     requires          Ω(𝑛3)  time    to         execute.         

         

d)    Modify     the      pop     method,          so        it          could   optionally       get       an        index   as        a          parameter.     This     index   indicates         the      position          of         the      element          that     is         to         be        removed         from    the      list.    

   

Notes:     

1.     Make sure    to         use      the      same   shrinking        strategy          described       above  in         section            (b).     

2.     Your  function          should raise    an IndexError exception in any case the index

(positive or negative) is out of range.          

         

Question      3:                    

a)    Give         a          linear implementation      of         the      following        function:         def find_duplicates(lst)

The          function          is         given   a          list       lst     of         n          integers.         All       the      elements        of         lst     are    from    the      domain:          {1, 2, …, n-1}. Note    that     this      restricted       domain           implies           that     there   are    element/s      appearing       in         lst     more   than    once.              

The          function          should return a          list       containing      all        the      elements        that     appear in         lst     more    than    once.  

   

For           example,         if          lst=[2, 4, 4, 1, 2],  the      call      find_duplicates(lst)            could   return [2, 4].   

   

b)    Analyze   the      worst-case     running          time    of         your    implementation         in         (a).     

         

Question      4:        

The    remove(value)     method           of         the      list  class,   removes         the      first    occurrence     of         value           from    the      list       it          was     called  on,       or        raises  a          ValueError            exception,       if          value            is           not      present.                     

Note:  Since   remove          needs  to         shift    elements,        its        worst-case     running          time    is         linear.            

         

In       this      question         we       will      look     into     the      function          remove_all(lst, value),      that     removes         all           occurrences   of         value            from    lst.   

         

a)    Consider the      following        implementation         of         remove_all:           def remove_all(lst, value):

    end = False     while(end == False):         try:

            lst.remove(value)         except ValueError:             end = True

 

 Analyze the      worst-case     running          time    of         the      implementation         above.

         

b)    Give         an        implementation         to         remove_all            that     runs    in         worst-case     linear  time.   Notes:            

1.     Your  implementation         should mutate           the      given  list      object (in-place),      without           using   an        additional          data     structure.      

2.     Your  implementation         should           keep   the      relative          order  of         the      elements        that     remain            in          the      list      

         

c)    Analyze   the      worst-case     running          time    of         your    implementation         in         (b).