CS 4349 is a course in advanced algorithm design and analysis.
By the end of the course, we expect that you will have
- the ability to use asymptotic notations, solve recurrences, and perform algorithm
analysis,
- the ability to design, analyze, and prove correctness of algorithms based on
divide-and-conquer techniques,
- the ability to design, analyze, and prove correctness of algorithms based on greedy
techniques,
- the ability to design, analyze, and prove correctness of algorithms based on dynamic
programming techniques, and
- the ability to design, analyze and prove correctness of graph algorithms.
The official course syllabus can be found here.
All policies from both the syllabus and website apply, but if there is a contradiction, then the
syllabus takes preference (but do email us so we can fix the issue!)
Announcements and updates to the schedule including recommended reading will take place on the
main course webpage.
We'll also make announcements on eLearning.
Additional details on the course and its policies are given below.
Do make yourself familiar with them to avoid confusion later.
And be sure to carefully read the writing policies and advice so we may
fairly grade you for the work you do for the homework and exams.
Welcome! We hope you find this course both interesting and useful.
Most of the lectures will be based on the excellent lecture notes of Jeff Erickson available
here.
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, often referred to
as CLRS.
I will also pull example out of the textbook, but I will not follow it too closely.
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.
I will always write out homework problems instead of just pointing you to
the textbook.
Your grade will be determined by three things: homework, a midterm exam, and a cumulative final
exam.
Your grade will be determined by a weighted sum of these three items as shown below.
- Homework: 50%
- Midterm Exam: 20%
- Final Exam: 30%
The "I don't know" policy
The homework and exam problems in this course will be difficult, and they will all require enough
mastery of the material to creatively solve new problems.
Your job when writing solutions will be to clearly and concisely explain the solution and why it is
correct.
You job is not to babble, regurgitate facts from lecture, or otherwise try
to fake us out when you don't know the answer.
Such solutions will be worth no credit.
However, for any question, or lettered part of a question, on either the homework or on an exam, you
may write "I don't know" and nothing else to receive 25% of the total
points for that problem or part.
If you write anything else or leave your solution blank, then the rule no longer applies and we will
grade exactly what is written.
Remember, a completely correct but suboptimal solution or significant progress toward an optimal
solution will always be worth more than 25%.
For example, if we expect an \(O(n \log n)\) time algorithm and you give and justify correctness
for an \(O(n^2)\) time algorithm, you will receive more than 25% of the points.
Grade cutoffs
The minimum cutoffs for 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% |
We may decide to lower these cutoffs depending on how difficult
assignments are and how the class as a whole performs.
That said, we will not lower the cutoff for a D- below 40%.
We reserve the right to change individual student grades when special circumstances arise, but only
up and very rarely.
We will release at least ten homework assignments.
They will generally be released once a week and be due at the beginning
of class one week later.
No late homework will be accepted.
However, we understand that mistakes happen and that sometimes things pile up.
Therefore, we will drop one of your weekly homework scores, whichever is lowest.
In the case of an unusual circumstance such as a documented extreme illness or
injury, contact Kyle as soon as possible to arrange accommodations.
Collaboration and submission
Homework assignments may optionally be done in small groups of up to three students.
Each group of students working together should turn in a single set of solutions.
Clearly print the names of every member of your group, the homework number, and
the problem number at the top of every page.
For example, you might write "Kyle Fox and TA TBA, HW0 #2".
Without this information, we cannot guess who you are or what problem you're supposedly solving, so
we cannot give any credit.
In addition, start each numbered homework problem on a new sheet of paper
so we don't miss any problems, and staple your entire assignment once in
the upper left corner so we don't lose anything.
Do not use paper clips, tape, glue, spit, or rubber bands, and don't try to keep pages together by
folding or tearing.
We hope you will put in an honest effort to solve each homework problem without having to rely on
resources outside of the course material or your own group.
However, we also want to give you the opportunity to discuss class material with other students and
access other kinds of outside help as needed.
If you use a solution from an outside source, such as a web page, a journal paper, a different
algorithms textbook, or your mom, or if you consult a student outside your homework group, then
you must rewrite the solution in your own words, and you must properly cite your
source.
Do not forgot to rewrite in your own words; the goal here is not to teach us what you found outside
the course material, but to convince us that you actually understand it yourself.
You may assume we have knowledge of the official course material without citation, but nothing else.
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, and we will report suspected violations to
the Office of Community Standards and Conduct.
A correct solution based on a cited source and written in your words is still worth full credit.
When in doubt, cite your source!
(That said, now would be a good time to mention that many of these course policies and the writing
advice given here are taken from algorithms course websites by
Jeff Erickson and
Erin Wolf Chambers.)
There are several websites out there that offer solutions to some of the problems we will post.
Be very careful with these sites.
The solutions are sometimes incorrect, and in cases where they are correct, they don't offer a full
or understandable justification for what they are doing.
We will put extra emphasis on justifying correctness during scoring in cases where you rely on an
outside source.
Regrades
Requests for regrades should be done within one week of an assignment or exam being returned.
Please be considerate of whether your request is legitimate.
All regrade requests must include an explanation of why you feel you were graded incorrectly.
Regrade means regrade, so your score may actually decrease.
Extra credit
We may occasionally offer opportunities to gain extra credit by solving additional challenging
problems or doing other relevant work.
However, these opportunities (if any) will be rare, and you should not depend upon them to get the
grade you desire.
The final grade cutoffs will be determined before taking extra credit into account, so these
opportunities will only help and never hinder students.
And no, the "I don't know" rule and ability to receive credit after citing sources
do not apply to extra credit problems.
Your group is on its own here.
Exams
If you know about a conflict with the scheduled exam dates, please inform me 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.
You may bring notes written or printed on both sides of a single 8.5’’ X 11’’ piece of paper during
exams.
No other outside sources or collaboration will be allowed.
These notes must be turned in along with the exam.
These notes are intended to help you avoid gotchas where you forgot one important fact you might
need later or to provide examples of algorithm design techniques we will go over in lecture.
It is extremely unlikely that your notes will contain verbatim the answer to any question I ask,
even if you stuff them silly with examples you find online, so prioritize readability over
exhaustiveness.
Attendance
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.