4003-531-01/4005-735-01 Parallel Computing I
Graduate Team Project

Team Formation
Team Proposal
Team Presentation 1
Team Presentation 2
Team Deliverables
Grading
Absences
Late Submissions
Plagiarism

Graduate students taking the course as section 4005-735-01 will do a team project in a two- or three-person team. You get to pick your own partners. You must do the following by 11:59pm Wednesday 13-Mar-2013:

1. Pick your partners. I would strongly prefer three persons on each team. I will accept two persons on a team if necessary; for example, if N ≢ 0 (mod 3), where N is the number of graduate students in the class.

2. Pick a name for your team.

3. Set up a web site for your team. You may use the web site in your CS account (public_html directory) or another publicly accessible web site. The web site home page must list the team name and the team members.

4. Post your team proposal on your web site. See Team Proposal below.

5. Send me an email giving the team name, the names of the team members, the email addresses of the team members, and the URL of the team web site.

Team formation is worth 4% of your final course grade. If you complete the above steps by the deadline, you will get 4%. Otherwise, you will get 0%; furthermore, I will assign you arbitrarily chosen partners.

The graduate team project is to solve an NP problem using an exhaustive search algorithm. An exhaustive search algorithm looks at every possible configuration of the problem, and chooses the configuration that solves the problem, if any. An NP problem, informally speaking, is one where the number of configurations is an exponential function of the problem size.

For example, graph coloring is an NP problem. Given a graph with V vertices and E edges, and given K different colors, the graph coloring problem is this: Is it possible to color each vertex with one of the K colors, such that no two adjacent vertices (no two vertices joined by an edge) have the same color? A configuration of the graph coloring problem is an assignment of a particular color to each vertex. There are K^V possible configurations; this is an exponential function of the graph size (V). An exhaustive search algorithm generates all possible configurations; if there is some configuration where no two adjacent vertices have the same color, that configuration solves the problem; otherwise, there is no solution. Here is a graph with V = 6 vertices and one of the configurations that solves the graph coloring problem for this graph with K = 2 colors:

You must pick an NP problem to solve.

• The problem must require large amounts of computation, so that a parallel program could potentially speed up the solution.

• You may not pick the graph coloring problem, because I will be doing that problem in class as a case study.

• Each team must pick a different problem. I will announce each team's chosen problem on the course web site.

You must do a literature search, identify three research papers that describe algorithms for solving your chosen NP problem, and analyze these papers.

• The papers must be published in refereed archival journals or conferences; that is, publications aimed at researchers. Be careful; not every publication meets this criterion. If you are not sure whether a particular publication meets this criterion, please ask me.

• I would strongly prefer papers that describe parallel algorithms for solving your problem. Papers that describe non-parallel algorithms are acceptable only if you cannot find any papers that describe parallel algorithms.

You must write a sequential program in Java to solve the problem with an exhaustive search. You must also write a parallel program using Parallel Java to solve the problem with an exhaustive search. You may write an SMP parallel program or a cluster parallel program. You must measure and compare the performance of the sequential and parallel versions. (You will not implement algorithms from the research papers.)

Write a proposal for your team project. The proposal must be at most two pages long. The proposal must be in the form of a PDF file. Post the proposal on the home page of your team web site. The proposal must include the following information:

• A description of your NP problem.

• A description of the exhaustive search algorithm for your problem.

• A description of the sequential and parallel programs you plan to deliver.

• A description of the performance metrics you plan to measure.

• Complete citations to the three research papers you plan to analyze.

• Complete citations to any papers, books, web sites, etc. with information about your problem that you plan to use.

I will not accept your team proposal unless it appears on the home page of your team web site. I will not drill down past the home page to try to find your team proposal. If your web hosting provider doesn't let you put documents on the home page, host your web site somewhere else.

The team will give their first presentation in class during week 5 of the course. Specific dates and times for each team's presentation will be assigned later.

The team must give prepared slides (using PowerPoint, LibreOffice, or the like) and must respond to questions from the audience. All team members must participate in the presentation. You must also post the prepared slides on the home page of your team web site before the class session in which you give your report, in the form of a PDF file. You may post other versions of your slides as well (e.g. PowerPoint or LibreOffice).

You will project your slides using the classroom's PC projector. You may use your own laptop. If you don't have a laptop, borrow one.

Cover the following items in your presentation. You will have a maximum of 10 minutes for your presentation.

• Introduce the team members.
• Describe your NP problem.
• Describe the exhaustive search algorithm for your problem.
• Give a brief demo of your sequential program for your problem, on a small instance of your problem.

Note that you must have a working sequential program by week 5.

The team will give their second presentation in class during week 10 of the course. Specific dates and times for each team's presentation will be assigned later.

The team must give prepared slides (using PowerPoint, LibreOffice, or the like) and must respond to questions from the audience. All team members must participate in the presentation. You must also post the prepared slides on the home page of your team web site before the class session in which you give your report, in the form of a PDF file. You may post other versions of your slides as well (e.g. PowerPoint or LibreOffice).

You will project your slides using the classroom's PC projector. You may use your own laptop. If you don't have a laptop, borrow one.

Cover the following items in your presentation. You will have a maximum of 20 minutes for your presentation.

• Introduce the team members.
• Briefly describe your NP problem.
• Briefly describe the exhaustive search algorithm for your problem.
• Describe the algorithm from your first research paper.
• Describe the algorithm from your second research paper.
• Describe the algorithm from your third research paper.
• Describe the design of your parallel program.
• Give a brief demo of your parallel program for your problem, on a small instance of your problem.
• Describe the performance metrics you measured.
• Discuss what you learned from your investigation.
• Discuss future work that could be done to further your investigation.

You must post the following items on the home page of your team web site. These team deliverables will be graded and must be posted by 11:59pm Wednesday 01-May-2013.

• A final report, in the form of a PDF file, including:
  • A description of your NP problem
  • A description of the exhaustive search algorithm for your problem
  • A description of the algorithm from your first research paper
  • A description of the algorithm from your second research paper
  • A description of the algorithm from your third research paper
  • The high-level design of your sequential program
  • The high-level design of your parallel program
  • A developer's manual for your software (i.e. exact instructions for how to compile the software)
  • A user's manual for your software (i.e. exact instructions for how to prepare the input, how to run the software, how to interpret the output, etc.)
  • The performance metrics you measured for your parallel program
  • A discussion of what you learned from the project
  • A discussion of possible future work
  • A statement of what each individual team member did on the project
  • List of references

• All software design descriptions, source code, test cases, input files, output files, test results, and so on that you developed during your investigation. These must be posted in a single JAR file (Java archive file).

I will not accept your team deliverables unless they appear on the home page of your team web site. I will not drill down past the home page to try to find your team deliverables. If your web hosting provider doesn't let you put documents on the home page, host your web site somewhere else.

14% of your final course grade is based on the quality of your two team presentations. All team members will receive the same grade for each presentation. I will grade each presentation on a scale of 0 to 10, with 10 = outstanding, 1 = unacceptable, and 0 = absent. However:

• If your prepared slides are not posted on the home page of the team web site in the form of a PDF file before giving the report in class, I will deduct 5 points from the presentation grade.

• Each presentation will be allotted the amount of time stated above. I will give a warning 3 minutes before the end of the allotted time. If you are not finished with your presentation in the allotted time, I will cut off the presentation, and I will deduct 2 points from the presentation grade. Plan your presentation and delivery so you will be finished within the allotted time.

16% of your final course grade is based on the quality of your team's results as recorded in your team's final deliverables posted on your team web site. All team members will receive the same grade for deliverables. I will grade the deliverables as follows:

• [28 points] Team Report
  Each of these items will be assigned points as follows:
  2 = Satisfactory
  1 = Needs improvement
  0 = Missing
  • A description of your NP problem
  • A description of the exhaustive search algorithm for your problem
  • A description of the algorithm from your first research paper
  • A description of the algorithm from your second research paper
  • A description of the algorithm from your third research paper
  • The high-level design of your sequential program
  • The high-level design of your parallel program
  • A developer's manual for your software
  • A user's manual for your software
  • The performance metrics you measured for your parallel program
  • A discussion of what you learned from the project
  • A discussion of possible future work
  • A statement of what each individual team member did on the project
  • List of references
• [10 points] Software deliverables (source code, etc.)
  10 = Satisfactory
  8 = Needs minor improvements
  6 = Needs major improvements
  0 = Missing
• [38 points] Total

After I have evaluated each presentation and the deliverables, I will add your grade and any comments I have to your encrypted grade file. See the Course Policies and the Encrypted Grades for further information.

If you are absent from class when one of your team presentations is scheduled, you will receive a grade of zero for the presentation unless before the start of the class when the presentation is scheduled you make an alternate arrangement with me. I am normally willing to permit this only for absences due to illness or unforeseen personal emergency. However, if you feel you have a valid reason for your absence, please discuss it with me. Appointments, job interviews, career fairs, vacations, trips home, and other scheduled activities are not valid excuses for absence. You have an obligation to this course, and you must schedule other activities so as not to interfere with class sessions.

If your team proposal is not posted on your team web site by the deadline, your team proposal will be late and will receive a grade of zero.

If your team deliverables are not posted on your team web site by the deadline, your team deliverables will be late and will receive a grade of zero.

You may request an extension for posting your team proposal or team deliverables. See the Course Policies for my policy on extensions.

The team proposal, team presentations, and team deliverables must be entirely your team's own work. I will not tolerate plagiarism. If in my judgment the team proposal, team presentations, or team deliverables are not entirely your team's own work, you will automatically receive, as a minimum, a grade of zero for the assignment. See the Course Policies for my policy on plagiarism.

Cryptography • 4003-482-01/4005-705-01 • Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2013 Alan Kaminsky. All rights reserved. Last updated 04-Mar-2013. Please send comments to ark­@­cs.rit.edu.