CS 563 – Spring 2020
Midterm Exam Part II – Coding Questions March 23, 2020
Name: ______________________ Student ID: __________________
• This is an open book exam.
Copyright By PowCoder代写 加微信 powcoder
• Time: 8:00am-11:59pm on March 23, 2020.
• This exam consists two parts. This is Part II: coding questions.
• For each of these questions, you should submit your source code, as well as
a sample output screenshot.
• Submit your files to Blackboard in zip format by the above noted deadline.
• Note that pseudo code is acceptable, with 15% of deduction.
CS 563 Midterm Exam (Mar. 23, 2020)
II-1. (10 pts) The following procedure (quad) is for calculating approximate integral of a continuous function, as shown in the figure. Note that c is the midpoint of [a, b].
You should read the pseudo code and try to understand the algorithm.
procedure quad(real left, real right, real fleft, real fright, real lrarea){ real mid = (left+right)/ 2;
real fmid = f(mid);
real larea = (fleft + fmid) * (mid-left) / 2; real rarea = (fmid + fright) * (right-mid) / 2; if (abs((larea+rarea) – lrarea) > epsilon) {
larea = quad(left, mid, fleft, fmid, larea);
rarea = quad(mid, right, fmid, fright, rarea); }
area = larea + rarea;
return area; }
Identify the portion of the program which can be parallelized. Write a concurrent version of the algorithm. There is no restriction on the programming language or the synchronization technique. However, it must be multithreaded.
In your sample output, test your function using the following case: f=x^2, a =2, b=3, epsilon=0.00001.
CS 563 Midterm Exam (Mar. 23, 2020)
II-2. (15pts) A computer server has two printers, A and B, which are similar but not identical. Three kinds of client processes use the printers: those that must use A, those that must use B, and those that can use either A or B.
Develop code that each kind of client executes to request and release a printer, and develop a server process to allocate the printers. Since this will be used in a distributed system, so you must use message passing. No shared variables are allowed. Your solution should be fair assuming that a client using a printer eventually releases it.
In your sample output, use the scenario of 5 clients for printer A, 5 clients for printer B, and 5 clients with no specific requirement on the type of printers.
II-3. (15pts) Suppose there is one bathroom in ENCS. It can be used by both men and women, but not at the same time.
(a) Develop a solution to this problem using semaphores for synchronization. Allow any number of men or women to be in the bathroom at the same time. Your solution should ensure the required exclusion and avoid deadlock, but it does not need to be fair.
(b) Modifyyouranswerto(a)sothatatmostfourpeopleareinthebathroomatthesametime,and also ensure fairness.
Note: feel free to use the semaphore implementation provided in Assignment 7, or develop your own. No restrictions on the programming languages.
In your sample output, test your program using 10 men processes and 10 women processes.
CS 563 Midterm Exam (Mar. 23, 2020)
II-4. (20pts) Choose your favorite programming language and synchronization techniques to solve the water molecule problem.
Suppose hydrogen and oxygen atoms are bouncing around in space trying to group together into water molecules. This requires that two hydrogen atoms and one oxygen atom synchronize with each other. Let the hydrogen (H) and oxygen (O) atoms be simulated by processes (or threads). Each H atom calls a procedure Hready until another H atom has also called Hready and one O atom has called Oready. Then one of the processes (say O atom) should call a procedure makeWater. After makeWater returns, all three processes should return from their calls of Hready and Oready. Your solution should avoid deadlock and starvation.
In your sample output, test your program using 20 hydrogen processes and 12 oxygen processes.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com