• January 29th, 2016

Data Structures and Algorithms

Paper, Order, or Assignment Requirements

Please solve the homework on a word document, do not solve question 7

Assignment #1 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) = n pn. [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.)

Latest completed orders:

Completed Orders
# Title Academic Level Subject Area # of Pages Paper Urgency