CS 473: Homework Policies


The course staff will have to critically examine several thousand pages of homework submissions before the end of semester! We desperately need your help to make sure homeworks are graded and returned quickly. If you have any questions or concerns, please don't hesitate to ask in lecture, during office hours, on the course newsgroup, or by email.

Logistics: How to submit

  • In extreme circumstances, we may forgive homeworks or even exams. Extreme circumstances include serious illness, injury, and research-related travel (for example, if you are presenting a paper at a conference). Please see professor for details.
  • Submit a paper copy of your homework in the homework boxes in the basement of Siebel Center. They are in the lower-level next to the snack machines. You should submit each question separately; one stapled copy per problem per homework in the appropriate box. So, for example if HW0 has 5 problems, then you should make 5 different submissions, one per problem. We highly recommend you typeset your homework, but alternatively you can use a tablet and write in free form, or write a solution on paper. If you are to typeset your homework, we strongly recommend you use latex.
  • For a single problem, a single submission per group suffices. It is not necessary that everybody in the group submits his/her own file separately.
  • It is not necessary to submit all the problems at once, you can do this gradually but of course before the deadline.
  • It is not necessary for all the problems of a homework to be submitted by the same member of the group. Different problems of a homework can be submitted by different members of the group.
  • It is OK that a group submits a single problem many times. While we collect all the submission, just state clearly which one is the final one.
  • You are not allowed to submit different problems of a single homework within different groups. Although we are not monitoring this constraint while you submit the problems, before we start to grade a homework we will carefully check for violations.
  • Scores and solutions will be made available on Moodle. Graded homeworks will be available during office hours and in discussion sections.

    Format: What to submit

    • You can use any typesetting software that you are comfortable with as long as it is mature enough to let you typeset a reasonable detail of mathematical formulas (like exponents, indices, greek letters, a solution for including figures when needed,...) so the grader can understand your mathematical symbols without any need for guessing.

    • LaTeX is by far the best system for typesetting mathematics (and you will be typsetting mathematics). TeXShop for Mac OS X, TeX Live for Linux (already included in many distributions), and MiKTeX for Windows are good options. We encourage you to use latex. We will provide you with a very simple latex template that you can use to typeset your solutions, as well as a very basic latex tutorial. You can read the tutorial here.

    • Clearly print/type your name(s), your NetID(s), the homework number, and the problem number at the top of every page. For example: "Chandra Chekuri (chekuri) HW0 #5". For group homework solutions, print the name and NetID of every group member on.

    Form: How to write

    In short, make it easy for the graders to figure out what you mean. If your solutions are difficult to read or understand, the graders will be less sympathetic to your mistakes. All this goes for exam problems, too.

    Content: What to write

    • Answer the right question. No matter how clear and polished your solution is, it's worthless if it doesn't 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'! (In exams we will indicate clearly whether we need a proof or not.)

    • 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.
      • Describe the most efficient algorithm you can. The more efficient your algorithm, the more points you get. 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!
      • Give a concise pseudocode description of your algorithm. But don't regurgitate! And don't turn in source code!
      • Justify the correctness of your algorithm. You may not have to do this on exams unless asked for.
      • 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(n2)." On the other hand, 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.

      Some problems may deviate from these default requirements. For example, you may be asked 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.


  • Webpage contents generously borrowed/copied from those of Jeff Erickson.