CSC352 Homework 1

Parts 1 and 2 of this homework are due on 2/9/10. Part 3 will be due 2/11 (it requires one full lecture of Python and treads). Submit all the parts electronically using your 352 accounts, and the submit command.

Feel free to work on Part 3 in a group. I am not worried about your sharing solutions for this part. I am more interested in your exploring different approaches and understanding the trade-offs that face you. Because we do not have TA to help you out with this programming assignment, feel free to rely on each other for help with debugging threads and thread programming.

Problem #1

Why am I asking you to read the first six section of John Von Neumann's First Draft Report on the EDVAC?

Write up your answer (at most one page) in pdf form in a file called part1.pdf and submit it electronically from your

352 account this way:

  submit hw1 part1.pdf

Problem #2

After having discussed the [View from Berkeley] paper, rewrite your summary, and make it more precise. For the 1/2 page summary, pick on what you think are the most important message(s). You are free to submit the same summary as the one you submitted on 1/2/10 if you feel you had already answered this part.

  submit hw1 part2.pdf

Problem #3

Take the threaded N-Queens problem and find a different approach to parallelize it.

The version that was given to you in class launches N new threads, Thread i starting by putting the first queen on Row 0, Column i, with i ranging from 0 to N-1, until one thread finds a solution. Figure out another way to find a solution. Remember, you could decide to use fewer threads, in which case you'd explore the solution tree in less breadth, but you'd go faster in depth... Or you could start more threads, exploring the tree slower in terms of depth, but faster in terms of breadth... Maybe... :-)

Figure out a different approach, run it, and compare its execution time to the threaded N-queens we saw in class.

In order to do so, you will have to measure the timing of your version and compare it to the timing of the class N-Queens for several values of N.

Here's an example for timing the execution of the N-queens problem. You can adapt it to measure the execution time of your version. The information is taken from http://www.cyberciti.biz/faq/bash-for-loop/

• create a text file in the directory where you have your N-queens problem. Call it timeIt.sh

#! /bin/bash
for i in {10..20}
do 
    echo "-----------------------------------"
    echo $i
    python threadedNQueens.py $i | grep "processor time"
done

• make the file executable

   chmod +x timeIt.sh

• run the file

   ./timeIt.sh

• observe the output

-----------------------------------
10
processor time:     0.023224 sec
-----------------------------------
11
processor time:     0.02232 sec
-----------------------------------
12
processor time:     0.094016 sec
-----------------------------------  
...

• Adapt this to your needs so that you can plot the average of 3 runs of your version of the N-queens to the average of 3 runs of the the class version of the N-queens problem, for N ranging from 10 to 20.

The answer to this problem should be a pdf containing 3 parts:

1. a one-paragraph description of your solution
2. the listing of your program's main class (not the whole program)
3. the plot of the execution time comparing your program to the class program.

  submit hw1 part3.pdf