Course Policies

This document is a draft and subject to change for the first two weeks of the semester.

Grading

There will be two in-class midterms, and a final during the finals period. There will also be 7 homework assignments and a collection of short online quizzes. The 7 homework assignments contain some written assignments that you are to do on your own and some oral presentation assignments that you will do in groups of three.

4 Written Homeworks	20% (5% each)
3 Oral Homeworks	15% (5% each)
Online Quizzes	12% (see below)
Midterm exams	30% (15% each)
Final exam	23%

Recitations

• Everyone is expected to go to their recitation section. 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.

Exams

• There will be two midterms and one final exam.

• Midterm I October 9:

  The first exam will be a take home exam. The exam will be available starting at Friday October 9th at 00:01 hour EDT and due on Friday October 9th at 23:59 hour EDT. See will be using GradeScope. More details to come.

• Midterm II November 6:

  The method for taking the remaining exams is to be determined.

Online Quizzes

• There will an online quiz most weeks, for a total of 12 quizzes. Most quizzes will be due Saturday 11:59pm, so that you can discuss them on Friday in recitations.
• You will be tested on the material from the previous 2-3 lectures. You may refer to the course materials to solve the quizzes.
• Quizzes are designed to make sure you are keeping up with the material presented in lectures. If you are, you will find most of the problems easy.

Online Quizzes

• 12% of your grade is allocated to "Online Quizzes + +Bonus". This works as follows. Each quiz is worth 1 point.

Homeworks

There will be written homeworks and oral presentations, described below.

Written HWs

• Each written HW will have four (4) problems. Alternate homeworks will have a programming problem. (See the section on programming problems below for more details on these.) The other problems will be written problems.
• You may discuss these problems with a group of up to three people. You must write up the solutions by yourself. If you did collaborate with a group, include the names of your group members in your write up. Of course all the course resources, such as piazza and office hours, are available for help.
• The written problems on these homeworks should be submitted electronically via gradescope. You can add yourself to gradescope using the code 94B7V5. Homeworks will be due at 11:59PM on their due date.
• You must typeset your homework. This makes your HWs legible, and the writing forces you to (re)think through the answers. Of course, merely typesetting your HW is no guarantee of legibility. Please re-read over your submissions! If we cannot understand what you've submitted, you may lose points.
• LaTeX (see Miktex for Windows machines) is a good typesetting system for documents with math. Here's a LaTeX guide by Adam Blank, and a Latex template for Hwks. You can customize it as you like.
• You will lose points for late submissions. Up to 24 hours late: 10 points off. 24-48 hours late: 20 points off. If you want to submit more than 48 hours late, you will lose 75 points. Moreover, you cannot submit electronically after 48 hours, and must contact your TA to submit. At this point solutions will be posted and you may look at them, though anything handed in should be put into your own words
• Each student also gets 2 "grace/mercy days", aka "10% off off coupons". These will be automatically applied to counteract up to 20% total in lateness penalties. Not good on hwks turned in more than 48 hours late. Non-transferrable. Void where prohibited.
• If you use any reference or webpage or material from any other class (including past iterations of 451), you must cite it, else it will be considered cheating. We reserve the right to deduct points for using such material beyond reason.
• We will use a randomized grading strategy. The programming problems will always be graded. From the others, we will choose two at random. Since you should read the sample solutions to all the problems, you can evaluate your solution for the remaining problem on your own. The goal is to have fast grading-turn-around times while giving you as much feedback as possible.

Oral HWs

• Each oral homework (Homeworks 2,4, and 7) has four (4) problems. One of these will be a programming problem. The other three will be regular problems for oral presentations.
• These homeworks are your chance for collaboration. Please form groups of three. The members of your group will work together to solve all four problems.
• For the lone programming problem, you must then write the solution program by yourself! The submission process takes place on Autolab and is described below.
• For the three oral presentation problems, you will present your solutions, as a group, to one of the course staff. Presentations will be given in 45-minute time slots (there will be an electronic sign-up sheet reachable from the course home page). At the presentation, each member of the group will spend 15 minutes presenting one of the problems. The instructor/TA will decide who presents which problem, and when one member is presenting, other members are not allowed to chime in. In the end, the three presentations together will determine the score for the group. However, we reserve the right to give different members different scores when we believe it is warranted.
• If you are nervous about your presentation, you may in addition hand in a written sketch of your solution as well. (This is optional.) We will then take this writeup into consideration in determining your grade on the assignment.

Programming Problems

• The solutions to programming problems will be submitted via Autolab. Your program will read its input from standard input and output to standard output. It will be judged on correctness and running time. The languages accepted are Java, C, C++, Ocaml, SML. (Sorry, no Python this semester.) Details of this process are explained here.
• Our submission system will run plagiarism-detection software on the submissions. Please do not copy!

Solving the Homework

Ideally, this is how you should approach the homework.

1. Read the material taught in class, and make sure you understand all the definitions, algorithms, theorems and proofs.
2. Read the homework problem. Carefully.
3. If you get stuck, here are some suggestions to get past it:
   • Come up with a small example, and see how you would solve that. 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 tree? a graph? a flow 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.
   • If you are still stuck, come to office hours. Sometimes just a brief meeting can get you pointed in the right direction (or help to back you up from a wrong path, to use a DFS analogy).
4. When you write down your solution, re-read what you've written. Is the solution understandable? Does it answer specifically what you've been asked about? Your answers should be clear, and often they will be short.

Bboards:

• We will use Piazza for online discussions and course announcements.
• Make sure you don't post questions to piazza that give away solutions (or even give hints).
• Piazza is best used for announcements, clarifications, and short queries. If you want to discuss problem solving, or need advice on how to get unstuck, please come to office hours! We are here to help you.

Textbooks:

• Several of the topics we teach, particularly the more advanced ones, are not covered in the standard Algorithms textbooks. Hence we will provide lecture notes covering all the material in this course.
• However, we would like you to have a book to give you more detailed coverage. (Or to give you an alternative perspective if you find our own confusing!) We recommend you get one of the following:
  • Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein (hereafter referred to as "CLRS"). It's big, it's fairly expensive, but it is the gold standard of algorithms books with a lot of material. Based on the Algorithms course at MIT.
  • Algorithms, by Dasgupta, Papadimitriou, and Vazirani (herafter referred to as "DPV"). Smaller, cheaper, more informal. A relatively new book based on Algorithms courses at UC Berkeley and UCSD. A preliminary (incomplete) version is available here.
• Specific readings in CLRS and DPV will be listed on the course schedule. It is recommended that you skim the reading before lecture, with a more thorough read afterwards.
• Other helpful material can be found in: Algorithm Design by J. Kleinberg and E. Tardos, Data Structures and Network Algorithms by R. E. Tarjan, Randomized Algorithms by Motwani and Raghavan, Programming Pearls by J. Bentley, Introduction to Algorithms: a Creative Approach by U. Manber, and the classic Aho-Hopcroft-Ullman book. See also some excellent lecture notes by Jeff Erickson at UIUC.

Other Policies

Lateness and Absence

• 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. Miller or Prof. Sutner as early as possible.
• Note that in general job interviews are not a valid reason for missing an assignment or exam.
• The CS department asks us to "remind [you] NOT to schedule flights or plan to leave Pittsburgh at the end of the semester until they know their final exam schedule. The earliest students should leave without knowing is the Tuesday after finals end, December 22."
Flight schedules are not a reason for academic accomodation.

Academic Integrity

• We will assume that you understand the issues and do not need an explanation here. If you cheat in the class we will penalize you and report you to the authorities. 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.