4020 Homework Guide

Homework in Computer Algorithms

Homework Submission, Late Homeworks:
Homework should submitted on LMS as a pdf file, and also a printout must be handed in at the beginning of lecture on the day it is due. If you want to receive a grade for your homework, you must turn in a physical copy; as long as you turn it in on LMS on time, you can turn in the physical copy late without penalty. If a solution to a problem requires multiple pages, these should be stapled together. The homework should be typed, although you can include hand-drawn formulas or figures.

I highly suggest learning and using LaTeX to format your homework. For some resources, I recommend a LaTeX tutorial; for actual writing I suggest either installing MiKTeX or using an online editor like Overleaf. LaTeX abilities will be useful for you far beyond this course, so it is well worth learning.

Homework should be handed in at the beginning of lecture on the day it is due. Any homework turned in after this point will result in a 50% grade reduction, and no homework will be accepted more than one day late, except in the case of a genuine emergency.

Writing Proofs and Algorithms:

• You are required to prove your statements, unless otherwise specified. If a homework or exam question asks you to design an algorithm for a certain task, then the answer must consist of a description of the algorithm (an English description is fine), as well as an analysis of its running time and a proof of its correctness. You should try to make your algorithms as efficient as possible.
• Many of the questions from the textbook consist of mostly English description, without much mathematical notation. This requires you to take a problem described in free text, and formalize it before solving it. Look at the "Solved Problems" in the textbook to see examples of this process.
• The best way to explain an algorithm is usually in English, with some mathematical notation. Some pseudo-code together with an English explanation is also fine. Solutions that simply give a long piece of pseudo-code without an explanation, however, tend to contain mistakes, and be very hard to understand. We reserve the right to deduct points for such solutions, even if they turn out to be correct.
• You should write up both your algorithms and your proofs clearly and neatly, as this will make your solution easier to understand, and will earn you more partial credit.
• You are allowed to use any result that is proved in class or in the textbook in your solutions, without having to re-prove this result (in other words, you can just cite the textbook in your solution).

Working Together:

You are allowed to work with a partner; each pair of students can submit just one copy of a homework together, as long as each of the pair writes up one of the homework problems. In addition to your partner, you are allowed (and encouraged) to discuss homework problems with other members of the class, and to formulate ideas together. There is no penalty for working in groups. However, every pair must write up their assignments separately, and include the list of "collaborators" that you discussed the assignment with. Make sure that you spend a lot of time thinking about the problems yourself and writing up the solutions; students who only follow their partner's lead will find the exams much more difficult.

You may not copy (or near-copy) a solution from another. Failure to write the solution to a homework completely on your own will be considered a breach of academic integrity, and may result in the final grade being reduced by a letter and a 0-grade for the homework for both parties. No collaboration is allowed during exams. It should go without saying that collaborating with people not taking this class, or using any resource other than the class textbook or notes, is a serious breach of academic integrity and will be punished severely.