Wednesday: Chapter 15 of the text (Dynamic Programming). My notes that I will hand out for this topic are actually done somewhat differently than what the book does, although there is a lot of overlap. But I would strongly suggest reading my notes first.
We will start this topic this week and finish it up in the class next week. Everything we do will be covered in this one handout.
Wednesday: We start depth-first search. This corresponds to Sections 22.3 through 22.5 in the text. However, the main source we will be using is the first chapter of my expository article "Notes on Graph Algorithms Used in Optimizing Compilers", which you can find on my web site.
Please be sure to print out a copy for yourself in preparation for this week's classes, as I won't be handing it out, but I will be going through it pretty closely. (If you don't have it with you in class, you will be really lost.)
This covers the same material as the text, so you can just skim the text if you want.
Wednesday: We start talking about flows in networks, the max-flow min-cut theorem and some applications. I will pass out the Lecture 14 handout, which covers this material.
Note: this handout covers pretty much what is in Chapter 26 of our text. However, I strongly recommend that you do not read Chapter 26. The reason is that I am using a different convention for representing such networks than the book does, and if you try to read both the book and my notes, you will really get confused.
Wednesday: A brief introduction to approximation algorithms for NP-complete problems, a couple of bits of history, and more review for the final exam.
The final will cover the entire course. As usual, there will be more questions than you can possibly do. So you don't have to worry if there are some you get stuck on. Just do other ones.
This prerequisite is important. If you have not had it, and done well in it, you should not be enrolled in this course.
Further, while CS 320L is the official prerequisite, there is some other material that you really need to know in order to understand what we are doing in this course. Undoubtedly you have studied this before, but I just want to make it explicit here. I will not review this material in class—you are responsible for understanding it. The homework and also the exams will include problems using this material:
Some serious single-variable calculus: derivatives, the chain rule, integrals, the "Fundamental Theorem of the Calculus", maxima and minima, increasing and decreasing functions, convex functions, step functions. (Do you know what a step function is? If not, you need to find out right away. Is a step function really a function? And how do you integrate a step function?)
And of course you should never get confused between the two functions
f(x) = xa(for instance,
f(x) = x3) and
g(x) = ax(for instance,
g(x) = 3x)
Which one grows faster? And is the difference in growth significant? (And I'm not putting these two questions here to practice my typing. Will you be able to answer these questions if I ask them to you on the first day of class?)
Please note: The classroom just changed. What you see here is the correct room.Office hours: Before class: M/W 4:30-5:15 PM
I'm sure everyone in this class has taken one or more courses in which you have learned some of the really great algorithms.This is not one of those courses. This is not a course in "really great algorithms", or in writing programs, or even in writing pseudo-code.
This is for all practical purposes a mathematics course. It is a course on the analysis of algorithms. We are going to prove theorems in this course. In fact, that's just about all we are going to do. And when I say we, I really mean you. The homework will consist of theorems that you will have to prove. The exams will consist of theorems that you will will have to prove. That's what we're going to do.
At a minimum, I plan to cover the following material this term:
There will be one homework assignment each week. I will not accept assignments handed in late.
There will be two in-class "mid-term" exams, and one final exam.
All the exams will be "closed-book" exams. No books, no notes, no smartphones or other electronic equipment, and so on. Just bring something to write with.
I will weight the work in the course roughly as follows when making up final grades:
I will not give out "review sheets" for the exams. It should go without saying, however, that the very best way to prepare for the exams is to
This course does not involve any programming per se, although without a doubt your experiences in building serious programs will help you understand many of the issues we deal with.
In fact, as I already stated above, the course could well be regarded as a mathematics course. I will be proving things in class, and you will be expected to write formal proofs in your assignments and on exams. If this is something you are not ready to come to grips with, you should wait until you are ready to take this class.
There is a style to writing proofs. In fact, there are several styles. Your goal should be to write proofs that are easy to read and that illuminate the reason why something is true. This is not easy to do. Good writing of any kind is difficult, and we will work hard at it all term.
Probably the single most important proof technique in this area is mathematical induction. I will assume not only that you are familiar with this, but are comfortable using it. I will not teach it, but I will expect to see inductive proofs written out clearly and well.
I also expect you to be familiar with standard mathematical notations such as summations (and of course, integrals). Some of this is reviewed in the appendices of the text. I will not review this in class. I expect you to know it, and we will be using it a lot.
One thing is very important to bear in mind: like any other kind of writing, a proof must be understandable. If I can't understand what you are writing, then it can't be correct. And I'm not going to try to guess what you had in mind. (One thing I have noticed is that some students seem to believe there is only one way to do something, and only one way to explain it, and so of course I must understand what they mean. But that's not true. There are almost always many ways to do things, and many ways to explain them. If I write on your paper "I don't understand this", I'm not being irritable—I really don't understand it.) If you are uncertain how to express something, please just talk to me or send me email, and I'll try to help. But don't even bother writing something that can't be understood.
Think of this like you would when writing a computer program. If the compiler or interpreter can't understand it, it's wrong. And you have to be really careful with your use of language and terms. For instance, one thing beginning programmers often get mixed up about is the correct use of "or" and "and". The meaning in computer languages is not the same as in English (or any other natural language, so far as I know). The same is true in proofs. We use language in very precise and fixed ways in proofs, and we do this so that what we write can be understood in its exact meaning by anyone at any time, anywhere in the world.
Just for a simple example: the sentence "All horses are not white." does not mean the same as "Not all horses are white." At least, not when writing proofs. In ordinary English, these two sentences are generally regarded as equivalent. But for our purposes they are not. You have to be careful about this.
Here's another example: The symbol "==>" means "implies". It does not mean "then". So you can write
if x = 3 then x + 5 = 8or you can write
x = 3 ==> x + 5 = 8But you cannot write
if x = 3 ==> x + 5 = 8 !!! WRONG !!!Here's another thing to watch out for: the symbol "=" means "equals". It doesn't mean anything else. (Well, there is one small exception, involving "big-O" notation, which we will cover in the second class.) So could could write something like this:
2x - 1 = 5 so x = 3But you cannot write
2x - 1 = 5 = x = 3 !!! WRONG !!!Please try to be careful about things like this. And please don't be offended if I correct mistakes like this in what you write.
I encourage you to talk with other students—in fact, with anyone—about the topics we are covering. And I also encourage you to send me email with questions; I'll be happy to get back to you as quickly as I can. However, the writeups you hand in must be entirely your own. You may not copy proofs, or algorithms, or parts of proofs or algorithms, or anything else, from anyone else's paper, or from the web, or from books, or from anywhere else, even if you give credit to that person or source. And you must be able to explain to me what you have written.
Please do take this seriously. I'm very happy to try to help you out in person or by email. I really do want every one of you to succeed, and I'll try hard to make that happen. But I have no tolerance at all for plagiarism. If I find evidence of it, you will receive an F for the course. And I don't give "second chances".
Students are required to adhere to the polices expressed at the University web site Academic Policies and Rights.