CS1134- Homework 2 Solved

Question        1:        

Use      the      definitions      of         O         and      of         Θ         in         order  to         show   the      following:      

a.         5n$ + 2n’ + 3n =           O 𝑛$    

b.         7n’ + 2n − 8 =   Θ 𝑛     

c.         Show      that     if          d(n)=O(f(n))   and      e(n)=O(g(n)),  then    the      product          d(n)e(n)           
 is                 O( f (n)g(n)). 

 

Question        2:        

Give     a          θ          characterization,       in         terms  of         n,         of         the      running          time    of         the      following        four functions:      
  

def example1(lst):


”””Return the sum of the prefix sums of sequence S.””” n = len(lst)
 total = 0
 for j in range(n): 

for k in range(1+j): 

total += lst[k]  return total


def example2(lst):


”””Return the sum of the prefix sums of sequence S.””” n = len(lst)
 prefix = 0
 total = 0
 for j in range(n):  prefix += lst[j]  total += prefix 

return total 
          

def example3(n):

    i = 1     sum = 0     while (i < n*n):         i *= 2         sum += i     return sum

  def example4(n):

    i = n     sum = 0     while (i 1):         for j in range(i):             sum += i*j         i //= 2     return sum


Question         3:        

Implement     a          function          def factors(num).         This     function          is         given   a          positive          integer num,    and      returns           a          generator,      that     when   iterated          over,   it          will      have    all        of         num’s  divisors in         an        ascending     order.

           

For      Example,        if          we       execute           the      following        code:   for curr_factor in factors(100):

print(curr_factor)

The      expected         output is:       

1                      2                      4                      5                      10                    20                    25                    50                    100   

     

Implementation         requirement: Pay      attention        to         the      running          time    of         your    implementation.        The     for loop    like      the      above, should run      in         a          total    cost     of         Θ         𝑛𝑢𝑚 . 

           
Question         4:        

The      number          e          is         an        important       mathematical constant         that     is         the      base    of         the      natural logarithm.      e          also     arises  in         the      study  of         compound      interest,          and      in         many  other   applications. 

Background   of         e:         https://en.wikipedia.org/wiki/E_(mathematical_constant)       

e          can      be        calculated       as        the      sum     of         the      infinite            series:

𝑒     
     

The      value   of         e          is         approximately           equal   to         2.71828.         We      can      get       an        approximate  value   of e,         by        calculating     only     a          partial sum     of         the      infinite            sum     above  (the     more   addends         we       add, the      better  approximation           we       get).   

           
Implement     the      function          def e_approx(n).           This     function          is         given   a          positive          integer            n, and      returns           an        approximation           of         e,         calculated       by        the      sum     of         the      first     (n+1)  addends of         the      infinite            sum     above.            

           
To        test      your    function          use      the      following        main:  def main():     for n in range(15):         curr_approx = e_approx(n)

        approx_str = "{:.15f}".format(curr_approx)         print("n =", n, "Approximation:", approx_str)
      

Note:   Pay      attention        to         the      running          time    of         e_approx.    By        calculating     the      factorials        over    for each    addend,          your    running          time    could   get       inefficient.      An       efficient          implementation         would run      in Θ 𝑛 .   

         
Question         5:        

Implement     the      function          def split_parity(lst).         That    takes   lst,    a          list       of         integers.         When called, the      function          changes          the      order  of         numbers         in         lst     so        that     all        the      odd     numbers will      appear first,    and      all        the      even    numbers         will      appear last.     Note    that     the      inner   order  of         the      odd numbers         and      the      inner   order  of         the      even    numbers         don’t   matter.           

           
For      example,         if          lst     is         a          list       containing      [1,        2,         3,         4],        after    calling split_parity,      lst could   look     like:     [3,        1,         2,         4].       

          
Implementation        requirements:           

1.     You           are      not      allowed         to         use      an        auxiliary         list       (a         temporary      local    list).               

2.     Pay            attention        to         the      running          time    of         your    implementation.        An       efficient          implementation      would run      in         a          linear  time.   That    is,        if          n          is         the      length of         lst,    the      running          time      should be        Θ 𝑛 .   


Question         6:        

Implement     the      function          def two_sum(srt_lst, target).    This     function          is         given: 

•       srt_lst -           a          list       of         integers          arranged        in         a          sorted order 

•       target    -           an        integer           

When  called, it          returns           two     indices            (collected       in         a          tuple), such    that     the      elements        in their    positions        add      up        to         target.         If         there   are      no        such    indices,           the      function          should return None. 
       

For      example,         if          srt_lst=[-2, 7, 11, 15, 20, 21],         and      target=22,  your    function          would return (1, 3)        because          srt_lst[1]+          srt_lst[3]=7+15=22     

           
Note:   Pay      attention         to         the       running           time     of         your     function.         Aim      for       a          linear   time     algorithm.           


Question         7:        

Implement     the      function          def findChange(lst01).         This     function          is         given   lst01,           a          list       of integers          containing      a          sequence        of         0s        followed         by        a          sequence        of         1s.                   When called, it          returns           the      index   of         the      first     1          in         lst01.          

           
For      example,         if          lst01            is         a          list       containing      [0, 0, 0, 0, 0, 1, 1, 1],  calling findChange(lst01)       will      return 5.        
          

Note:   Pay      attention        to         the      running          time    of         your    function.         If         lst01            is         a          list       of size     𝑛,         an        efficient          implementation         would run      in         logarithmic    time    (that    is         Θ 𝑙𝑜𝑔’(𝑛) ).