Posted by: atri | November 26, 2007

Project Reports

The project reports are due on Tuesday, Dec 11 by 8am (the deadline for the scribed notes is midnight Dec 11). This is a hard deadline.

Here are some thoughts on my expectations for the project reports (in no particular order):

  • I do expect to see proofs in your report. However, the proofs should not be produced verbatim from the papers that you are surveying. Your contribution will be to give the reader the key ideas/intuition in the proofs. Of course it will not be possible for you to give detailed proofs for every result that you state. It is OK to just give the statement of some results: for example, proofs that are just routine calculations. Basically, you are expected to prove (or at least give a proofs sketch) of the important lemmas/theorems that you will mention in your report.
  • I am expecting a report of around 20 pages. This number is not a hard number. A report of around 18 pages is fine. Try to keep your report under 30ish pages if possible. Do not try to add material just for the sake of paper count: a shorter coherent report will be graded higher than a longer rambling report.
  • You do not need to prove/expand on results we have covered in class unless a detailed understanding of the result is necessary for the rest of your report to make sense.
  • The target audience for your report is a person who is comfortable with math (and may have some exposure to basic coding theory). So make sure that your report is accessible to such an audience. Among other things make sure that you motivate the general problem that you are considering well enough. If the reader is not convinced that the problem is interesting/important, the rest of your survey will be useless. Some part of your grade will depend on how accessible your report is to a general audience.
  • Please be precise in notation/definition. In particular, define any new term that you will be using (having a short description of the basic notions of codes would helpful for a reader who is not familiar with the coding notions).

If you have any comments/questions, feel free to use the comments section of this post.

Posted in projects

« Lecture 37: List Decoding of RS codes
Lecture 38: Guruswami-Sudan List Decoder »

Responses

One particular question, which may be specific to my project, on complexity-theoretic aspects of coding theory - can I assume the reader is familiar with the concept of NP-completeness?

By: Nathan Russell on November 29, 2007
at 6:00 pm

Sure. However, you should give pointers for readers who are not familiar with the concept to get more information. Along the same lines, spend a paragraph or so talking about NP-completeness and why it is a measure of “hardness” of a problem.

By: atri on November 29, 2007
at 7:24 pm

One other thing. I hesitate to ask this here, but it occurs to me that others might be wondering as well. What font does the 20 page figure assume? I’m going with the Lyx default font, and the default single spacing, but it’s difficult to read at the default size, so I moved the font size up to 12 point - is this problematic?

I felt it was better to err on the side of assuming single spacing, as well.

Thanks
Nathan

By: Nathan Russell on November 30, 2007
at 9:54 pm

To clarify, honestly, I don’t have that much written yet, and obviously I’ll do whichever the requirement is - I could at this point do either, and have the coverage in the paper even. I just can’t find where single or double spacing was specified.

By: Nathan Russell on November 30, 2007
at 10:10 pm

Well, I would say around 20 pages with single spacing with 11pt font.

If I were you I would not worry too much about the page limits, fonts etc. You should focus more on the content: as long as you are not way off the limit you should be fine. I put in the page limit as a guideline to make sure for example I do not get a 50 page report or a 10 page report.

By: atri on December 1, 2007
at 1:09 am

Thanks again.

I’ve really just been introducing concepts as I go along. So, for example, if I need to use a specific aspect of NP theory (or graph theory, or whatever) I will explain it quickly. One thing I’m not sure is where to cite really basic concepts to.

By: Nathan Russell on December 4, 2007
at 1:44 pm

For things like NP-completeness you can cite any standard complexity books.

By: atri on December 4, 2007
at 2:04 pm

That sounds great. I own both Garey and Johnson and CLRS, so I’ll just dig through there?

By: Nathan Russell on December 4, 2007
at 3:08 pm

By the way, I know this is turning into a long discussion, and I’d just email you except that I suspect other students are wondering some of the same things.

By: Nathan Russell on December 4, 2007
at 3:59 pm

Well, GJ is great for referring standard NP-complete problem. CLRS is good for algorithms but is not so good for complexity (though I guess it is fine for just NP-completeness). The standard text in complexity would for e.g. Papadimitriou’s book. Another option would be the upcoming book of Sanjeev Arora and Boaz Barak, which is online (it has not been published yet).

By: atri on December 4, 2007
at 4:09 pm

Thanks much.

By: Nathan Russell on December 4, 2007
at 6:59 pm

Leave a response






Your response:

Categories