This exam can be developed individually or in pairs.
Using Clojure, write the code to find a normal magic square of order n (n ≥ 1).
According to the definition in Wikipedia:
A magic square of order n is an arrangement of n2 numbers, usually distinct integers, in a square, such that the n numbers in all rows, all columns, and both diagonals sum to the same constant. A normal magic square contains the integers from 1 to n2.
Normal magic squares exist for all orders n ≥ 1 except n = 2, although the case n = 1 is trivial, consisting of a single cell containing the number 1.
The constant sum in every row, column and diagonal is called the magic constant or magic sum, M. The magic constant of a normal magic square depends only on n and has the value
M = n(n2 + 1)/2
You must provide two implementations of the solution to this problem:
magic/square-seq: A sequential implementation.
magic/square-par: A parallel implementation (using the pmap function or similar) that runs faster than the sequential implementation on a multi-core system.
You may define any number of additional auxiliary functions. Just make sure every single function contains a doc-string explaining its purpose.
The output of both functions should be the first solution found, using the same format as shown below (you can use Clojure's printf function to align nicely the numbers):
user=> (magic/square-seq 4) The sum of all rows, all columns, and both diagonals is 34. +----+----+----+----+ | 4| 14| 15| 1| +----+----+----+----+ | 9| 7| 6| 12| +----+----+----+----+ | 5| 11| 10| 8| +----+----+----+----+ | 16| 2| 3| 13| +----+----+----+----+
If there is no solution, the functions should just print "No possible solution".
Run your functions multiple times and measure how long they take to execute for different values of n.
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 11, 2011.
;;; Clojure Source File
;;; Activity: Third Quarter Term Exam (Magic Square)
;;; Authors: 456654 Anthony Stark
;;; 1166611 Steve Rogers
;;;----------------------------------------------------
.
. (The rest of the program goes here)
.
Write a report of at least 200 words in which you describe how you solved the problem, the results of the time measurements and your conclusions. Include also a chart (bars, lines, 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 (magic.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 magic.clj report.pdf
Your program will be personally assessed on Friday, November 11 during the class' time slot. Before this, you must upload the exam3.tgz file using the Online Assignment Delivery System (SETA). Only one person per team needs to do the upload.
| 35% | The sequential implementation solves the problem correctly. |
|---|---|
| 35% | The parallel implementation solves the problem correctly and produces an observable speedup. |
| 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. |