# CS41 — Interesting Problems

## Intro

For the first few weeks of the semester while we are working on some math preliminaries, the class will be divided into teams, each of which will be assigned one of the interesting problems below. Your team will design an algorithm to solve your problem, implement it, analyze it's complexity, and present your solutions both in front of the class and in a written summary. The work should be done without reading ahead, or consulting other texts teams, students, or the internet.

Groups will be assigned by either yourselves or me and will not change for the duration of the project. Each week, each group will have a leader, recorder, and presenter. The leader should schedule meetings, and move meeting discussions forward smoothly. The recorder will be responsible for keeping notes and writing any reports that are to be submitted to me. The presenter will be responsible for giving in class progress statements.

By the end of the project, groups should have working code, an analysis of their algorithm, a discussion of the approach used including test data, and a discussion of things you might have liked to do but did not have time for.

CPU scheduling
You have recently been hired by a large data center to develop a new algorithm for scheduling jobs on a single processor. Clients can submit jobs to the data center. Each job a(i) takes a known time t(i) to process on a single CPU. Clients will pay for jobs you succesfully run, but only if the job is completed by a specified deadline d(i). If you succeed in completing a job before the deadline, you are paid and amount p(i), otherwise you are paid nothing. Suppose you are given a set of n jobs a(i)=<t(i), d(i), p(i)> and you want to maximize the profit you can obtain by scheduling the jobs. It may not be possible to schedule all the jobs and have them all finish before their respective deadline. Design an algorithm that will create a job schedule and maximize the profit. You may assume that all times, deadlines, and profits are integers. How long does it take for you algorithm to run? What parameters does the run time of your algorithm depend on, e.g., number of jobs, maximum profit, latest deadline, longest running job? How do you know if it is correct? Do you think your asymptotic running time is optimal?

Sum of n dice