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 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


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:

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:

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