Data Structures and Algorithms Assignment #1Solution

This assignment covers Chapters 2, 3, and 4 of the text  [100 marks  total].

Submit  electronically,  before midnight on Friday,  using the submission link on Blackboard for Assignment #1, a file named yourFirstName-yourLastName.pdf containing  your solution to this assignment (a .doc or .docx file is also acceptable, but  .pdf is preferred).

1.  Suppose  the  functions  g1 , . . . , g7   are  defined  as  follows:  g1 (n)  = √n, g2 (n)  = 2n ,  g3 (n)  = n1/3 , g4 (n)  = (log n)2 , g5 (n)  = nlog n , g6 (n)  = n/ log n and  g7 (n)  = (1/3)n .  Arrange  these  seven functions in ascending  order  by their  growth  rate.   In other  words, if you place g(n)  after  f (n)  then  show that f (n) = O(g(n)). Fully justify  your answer!  [25 marks]

 

2.  Consider  the following algorithm [10 marks].

 

Algorithm 1 function  Pesky(n)

Require: An integer  n ≥ 0.

1:  r ← 0

2:  for  i ← 1 to n do

3:       for  j ← 1 to i do

4:            for  k ← j to i + j do

5:                 r ← r + 1

6:            end for

7:       end for

8:  end for

9:  return r

 

 

(a)  What  is the  value returned by the  function  Pesky?  Express  your answer  as a function  of n and give the closed form.

(b)  Using O() notation, give the worst-case  running  time of the function  Pesky.

 

3.  Consider  the following recursive algorithm [10 marks].

 

Algorithm 2 function  g(n)

Require: A positive  integer  n.

1:  if n ≤ 1 then

2:       return  n

3:  else

4:       return  5 · g(n − 1) − 6 · g(n − 2)

5:  end if

 

 

(a)  Set  up  a  recurrence   for  this  function’s  values  and  solve  it  to  determine what  this  algorithm computes.

(b)  Set up and solve a recurrence  relation  for the number  of multiplications made by this algorithm.

4.  Let T (n)  be defined recursively  as [5 marks]:

 

T (n) =

 

 

Show by induction  that T (n) = 4n.


   4                        if n = 1

T (n − 1) + 4   otherwise

 

5.  You’re at  the  base of a staircase  consisting  of n stairs.  If each step  you make takes  you either  one or two stairs  higher,  what  is the number  of different ways in which you can climb the staircase?  Explain how you derived  your mathematical expression  in words.  [10 marks]

 

6.  Design a divide-and-conquer algorithm for computing  the number  of levels in a binary  tree.  In partic- ular,  the  algorithm should  return 0 and  1 for the  empty  and  single-node trees,  respectively.   What  is the efficiency class of your algorithm? [10 marks]

 

7.  Given  a pristine  chocolate  bar  with  n × m pieces making  up the  bar.   You need to break  it into  nm

1 × 1 pieces to share with nm  people.  You can break  the bar only in a straight line, and once broken, only one piece at  a time  can  be further  broken.   Design  an  algorithm that solves the  problem  with the  minimum  number  of bar  breaks.   What  is this  minimum  number?   Justify  your  answer  by using properties  of a binary  tree.  (Hint:  Think  divide-and-conquer.) [10 marks]

 

8.  Read the notes on OpenMP  (file OpenMP.pdf) compiling and executing  the sample programs  included in the zip file (file openmp.zip) as you go to familiarize  yourself with the various  OpenMP  directives. Take screenshots  of each activity  as you work your way through the exercise to include in your solution, including  answers to any questions  asked.  [20 marks]

Answer  the  following questions;  it  is expected  that you will run  each  program  multiple  times.   You may need to modify the  program(s) to answer  the  questions.  Be sure to explain  the  experiments you conducted.

 

(a)  For the program  in the file parfor.cc vary the value of the variable  n and the number  of threads specified in the  num threads clause.  How are the  iterations distributed among threads? Be sure to try  out fewer iterations than  threads, and more iterations than  threads, etc.

(b)  For the  program  in the  file private.cc explore the  values of the  variables  a and  i before, after, and  inside  the  parallel  region.   Try  initializing  the  variables  before  the  #pragma and  also  not initializing  them.

(c)  For the program  in the file reduction.cc explore the run time of the reduction clause by varying the  number  of threads in the  num threads clause.  (Thinking ahead:  Can  you use a reduction to implement the parallel  sum in the ParallelAverage command  in Project  #1?)

(d)  For the program  in the file schedule.cc explore the impact  of the schedule kind and chunk size on how chunks are assigned to threads. Investigate the schedules when kind is static, dynamic, and runtime. Specifically, for n=200 iterations and num threads(5) plot a graph for each schedule kind: give the  iteration number  along the  x-axis (1, . . . , 200) and  the  thread identifier  along the y-axis (0, . . . , 4).  This  graph  should indicate  which thread was assigned to which loop iteration, graphically  illustrating the differences between the kinds of schedules.  Explain  the results  of your graphs.  (Hint:  To make schedule.cc run faster,  put the threads to sleep for less time.)