15-451/651: Algorithms

Spring 2015

Historically, the average grade in this class has been a B. Given the class' quality of work this may increase or decrease.

Homeworks 30%Quizzes (online) 10%Midterm exams (in class) 30%Final exam 30%

- Everyone is expected to go to their recitation section. Remember, in most of the recitations, there are in-recitation quizzes, which are worth points.
- Recitations are a chance to engage in more discussion than is usually possible in a large lecture, with a focus on the process of solving algorithmic problems. Recitations will occasionally contain new material as well, on which you may be tested.

- There will be two midterms and one final exam
- Each midterm will be offered in class
- The final exam will be during the finals period for the semester

- There will a quiz online most weeks.
- You will be tested on the material from the previous 2-3 lectures.
- Quizzes are designed to be easy, assuming you are keeping up with the lectures.

- All written homeworks should be submitted electronically via autolab. Due dates are generally on Thursdays, 11:59PM.
- All written homework must be typeset and submitted electronically via Autolab. LaTeX (see Miktex for Windows machines) is a good typesetting system for documents with lots of math; you probably know it from taking 15-251.
- Each individual student has four (4) mercy days over the course of the semester to extend the deadline for written homeworks.
- At most two (2) late days may be taken on a single written assignment. After two days, no submissions may be made.
- You may work in groups of 2-3. However, each person should hand-in their own writeup. That is, collaboration should be limited to talking about the problems, so that your writeup is written entirely by you and not copied from your partner. You should wait a reasonable period of time between collaborating and writing up your solutions. In addition, list all members of your group on your written HWs.
- If you use any reference or webpage or a solution from any other class (including past iterations of 451), you must cite it.

Algorithms is a pivotal course in computer science undergrad studies. The course's goal is to give you the basic principles in analyzing and designing of algorithms. It is not an easy course (not that other courses taught in CMU are easy!). It will require a significant amount of work on your part to follow what is taught in class. This is why we give weekly homework assignments. They are designed to give you a better understanding of the material taught in class. We stress that the homework is meant for you. We devote a fairly large amount of time for designing, writing, grading and explaining the homework, so that you can test yourselves and see how well you understand and implement the course's material.

- Read the material taught in class, and make sure you understand all the definitions, algorithms, theorems and proofs.
- Read the homework.
**Carefully.** - Spend at least one hour thinking about each problem by yourselves. This is the vital part of
understanding the course's material. You will get stuck, that's ok. When you do, here are
some suggestions to help you get past it.
- Come up with a dummy example, over a small number of item, and try to solve it. This is particularly helpful when you're trying to follow an algorithm, or when devising a counter example.
- Which algorithms / techniques / heuristics taught in class are applicable to the problem at hand? When do they fail and for what reason?
- Reduce the problem to a problem taught in class. Can the problem be represented as a graph? a network? maybe to a less general instance of the problem itself (a graph with negative weight to a graph with unique, non-negative weights)?
- The notion of sub-problem (divide-and-conquer, dynamic programming, induction) is a recurring theme in this class. Try to identify and solve the sub-problems of the problem at hand.

- Only after you gave the problem a serious amount of thinking, try to collaborate, ask on Piazza, or come to the TAs for guidance.
- Write down the solution, by yourselves. Re-read what you've wrote. Make sure the solution is exact, and answers specifically what you've been asked about. It should be clear, but it need not necessarily be long.

- Make-ups for the exams and the final must be arranged at least one week in advance, barring extreme situations. Make sure to document any health problems you might have. If you need special accommodations, please contact Prof. Adamchik as early as possible.

- We will assume that you understand the issues and do not need an explanation here. Issues will be handled in accordance with the University Policy on Academic Integrity.

Finally, feel free to contact any member of the course staff to clarify these policies.