Data Structures and Algorithms
Assignment #1
See Blackboard for submission time requirements for your CSE 310 section
This assignment covers Chapters 2 and 3 of the text as well as an introduction to OpenMP. [75 marks total]
1. Prove by induction on n ! 1 that Pn i=1 1/2i = 1 ” 1/2n. [5 marks]
2. For each of the following pairs of functions f(n) and g(n), either f(n) = O(g(n)) or g(n) = O(f(n)),
but not both. Determine which is the case. Justify your answer. [15 marks total]
(a) f(n) = (n2 ” n)/2 and g(n) = 6n. [5 marks]
(b) f(n) = n + log n and g(n) = npn. [5 marks]
(c) f(n) = 2(log n)2 and g(n) = log n + 1. [5 marks]
3. For each of the following pairs of functions f(n) and g(n), state whether f(n) = O(g(n)), f(n) =
⌦(g(n)), f(n) = ⇥(g(n)), or none of the above. Justify your answer. [15 marks total]
(a) f(n) = n2 + 3n + 4 and g(n) = 6n + 7. [5 marks]
(b) f(n) = pn and g(n) log(n + 3). [5 marks]
(c) f(n) = 2n ” n2 and g(n) = n4 + n2. [5 marks]
4. Prove that (n + 1)2 = O(n2). [5 marks]
5. Prove that dlog ne = O(n). [5 marks]
6. Consider the following algorithm [10 marks total].
Algorithm 1 function Mystery(n)
1: r 0
2: for i 1 to n ” 1 do
3: for j i + 1 to n do
4: for k 1 to 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 Mystery? Express your answer as a function of n and
give the closed form. [5 marks]
(b) Using O() notation, give the worst-case running time of the function Mystery. [5 marks]
7. 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 total; 5 marks for each part]
1
(Use the definition of the O-notation,
by specifying two positive constants for the questions 4 and 5.)
(Show your work and justify your answers for (a) and (b))
To 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. Describe your observations about the values of the variables a and i in each of
these cases.
(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. That is, for increasing values of n, compare the
run time of the reduction clause (summation in parallel) to summation performed sequentially
(i.e., comment out the #pragma). Explain the observations of your experimentation.
(Thinking ahead: You might decide to use a reduction to implement the sum in parallel as part
of computing an average 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 di↵erences 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.)
TAKE ADVANTAGE OF OUR PROMOTIONAL DISCOUNT DISPLAYED ON THE WEBSITE AND GET A DISCOUNT FOR YOUR PAPER NOW!