Syllabus for Computer Science 366b, Intensive Algorithms
Spring 2018
The relation between 365 and 366
CPSC 365 and 366 cover essentially the same material, meet at the same
time, and use the same book.
You can only get credit for one of them.
366, the intensive version, is being offered for the first time this year.
It is intended for students who are comfortable with proofs,
who would like to be prepared for graduate school, and
who want to improve their problem solving abilities.
Intensive Algorithms (366) will differ from Algorithms (365) in that
- Familiarity with how to write proofs will be assumed. This is
why MATH 244 is suggested as a prerequisite instead of CPSC 202
(which covers proofs in less detail).
- It will cover a little more material.
- The problems discussed in class will often be more
sophisticated.
- It will provide more exposure to current research topics.
- Students will work on the problems on their own. While
collaboration is wonderful, it will be forbidden in this class so
that every student can have the experience of solving problems on
their own.
- It will have a final exam.
Most students should take 365 instead of 366.
This is true even for students who love proofs and problem solving.
CPSC 366 will take more time than 365.
The Computer Science major has many courses that take a lot of
time, and I recommend against taking too many at once.
Course Information
Prerequisites
The prerequisites for this course are discrete math
(MATH 244) and CPSC 223.
The background in discrete math is essential.
You should be used to reasoning about graphs and
enjoy learning and writing proofs.
Students will tell you that CS 223 is less essential.
But, it would be better to take it first if you can.
The main things that are taught in CS 223 that you must know
are how to implement basic data structures
in a language like C or Java.
You should also be able to estimate how many basic operations
are required by these implementations.
A good review of some of the prerequisites appears in Chapters 2 and 3 of Kleinberg-Tardos.
Course Requirements
I expect that there will be 9 problem sets and a final exam.
We will drop every student's lowest problem set grade, normalizing
for the difficulty of that problem set.
I say "expect" because plans will change if enrollment or staffing
differ substantially from my expectations.
I do not expect an in-class test or midterm.
There will be no programming in this class.
All of the assignments will involve designing, analyzing, and proving
correctness of algorithms.
The grading breakdown will be:
- Problem sets: 80%
- Final: 20%
As the problems will be hard and you will be working on your own,
perfection will not be required to get a A.
I expect to set the threshold between A- and A to around 92%.
Problem Sets
The homework problems are the major assignments in this course,
and you are to work on them on your own.
It should go without saying that you may not search the web for
solutions to similar problems.
Most of the problems assigned will require a flash of insight or
inspiration.
The reason that you are forbidden from collaborating
on the problem sets is that I want every student to
practice having insight, and to learn how they do it best.
I suggest looking at the problems as soon as they are assigned, and
starting to think about them early.
Of course, you can discuss the problems with the course staff.
All problem sets must be submitted via Gradescope.
Gradescope requires a PDF of your homework.
There are three ways that students usually produce these:
- Write it by hand, and scan it by camera or scanner.
- Write it in LaTeX, and generate a PDF. We recommend generating
your latex either through an editor like Emacs or Sublime,
via an integrated package like TexWorks or TexShop, or
an online system like ShareLaTeX. We will provide some examples of
good LaTeX.
- Write it in Word, using "Insert Equation" for the math, and
generate a PDF.
If generating a PDF is going to pose a problem, contact the course
staff as early as possible to let us know so that we can figure out
how to make a suitable accommodation.
Solution Sets
Solution sets are only distributed on paper.
These solutions are for your own personal use, and are not to be given
to other students or stored anywhere that students in future years
might encounter them.
The one exception to this rule is that you may give a copy of a
solution sets to another student who is presently enrolled in the course.
Late Assignments
As solution sets will be distributed at the end of the class at which
they are due, late
assignments will not be accepted.
There is a small chance that we will accept a problem set submitted
during class before the solutions have been handed out.
But, it would be substantially penalized.
Students who have a Dean's excuse for a problem set will be assigned
an alternate problem set.
Technology in the classroom
One of your jobs as an undergraduate is to figure out how you learn
best. I learn best when I take notes on paper with
no lines, or when I simulate this process with a tablet.
Some of you will learn best when you take notes with a laptop,
and some of you will be better off just paying careful attention and
not taking notes at all.
I will not presume to tell you what is best for you.
I do request that you ask a question if you are confused.
Even if you do not know why you are confused, asking a question can
give you time to figure out why.
Where to find information
- The course schedule page. Look here
first.
- If there is information you need, and it is not on the course
schedule page, please look at this page. It should be here
- If neither of these pages reveals what you need to know,
you can email the course staff at TBA.
- If you miss a class and would like to find out what happened,
ask another student in the course. Please do not ask the course
staff.
Also, do not forget to look at the course
schedule page
to find out which readings go with with lectures.