This exam must be developed individually.
The following problem is an adaptation of problem 1196 - Ring of Primes from the Caribbean Online Judge.
A ring of primes of size n (where n is an even number) is a circular list with n nodes numbered from 1 to n in which the sum of every two adjacent nodes is a prime number.
For example, the following image represents one possible ring of primes of size n=6:
The above image can be represented as a Clojure sequence starting in 1 and then going clockwise:
(1 4 3 2 5 6)
A second solution for n=6 would be:
(1 6 5 2 3 4)
Note that the ring always starts with 1.
The function rc(n) is the number of different rings of primes that exist for a certain size n. Thus, from the above example, rc(6) = 2.
Another example: all the possible rings of primes for n=8 would be:
(1 2 3 8 5 6 7 4) (1 2 5 8 3 4 7 6) (1 4 7 6 5 8 3 2) (1 6 7 4 3 8 5 2)
This means that rc(8) = 4.
Find:
rc(18)
Spoler alert!
The correct answer is: 770,144.
Write a Clojure function that allows you to compute this solution in parallel, using a computer system with a dual-core CPU or better. The name of the function must be rc18 and it must be contained in a namespace called exam3 (thus, your source file should be called exam3.clj). The function should take as an argument the number of threads to use during the computation.
Usage examples:
(exam3/rc18 1) ⇒ 770144 (exam3/rc18 2) ⇒ 770144 ;;; Same result as above, except computed faster! ;;; Using all available CPU cores. (def n (.. Runtime getRuntime availableProcessors)) n ⇒ 4 (exam3/rc18 n) ⇒ 770144 ;;; Use the 'time' function to measure the execution speed. (time (exam3/rc18 1)) "Elapsed time: 5316.49139 msecs" ⇒ 770144 (time (exam3/rc18 2)) "Elapsed time: 2998.792322 msecs" ⇒ 770144 (time (exam3/rc18 n)) "Elapsed time: 2437.281383 msecs" ⇒ 770144
NOTE: Elapsed times in your system may vary considerably from the ones presented here.
You may define any number of additional auxiliary functions. Just make sure every single function contains a doc-string explaining its purpose.
Run your functions multiple times and measure how long they take to execute for different number of threads.
When running the function with the number of threads equal to the number of available CPU cores, make sure that all CPU cores get used at near 100% their capacity during a certain moment, as shown in the following image of the system monitor:
The program source file must include at the top the author's personal information (name and student ID) within comments. For example:
;;;----------------------------------------------------
;;; ITESM CEM, November 12, 2013.
;;; Clojure Source File
;;; Activity: Third Quarter Term Exam
;;; (Ring of primes)
;;; Author: 1166611 Anthony Stark
;;;----------------------------------------------------
.
. (The rest of the program goes here)
.
Write a report of at least 300 words in which you describe how you solved the problem, the results of the time measurements and your conclusions. Include also at least one chart (bar chart, line chart, etc.) in which the speedup improvements can be clearly observed. The report must be presented as a PDF document called report.pdf.
Place both files (exam3.clj and report.pdf) in a tarball file called exam3.tgz. From a terminal, you can use the following command to create this file:
tar czf exam3.tgz exam3.clj report.pdf
Using the Online
Assignment Delivery System (SETA), deliver the file
exam3.tgz. No exams will be accepted through
e-mail or any other means.
Due date is Tuesday, November 12.
| 35% | The implementation gives the correct result. |
|---|---|
| 35% | The implementation produces an observable speedup (Sp ≥ 1.2) when running the function with multiple threads in a multi-core system. |
| 20% | The written report contains all the requested elements. |
| 5% | Each function in the Clojure source file contains a short documentation string. |
| 5% | The source file contains within comments the authors' personal information. |
| DA | In case of plagiarism or any kind of fraud. |