CS 4349 — About this Course


CS 4349 is a course in advanced algorithm design and analysis. By the end of the course, we expect that you will have The course emphasizes a theoretical approach. In other words, we will expect you to write proofs! While we require proofs for correctness and analysis of algorithms in the homework assignments, we will not require proofs for algorithms in exams unless the problem states otherwise. That said, part of the emphasis in the lectures and the assignment feedback will be on how to rigorously describe algorithms and how to convince others of their correctness.

The official course syllabus can be found here. Please look over it carefully. The course website is intended as a supplement to the syllabus, but whatever is written in the syllabus is the final word on a subject.

Announcements and updates to the schdule including recommended reading will take place on the main course webpage. Additional details on the course and its policies are given below. Please make yourself familiar with them to avoid confusion later. There is even some advice on how to perform better on homework and exams.

Welcome to CS 4349! We hope you find it both interesting and useful to your future career.

Reading

The standard required textbook for CS 4349 is Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, 3rd Edition. MIT Press 2009, or simply CLRS. I also highly recommend the online lecture notes by Jeff Erickson available here. While I will pull many examples from both, you should consider the textbook and lecture notes as supplements to the lectures and not your only source for some material. The homework and exams are mainly about mastering the tools I describe during lectures. So, I will not ask you homework questions that require possession of the textbook, and I will certainly not ask you to simply recall details contained only in the text but not discussed during lecture. That said, the more you read outside of lecture, the more examples and details you will see, and hopefully your reading will lead to a deeper understanding of the class material.

Grading

This course uses a combination of a curve and an absolute grading scale. That way, we may safely challenge you in homework and exams while still making it possible for everybody who does well to get a good grade.
  1. We drop everybody's lowest homework assignment score. Your total homework score is computed only using the remaining assignments. Each assignment (other than the one we drop) is weighted equally.
  2. We compute a raw total for each student. Each type of graded material contributes to your raw total according to these weights. The raw total does not include extra credit.
  3. We compute an adjusted total for each student. The adjusted total is your raw total plus any extra credit earned on homework assignments.
  4. Each student then receives either a curved grade or absolute grade, whichever is better. The curved grade cutoffs are computed using the students' raw totals. Unfortunately, I will not know these cutoffs until final grades are in. Your curved grade is determined by where your adjusted total lies between the cutoffs.

    The minimum cutoffs for the absolute grades are given in the following table:
    A+: 90%A: 85%A-: 82.5%B+ 80%B: 75%B-: 72.5%
    C+: 70%C: 65%C-: 62.5%D+ 60%D: 55%D-: 52.5%
    (In case of discrepancy between this table and the syllabus, we defer to the syllabus.)

    Your absolute grade is determined by where your adjusted total lies between the cutoffs. Again, you receive the better of your curved grade and absolute grade.
  5. The instructor may increase grades beyond what is computed above at his discretion.

Homework

We intend to release homework about once a week. It will be released on Wednesday, just before class, and be due at the beginning of class the following Wednesday. No late homework will be accepted so we may make the solutions public as soon as possible. This rather strict policy is part of the reason we drop your lowest homework score.

We may include more difficult extra credit questions on some homework assignments to encourage a deeper understanding of the material. Together, these questions will be worth at most 1/6 of the overall homework score. As explained above, the cutoff points for the curved grades are not affected by extra credit.

Collaboration

You are encouraged to discuss homework problems with other students. However, it is expected that you not work together while writing down your solutions and that solutions be written in your own words.

You are expected not to use outside sources while solving homework problems. However, if you do use outside sources (or write solutions in close collaboration with another student) then you may cite that source (or student) and still receive full credit for the solution. Material from the lecture, the required textbook, or prerequisite courses need not be cited. Failure to cite other sources or failure to provide solutions in your own words, even if quoting a source, is considered an act of academic dishonesty.

Extra credit problems are an exception to outside sources policy. You must discover and write extra credit solutions independently to receive credit.

Regrades

Requests for regrades on a homework problem must be made directly to the TA within one week of the homework assignment being returned. Please be considerate of whether your request is legitimate, and please be prepared to explain why you feel you were graded incorrectly. Regrade means regrade, so your score may actually decrease.

General advice

Please make sure your answers are readable. Any homework solution that is unintelligible will receive a score of 0 regardless of correctness. It is not required, but we highly recommend you typeset your homework solutions, preferably using LaTeX.

Unless we say otherwise, you must prove your answer is correct to receive full credit for a homework problem.

We can only grade what we are given, even if you appear to have the right answer in mind. Please do not attempt to describe algorithms by only giving examples and assume we can fill in the details. As a general tip, a former student of this course who did well should be able to read your homework solution, understand whatever algorithm you have in mind, and feel confident about its correctness, even if they have never seen the specific homework problem before.

Exams

There will be one midterm exam scheduled for Wednesday, October 4th, from 7:00pm to 9:00pm and one final exam during the regularly scheduled final exam period. The midterm will be in the normal classroom.

As opposed to homework, we will generally not require proofs on exam questions unless we specify otherwise. There just isn't time to write a coherent proof! Otherwise, the advice given above for homework still stands, minus the part about LaTeX, of course.

Notes

You may bring a single piece of 8.5'' by 11'' paper with written or printed notes to the exam room, but we will need to take it after the exam in case there are students taking conflict exams at a later date. Other than that, no outside material or collaboration will be allowed during exams.

Conflicts

If you know about a conflict with the scheduled exam dates, please inform the instructor at least one week in advance so we can set a conflict exam time. Makeup exams for unexpected conflicts will be scheduled if you have a documented medical excuse. If you have or feel you may have a disability that requires a reasonable accommodation in how I structure or administer an exam, please consult with and get written documentation from the Office of Student AccessAbility (OSA) at least one week in advance of the exam.

Regrades

Similar to homework, requests for regrades on a homework problem must be made directly to the instructor within one week of the homework assignment being returned. Please be considerate of whether your request is legitimate, and please be prepared to explain why you feel you were graded incorrectly. Regrade means regrade, so your score may actually decrease.

Attendance Policy

It is the Computer Science Department’s policy that absence in three consecutive lectures will result in the course grade being lowered by one letter and absence in four consecutive lectures will automatically result in a failing grade (F) in the course.