CMSC 441 — Fall 2016 — C. S. Marron

Projects

Project Descriptions

• Project 1: Dynamic Programming

  • Project Description
  • You can generate random test data with the following command:
    
    cat /dev/urandom | tr -dc 'HGWT' | fold -w 10000 | head -n 1 > test1.txt
    
    Change 10000 to the length you want. On some Linux systems, you may need to change -w to -n.
  • Here is a file of sample data and the results produced by my code. For my program, I specify a data file and a number \(n\) of initial characters to process. So, for example, \(n = 100\) means "read the first 100 characters of the file and compute the maximum number of matchings from that string." The results file includes my answer for several values of \(n\).
  • Project rubric:
    1. Recursive formula for \(OPT(i, j)\) and proof of optimal substructure — 15 points
    2. Design of algorithm to compute the size \(|S|\) of a maximal line folding for a given input sequence — 15 points
    3. Design of algorithm to recover the maximal line folding \(S\) for a given input sequence — 10 points
    4. Analysis and asymptotic bounds for the algorithm to compute \(|S|\) — 15 points
    5. Implementation of algorithms — 20 points
    6. Empirical performance data and comparison with theoretical running time — 20 points
    7. Quality of writing — 5 points
  • When timing your implementation, you only want to time the dynamic programming portion, which is the computation of \(OPT(1, n)\). In particular, do not include the reconstruction code in your timings.
  • Your implementation must be able to run on GL.

• Project 2: Multithreaded Algorithms

  • Project Description
  • example2.c is a second, simpler example of using OpenMP. Note in particular the use of the omp_get_wtime() function.
  • example2.slurm is the slurm file that goes with example2.c. It requests a 16-core node (hpcf2013).
  • example.c — C program for use with example.slurm. Compile with icc example.c -openmp -o example
  • example.slurm — Sample slurm batch file. Submit with sbatch example.slurm.

Project Policies

You may work with a partner on your projects. If you choose to work with a partner, be sure that all submitted files are clearly marked with both students' names. Partners must work together on the entire project (milestones, if any, and final submission).

General Project Rules

1. You (and your partner) should try as much as possible to complete the project by yourselves.
2. You may get assistance only from your instructor or TA.
3. You must document all help that you receive.

Apart from working with your partner, you MAY NOT

1. Copy anyone else's code,
2. Have someone else write your code for you,
3. Submit someone else's code as your own,
4. Look at someone else's code, or
5. Have someone else's code in your possession at any time.

See the Acadmeic Conduct portion of the syllabus for more more informtion, including the penalties for academic misconduct.

Project Submission

Projects will be submitted on Blackboard.

Late Policy

The due date and time for each project will be found on the course schedule and in the project description. A project is considered late if even one of the submitted files is timestamped past the due date and time.

If a project is late, the following grade penalties will apply:

• Up to 24 hours late: 15 point reduction
• 24 to 48 hours late: 40 point reduction
• More than 48 hours late: no credit

All due dates and times, and assessments of late penalties, are firm.