1. Your company has 500 stockbrokers who sell stocks in different industries—electrical, healthcare, finance, and oil. You would like to compute each salesperson’s total commission. The commission is $50 for each electrical stock, $25 for each healthcare, $10 for finance, and $100 for oil. Describe a parallel algorithm to solve this problem in the shortest possible time.
2. In the AES encryption problem, our program searches for a portion of the 256-bit key that matches a given plaintext to its ciphertext. It uses a brute-force attack which searches the entire search space.
a) Is this problem a proper candidate for embarrassingly parallel computation? Explain why or why not.
b) Suppose that the most significant 192 bits of the key are already known. If the program creates 8 threads, how many encryptions does each thread need to compute if the workloads are well-balanced among the threads?
3. We know that we can compute cos(x) using the Taylor series expansion. Answer the following questions on this method:
• Write a sequential program in pseudocode that computes cos(x) for x = 0.0, 0.1, 0.2, …, 14999.9, 15000.0 with three digits of precision. In other words, the Taylor series expansion should continue until ‘term/sum I < 0.001 where term refers to the last term in the Taylor series and sum is the summation of all the terms expanded so far.
• Convert the sequential program into an SMP parallel program (in pseudocode).
• Calculate Speedup and Eff as K (number of processors) changes.
4. A mailman needs to deliver mail in the neighborhood. Unfortunately, he does not have a good map. Hence, he will walk around randomly in the neighborhood with some heuristics. He knows around 1/2 of the homes are located on the east side, 1/4 are on the west side, 1/8 are on the north, and another 1/8 are on the south. The mailman will move around based on these probabilities. Specifically, he starts at (0,0) where the post office is located, and moves one mile in each of the four directions at random with the specified probabilities. Write a cluster parallel algorithm to calculate the mailman’s final position.