Winter 2014

CS 252: Algorithms

Jadrian Miles

*Table of Contents*

**This class is a writing class.** A major component of your grade, and of the work in the course, consists of writing up solutions to computational problems. In addition to writing a description of each algorithm you submit, you will also provide an analysis of this algorithm. Thus your submission is a piece of writing, and it will be assessed not only for correctness but also for having a clear and logical structure, and for being organized, readable, and professional.

As befits a class that focuses (at least partly) on writing, I will expect you to have gone through multiple passes of drafting, editing, and revising of your work. Please try to turn in work that you are proud of: take the time to proofread it and format it nicely. You should think of each submission as a mini-essay, and exercise the same care that you would when constructing an essay for any other class outside the sciences.

Problem sets are assigned approximately weekly in this course, and typically consist of three problems. The problems are due one at a time, and you have your choice of the order in which you turn them in.

You are encouraged to collaborate with your classmates on assignments in ﬁguring out how to solve problems, but you must write your solutions yourself. For more details, please see the Collaboration Policy in the Syllabus. Please work with no more than two other people on a given problem; you won't learn as much working in a larger group. If you’re working with a group, read over and attempt the problems on your own before you meet. You’ll get more out of it, and so will your group. Remember that you must list your collaborators on every problem, and you may not work from notes generated in a collaborative session!

This section is an elaboration of the descriptions given in the Grading Rubric; please see that document for more discussion of how your work is evaluated.

Most homework questions ask you to give an algorithm to solve a particular problem. Some other problems instead ask you to prove particular properties of a given algorithm, or provide a counterexample to some claim, etc. When your answer to a question involves “giving an algorithm”, unless otherwise specified, a complete solution to that question consists of the following three things:

- a description of an algorithm to solve the problem;
- a claim of the algorithm's correctness, and a proof of that claim; and
- a statement of the algorithm's complexity (in time and, if requested, space), and a proof of that claim.

Unlike some other CS classes, you generally do not submit actual code or programs; instead you write things, like in a math class or most classes outside the sciences. *The quality of your writing matters*; specifically, your grade depends partially on the quality of your writing.

You may choose how you wish to present the elements of your solution (there are some recommendations below), but please keep in mind that your solution is evaluated for *correctness*, *style*, *clarity*, *precision*, and *conciseness*. What do these mean, exactly? Well...

- Correctness
- Your algorithm must produce the correct output for all valid inputs, as specified by the problem statement, and it must also satisfy all specified time or space complexity requirements. In addition, the statements that you offer as proof of the algorithm's correctness and of its complexity must
*themselves*be correct; that is, they must actually prove what you claim about the algorithm. - Style
- The presentation of your solutions should professional and direct. Imagine that you're directing your write-ups toward an outsider who's knowledgeable about algorithms but isn't in our class, maybe a CS professor at another college. The environment of our classroom and the style of the problem sets are generally pretty light-hearted, but please keep a professional demeanor in your write-ups.
- Clarity
- Your solution should be easy to understand. Your notation should be straightforward, and your prose should guide the reader clearly through the reasoning of your solution.
- Precision
- Your solution should be unambiguous to a reasonable and well-informed reader.
- Conciseness
- You should avoid unnecessary exposition and detail as much as possible. Use mathematical syntax or pseudocode in place of repetitive or long-winded prose. Do not describe the
*thought process that led you to a solution*; instead, simply state your solution. It is also usually unnecessary to provide examples when explaining your algorithm; if an example seems necessary, consider redesigning the logic of your algorithm to make it easier to follow.

Every solution you hand in must be typeset in LaTeX and exported to PDF. If you need some help getting started, I really like Andy Roberts's tutorials; your classmates, Google, and Wikibooks are also great resources. The department has TexWorks and TexShop installed on their machines, and the MacTeX package is great for running LaTeX on your own Apple machine. Many students also like to work in the writeLaTeX.com online editor.

Your submission must be on letter-size (8.5" x 11") paper — note that many LaTeX installs use A4-size paper by default, which is not appropriate for submissions. There should be an effective margin of one inch on the left and right sides of the main body of your submission. It's okay for hanging section labels to run into this margin if you desire. There should also be a margin of approximately one inch at the top and bottom of your text. Headers and footers may fall within this margin or may start an inch away from the page edge.

Every submission must have a header with exactly these contents:

<full_name> (<username>) |
Problem <X>.<Y> |
CS 252, Winter 2014 |

Time estimate: <T> minutes |
Collaborated with: <person_list> |

The header must be separated from the body of your submission by a horizontal line. The problem-set number (X) is between 1 and 9; each problem set is made up of up to three problems. The problem number (Y) is specified in the assignment; it corresponds to the order in which the problems are described, regardless of the order in which you turn them in. A “*person_list*” consists of either the string “no one” or a comma-separated list of pairs of full names and usernames in parentheses, just like the one for your name on the first line. If you talk to me, another faculty member, a student outside our class, or someone else, they still count; please credit them in your collaborator list. (Though it's okay to go over two collaborators in this case.)

Your typesetting must use text styling (fonts, spacing, alignment, etc.) to differentiate prose, mathematical variables, and pseudocode. Check Google or Wikibooks for pseudocode typesetting advice. Do not use especially small or large fonts; the default sizing used by the LaTeX “article” package is appropriate.

If you'd like to include a diagram, a hand-drawn one is acceptable.

Submit your solution to each problem as a PDF in the hand-in directory on your Courses network drive, with the following filename: `username-X.Y.pdf`, where X is the problem-set number and Y is the problem number.

The writing that you do for these problem may take the form of *prose*, *pseudocode*, or *math*, and often all three are required for a high-quality submission.

Pseudocode's main purpose is to support the precision and conciseness requirements of your solution. Pseudocode doesn't necessarily have to look much like regular computer code; sometimes it can be as simple as English prose with meaningful indentation. But avoid being long-winded when writing this way: a good general guideline is that no line of pseudocode should be as long as the width of your page. (And usually they should be *much* shorter!)

If you do write pseudocode, and it contains a lot of variables or sophisticated logic, provide a short prose explanation first. Talk about the big picture of your solution, describe the meaning of the important variables, and state any invariants that your algorithm maintains as it runs. (Note that this does *not* mean that you should describe the exact mechanics of your code in prose. Just describe the big picture; the prose should not be redundant with the pseudocode.)

I recommend that you explicitly divide the presentation of your solution into the three sections described in the "Contents" section above. Here's a template that serves people well:

You may assume that your inputs are always valid (that is, that they conform to the specification given for the problem), but you must not assume they are non-degenerate unless specified. Be careful about edge cases.

If you are given input and told that it has a specific property (that it is sorted, say, or that it is a spanning tree of a given graph), you do not have any guarantees about the process used to construct the input. Assuming that a particular process was used to construct it is an invalid line of reasoning. You should consider your inputs as handed down by an omniscient oracle.

By default, all indexing is assumed to be *1-based*; that is, an array *A* of length *N* has entries *A[1]*, *A[2]*, and so on up to its last entry, *A[N]*. (Same goes with strings, multi-dimensional arrays, lists of nodes in a graph, etc.) Really, you should always specify your indexing, but if you don't, I'm going to assume it's 1-based, and consider *A[0]* to be an out-of-bounds array access.

*A[n]* refers to the element at index *n* of array *A*. In contrast, *A[1...n]* refers to all values in *A* at indices from 1 up to *n*. We use the latter notation for declaring a length-*n* array, and also for implicitly specifying that *n* is the length of an array provided as an argument to a function.

Any result that we prove in class, or that we just state without proof in class, is fair game for use without proof in homework turned in after that result is covered (or on an exam, for that matter). For example, you can just say to use mergesort in your algorithm, and then state in your running-time analysis that “mergesort takes *O(n log n)* time”, without any further proof being necessary. Same goes for properties of algorithms that we prove or offer without proof; for example, “the Gale–Shapley algorithm returns a stable matching of its inputs” is a valid statement as part of a proof you write.

However, this is the only valid way to invoke material from class. Here are some common invalid approaches:

- It is not sufficient to only
*refer*to proofs we do in class. For example, “X is true for the same reason that Y [which we covered in class] is true” is not a valid proof of X. - A
*similarity*between your algorithm and one we covered in class is not sufficient evidence that it has similar properties. For example, “my algorithm X is similar to algorithm Y [which we covered in class]; since Y has property Z, X also has property Z” is flawed reasoning.

This means that if you modify the inner workings of a “textbook” algorithm, your proof of correctness (or running time) for this new algorithm must start from scratch, even if it is nearly identical to the proof of correctness (or running time) of the original algorithm. (An often preferable strategy, described below, is to modify the *inputs* to your algorithm so they can be operated on by the textbook algorithm.)

A note on tone: we're operating under a sort of creative fiction — our objective is to *report* a correct solution, not describe our *thought process* in designing it. You may feel a little uncertain about your work, but the style to aim for is concrete *statements*.

This means that you should use an active, constructive voice in describing your solution, rather than a passive or tentative one. Many people (and I am often one of them) tend to write things like “we could construct a graph to solve the problem. The graph would have such-and-so properties...”. Instead, it is preferable to just write: “construct a graph by following these steps...”.

One last suggestion: be lazy! A common algorithmic technique is to transform a given problem into an instance of a familiar problem, use a known algorithm to solve this auxiliary problem, and then transform the output into a solution for the given problem. This approach has three great benefits over rolling your own complete algorithm: it's often far easier to describe, for your reader to understand, and to prove correct. However, sometimes searching too hard for a lazy solution might take you down the path to an incorrect solution; carefully scrutinize your solution and try to find inputs that make it produce incorrect results.

Each submission will be graded on a five-point scale:

- 0: no genuine attempt
- 1: (incorrect) some good ideas but incomplete or incorrect
- 2: (incorrect) complete and close to correct, but makes mistakes or otherwise does not meet the requirements of the problem statement;
*or*algorithm is correct but analysis is incomplete - 3: (correct) fundamentally correct with major technical or presentation flaws
- 4: (correct) fundamentally correct with minor technical or presentation flaws
- 5: Solution-set-worthy

Answers to homework questions are not always supposed to be obvious to you — you should have to think and struggle to answer some of the questions. To calibrate your personal expectations: don’t worry if you can’t solve every problem! (Getting an A does not require solving all the questions.) Write up whatever progress you’ve made on each question. You will receive partial credit, especially for an answer like “Here’s where I got stuck. I can’t see how to ﬁnish the argument because x.” (On the other hand, getting an A does require solving most of the problems; just don’t panic if there’s a question once every two or three weeks that stumps you.) Getting a 5 is generally quite difficult to do; your work really has to be extraordinary to get that mark, and you should not feel that you fell short if you don't get it consistently.

As mentioned in the syllabus, these numbers are simply labels for categories and have no mathematical significance. The mapping from categories to numerical grades will be determined and announced later in the course, but generally having more 4s than 3s, and a lot more correct solutions than incorrect ones, is enough to get you an A.