### Submitting homework assignments

- All homework assignments that require detailed solutions (i.e., questions are not multiple choice) must be typewritten and submitted using TurnItIn.
- Late submissions will not be accepted.
- To offset the rather stringent policy regarding late submissions, we will drop the 6 lowest problem scores over the course of the term. We expect to assign about 26 problems during the term and only the highest 20 scores will count towards the final grade. (This is equivalent to dropping a bit more than one full assignment.)

### Homework Format

**You must submit only typeset solutions.**This is a hard requirement but it serves two purposes. We will almost certainly be able to read your solutions and you will be able to distill the solution to its essentials when you go from handwritten notes to a typewritten solution.- We strongly recommend that you use LaTeX to typeset your solutions although Microsoft Word or Google Docs (and similar tools) may also be acceptable depending on your proficiency with the chosen tool.

### How to Write Solutions

**Write carefully.**We can only mark what you write, not what you mean. We will not attempt to read your mind.**Write sensibly.**You may lose points for poor spelling, grammar, punctuation, arithmetic, algebra, logic, pseudo-code and so forth. If we cannot decipher your solution we cannot give you credit.**Give generic solutions, not just examples.**In particular, don’t describe the first two or three iterations of your algorithm and then write “and so on”. Solutions that include phrases like “and so on”, “etc.”, “do this for all X”, or “…” will get no credit. Those are clear signals that your algorithm should have used a loop or recursion, or that your proof should have used induction, but did not**Write top-down, breadth-first solutions.**Describe the key ideas behind your solution before going into details. The reader should understand your approach almost immediately. An incomplete solution that includes all the main ideas but omits some details is worth far more than a complete, correct, detailed, but opaque solution. Even the most complex homework problem in this class can be answered completely in at most two typeset pages (or about five handwritten pages); most problems will require considerably less. Simliarly, even the most complicated exam problem can be answered completely in less than a single hand-written page.**State your assumptions.**If a problem statement is ambiguous, explicitly state any additional assumptions that your solution requires. (Of course, you should also ask for clarification in class, in office hours, or on the online discussion forum.) For example, if the performance of your algorithm depends on how the input is represented, tell us exactly what representation you require. If your solution to a recurrence assumes a particular base case, tell us what base case you require.**Do not submit code.**Describe your algorithms using well-structured, human-readable pseudocode. See the lecture notes and recommended textbook for examples of the type of presentation we want. Your description should allow a competent programmer*who has not taken this course*to easily implement your algorithm in*their*favorite programming language. We want to see your ideas, not syntactic sugar.**Omit irrelevant details.**If the same algorithm works equally fast whether the input is an array, a singly linked list, a doubly linked list, or a binary tree, try to describe it so that a competent programmer can easily use any of these data structures. If your homework solution is longer than two typeset pages, you have included too many details.**Do not babble.**A crucial part of mastering any new material is learning to recognize when you do not know something. Do not try to bluff your way through; if you do not know the answer, just say so.**Answering “I don’t know” (and**Synonyms like “No idea” or “WTF” or “知りません” or “أنا لاأعرف” are also acceptable, but you must write*nothing*else) to any homework or exam question is automatically worth 20% partial credit for that question.*something*; a blank page is worth zero points. Readable, correct, but suboptimal solutions are*always*worth more than 20%. This rule does not apply to extra credit problems (if any).**Do not regurgitate.**If your answer is a simple modification of something we’ve seen in class, just say so and (carefully!) describe the changes. For example, if the complete and correct answer appears on page 6 of Jeff’s lecture notes on recursion, the*best*solution you can submit is “See page 6 of Jeff’s lecture notes on recursion.” The same goes for any material presented in the actual lectures or previous exams and homeworks**from this semester**. Vomiting will cost you points. If your answer comes from*any*other source, you must write the solution in your own words and cite your source; see below.**Write**We*everything*in your own words, and properly cite*every*outside source you use.*strongly*encourge you to use*any*outside source at your disposal, provided you use your sources properly and give them proper credit. If you get an idea from an outside source, citing that source will not lower your grade. Failing to properly cite an outside source—thereby taking credit for ideas that are not your own—may result in a zero on the homework, or worse.Sources that you may use but must cite include textbooks, journal papers, conference papers, newspaper and magazine articles, web pages, blog postings, tweets, Wikipedia, newsgroup postings, lecture notes from other algorithms classes, official homework solutions from previous offerings of EECE 320, other students in EECE 320, other students not in EECE 320, whiteboards that someone forgot to erase, and your mom. The only sources that you do*not*need to explicitly cite are official course materials (lectures, lecture notes, previous homework and exam solutions from this semester) and sources for prerequisite material (which we assume you already know).**List everyone you worked with on each homework problem.**Again, we strongly encourage you to work together, but you must give everyone proper credit. If you work in a group of 20 students, then all 20 names should appear on your homework solution. If someone was particularly helpful, describe their contribution. Be generous; if you are not sure whether someone should be included in your list of collaborators, include them. For discussions in class, in section, or in office hours, where collecting names is impractical, it is okay to write something like “discussions in class”.**In particular, if you find a complete solution on the web, do not just copy and paste the solution.**The assignments are supposed to demonstrate your mastery of the material, not your ability to use Google.

### What to Write

**Answer the right question.**No matter how clear and polished your solution is, it is worthless if it does not answer the question we asked. Make sure you understand the question before you start thinking about how to answer it. If something is unclear, ask for clarification! This is especially important on exams.**Justify your answers.**Unless the problem specifically says otherwise,*every*homework problem requires a proof. Without a proof, even a perfectly correct solution is worth nothing. In particular, the sentence “It’s obvious!” is not a proof—’obvious’ is often a synonym for ‘false’! (Proofs are only required on exams if we specifically ask for them.)- By default, if a homework or exam problem asks you to describe an algorithm, you need to do several things to get full credit:
- If necessary,
**formally restate the problem**in terms of combinatorial objects such as sets, sequences, lists, graphs, or trees. In other words, tell us what the problem is*really*asking for. This is often the hardest part of designing an algorithm. **Give a concise pseudocode description of your algorithm.**Don’t regurgitate, and don’t turn in code!**Describe a***correct*algorithm.**Justify the correctness of your algorithm.**You usually won’t have to do this on exams.**Analyze your algorithm’s running time.**This may be as simple as saying “There are two nested loops from 1 to*n*, so the running time is O(*n*²).” Or it may require setting up and solving a summation and/or a recurrence, in which case you’ll also have to prove your answer is correct.**Describe the fastest correct algorithm you can**, even if the problem does not include the words “fast” or “efficient”. Faster algorithms are worth more points; brute force is usually not worth very much. We will not always tell you what time bound to shoot for; that’s part of what you’re trying to learn.**However, if your algorithm is incorrect, you will not get any points, no matter how fast it is!**

Some problems may deviate from these default requirements. For example, we may ask you for an algorithm that uses a particular approach, even though another approach may be more efficient. (Answer the right question!) Some problems may ask you to analyze the space used by your algorithm in addition to the running time. Exam problems will rarely ask for proofs of correctness.

- If necessary,

(These policies are minor modifications of Jeff Erickson’s policies at UIUC.)