Guidelines for presenting an algorithm as a solution to a problem:

1. Brief, informal, intuitive description. A line or two of English.

2. Detailed description. Mostly English, but may include well-documented pseudocode

and diagrams.

3. Proof of correctness - this means that for all inputs for which this program terminates,

the algorithm gives the correct corresponding output. Sometimes this can be included

in the detailed description if worded appropriately. Usually best to add separately.

Mostly English, math and diagrams.

4. Proof of termination - this means that the algorithm will terminate on all inputs.

Usually trivial, sometimes not. Make sure one way or the other.

5. Analysis of time and space complexity. Upper bound on the worst case is what we

seek in general.

Computer science is the only scientific community that considers conference publica- |tion as the primary means of publishing our research results (rather than journals): http://cacm. acm. org/magazines/2009/5/24632-conferences-vs-journals-in-com fulltext. In other disciplines, a publication" means a paper has appeared in what is known a refereed" and indexed (by an officially recognized body, such as the Web of Science) journal. So in computer science, the conference publications are reviewed (by volunteer researchers, such as your professors, for the so-called honor of having a line in your resume that says they served as a member of the conference Program Com- mittee). Suppose a conference receives n paper submissions and there are m members of the Program Committee. The Program Committee members then bid on which pa- pers they can and are willing to review2. After that, reviewers are assigned to papers (from among those they bid on) so that each paper has, lets say, at least 3 reviewers and each reviewer reviews at most, lets say, 5 papers. (The reviewers collective scores then decide whether a paper is accepted for the conference or not. Typically, for a good conference, only about 20% of the papers are accepted.) Design and analyze a polynomial-time algorithm to make the assignment of reviewers to papers (so that each reviewer reviews only the papers they bid on and the min and max constraints are resp decide that no feasible assignment exists. Computer science is the only scientific community that considers conference publica- |tion as the primary means of publishing our research results (rather than journals): http://cacm. acm. org/magazines/2009/5/24632-conferences-vs-journals-in-com fulltext. In other disciplines, a publication" means a paper has appeared in what is known a refereed" and indexed (by an officially recognized body, such as the Web of Science) journal. So in computer science, the conference publications are reviewed (by volunteer researchers, such as your professors, for the so-called honor of having a line in your resume that says they served as a member of the conference Program Com- mittee). Suppose a conference receives n paper submissions and there are m members of the Program Committee. The Program Committee members then bid on which pa- pers they can and are willing to review2. After that, reviewers are assigned to papers (from among those they bid on) so that each paper has, lets say, at least 3 reviewers and each reviewer reviews at most, lets say, 5 papers. (The reviewers collective scores then decide whether a paper is accepted for the conference or not. Typically, for a good conference, only about 20% of the papers are accepted.) Design and analyze a polynomial-time algorithm to make the assignment of reviewers to papers (so that each reviewer reviews only the papers they bid on and the min and max constraints are resp decide that no feasible assignment exists