Sc10-student-contest
From Education
Contents |
The Problems
Some of the problems here may take some programming knowledge, some might take some systems knowledge, and some may take some knowledge outside of traditional CS. Solve them to the best of your ability, but for every problem you attempt, make sure to write down where you've gotten. The primary deliverable for all of these problems is a short write-up describing what you did, what you learned, how you could have done better, and anything else you think might help the graders.
Put this writeup, along with any source code and anything else the problem asks for, into its own folder on your team's USB drive and hand this in at or before 5:00 PM Central Time.
Send any questions to contest@sc-education.org.
Submitting Results
- Each team will be given a blank USB drive during the contest. At 5pm each team will turn-in their USB drive with the following information.
- The root directory of the USB drive must contain exactly one file named README
- The first line of this file must contain the team name and contact telephone number(s) and email address for the team leader (not the coach). This is the person the organizers will contact if there are questions about the team's results submission.
- Subsequent lines in the file should contain the name and grade of each member of the team (one line per team member). For grade use the following coding:
- For Middle School: MS-5, MS-6, MS-7, MS-8
- For High School: HS-9, HS-10, HS-11, HS-12
- For Community College: CC-13, CC-14, CC-15, etc
- For Four Year: 4Y-13, 4Y-14, etc
- For Grad School: GS-1, GS-2, etc
- The root directory of the USB drive must contain exactly one problem directory for each attempted problem, with the directory name exactly corresponding to the name of the corresponding problem.
- Each problem directory must contain a file named README, as well as whatever other files and subdirectories the team chooses to convey their solution to the problem.
- The problem README file must contain a coherent and succinct description of the solution and a description of the contents of the directory for the problem.
- If you write software as part of a solution to a problem please include the source(s), the binary, and a note about the platform it was built for.
The Case of the Dutiful Drunken Dude
There is this dude, Sissy Fuss the Greek, with this lifetime gig that's a royal pain in the you know what. Anyway, he found a way to change jobs, but the dude needs your help to figure out how long it is likely to take. We don't know many details on the new job yet, but we've heard it does involve drinking a coffee liqueur and milk (don't try this at home kids), random walking, big rocks and probability.
This problem involves many aspects of computer science, mathematics and problem solving. At its heart though it is a problem about algorithm. The successful algorithm will not only be correct, but will finish running in the allotted time.
Problem Description
The dude's world is a 3x3 grid laid out on the side of a hill where he starts out in the center. There are these three big boulders, one in each of the 3 bottom square of this grid. He has to move each one up to the top row of the grid where there are three pedestals, one in each of the top squares. The dude is made to drink a quart of Kailua and milk each morning to disorient him, ensuring he moves randomly to an adjacent square, no diagonal moves since he's not wearing a miter. He can only move into one square each day. If he ends up in a square with a boulder and he is not carrying one, then he picks it up. If he ends up in a square with an empty pedestal and he is carrying a boulder, this is the only time and place he sets it down. Luckily, the pedestal has a permanent quick-set cement, which both prevents the boulder rolling back down the hill and prevents the dude from ever picking it up again.
How many days (to ten decimal places) is it likely to take the dude to complete this task?
Technology
- Required tools
- Programming ability in C or Fortran
- Knowledge of probability and statistics
- Suggested tools
- Knowledge and use of MPI/OPenMP/Cuda would allow for early completion, if
you have a parallel algorithm
- Numerical Analysis understanding of various kinds of error and management
of that error
Grading
- In a folder named "DrunkenDude" on your team's USB drive:
- Program solving the problem
- wallclock time of each solution
- Numerical error analysis of each solution
- What the graders will be looking for.
- Your report should include a description of the steps taken by the team in
working to obtain results. State the problems encountered, the possible solutions considered and tried, and the solution that was used.
- Discuss any problem encountered in getting ten digits of accuracy
- Discussion of algorithmic and programming tactics taken to minimize
wallclock time without unduly affecting accuracy and precision of your code
- Your report should also include observations on additional steps that
might be taken to improve the accuracy and/or speed of execution of your code, were you to have more time.
Extra Points
Solve the similar 5x5 or 7x7 problem. Solve to 20, 30, 40, or 50 places.
Folding, but not your laundry
This problem is based on the processes and chemistry used by chains of amino acids to "fold" into proteins. The structure of the problem is from Project Euler Problem 300, you should become familiar with their description before proceeding.
Generalized double pendulum
You'll be asked to examine the behavior of the motion of "n" coupled pendulums.
Ising on the Cake
The Ising model is one of physics’s simplest yet most successful models. It consists of a d-dimensional lattice of binary spins (up/down), and a Hamiltonian. Probabilistic methods, such as Monte Carlo, are commonly used to come to numerical solutions. Your task will be to study the thermodynamic behavior of ising models of large systems using numerical methods.
How fast can you run
Often the best way to compare two or more computational resources is to analyze how quickly and efficiently they can each solve a given problem. Some of these applications give better light into the resource's performance than others. Be prepared to use some common benchmarking tools.
top500.org is the canonical list of the fastest computers in the world, with the most recent version of it released on Sunday. How do they figure out how to rank the machines? They measure how much work each machine can do. In order to make sure every center measures their machine in the same way, they're asked to run the same benchmarking program. For the top500 list, this is HPL, High Performance Linpack.
You should download, compile, and run HPL on a handful of Al-Salam nodes.
For your deliverable, you should give us your:
- HPL.dat
- HPL.out; and
- a write up, potentially addressing these issues:
- What do all the numbers in HPL.dat mean?
- How do the results in HPL.out connect to those numbers?
- How do you think you could have gotten better results, given more time?
The Machines
You're being given access to the following machines for use for the contest:
- The Intel Many-core Testing Lab (MTL)
- Earlham College's Al-Salam cluster
