Analysis of Algorithms (Fall 2014)

This class is taught by Jay McCarthy. Call him Jay. Email him at jomccarthy AT vassar DOT edu.

We meet in SP105 at 16:35-17:50 TR.

Jay McCarthy’s office hours are 9am-5pm M-F (except when teaching) in SP104.4.

There is a mailing list hosted at Google Groups. Use it to ask non-revealing questions and receive answers, as well as general course announcements. You are responsible for reading the content of this mailing list.

1 Introduction

Introduces the systematic study of algorithms and their analysis with regard to time and space complexity. Topics include divide-and-conquer, dynamic programming, greediness, randomization, upper and lower-bound analysis, and introduction to NP completeness. Emphasis is placed on general design and analysis techniques that underlie algorithmic paradigms. Builds a foundation for advanced work in computer science.

2 Meetings

Jay will not be present on days marked with a * in the Exercises column. Page numbers are for the PDF, subtract 21 to get the page number for the text.

This schedule is likely to change as we calibrate each other and figure how much work, how fast is the right balance. In particular, I am equally worried about going too slow and assigning too much—so please tell me if I am too slow or too fast. (A good metric for deciding this is how much time it takes to prepare for class. I expect about two hours. If you are doing it in much less than two hours, I’m going too slow. If most of you are taking more than two hours, I’m going too fast or too much. By the way, don’t spend more than two hours—just go as far as you can and stop and tell me.)

3 Projects

Out dates are suggestions—you may need to start earlier.

This schedule may change.

4 Meeting Format

When I took a class like this in college and grad school, I was very annoyed by the way class time was used. I would read a chapter of the book beforehand, but invariably no one else would. The professor would assume that no one had read anything, so she would present the material using slides and then give us a few minutes at the end for questions about exercises or other things. I found this so aggravating because the more difficult parts of the text or exercises were never talked about in class, because a foundation had to be built for everyone to get on the same page. So, the professor spent all the class time on the stuff that was easy to learn on your own and almost no time on the stuff that was hard. I hope to flip this dynamic in our class. So, before class, I expect you to read the chapter, do the listed exercises, and be prepared to talk about them.

Here’s how I’d like the meeting to go each day:

At the start, I’d like to give my own brief recap of what was important about the chapter. Next, we’ll discuss what was difficult in the reading. Ideally, you will each volunteer something that you found challenging or are extremely confident in your understanding and we can talk about them as a group. In the worst case, I’ll just have to start assigning random people to talk about things that I would expect would be hard. I don’t think that will be MOST productive though. For the rest of the class, we’ll work through the difficult parts of the assigned exercises. I’m a big believer that you nail down your understanding of these ideas by doing the exercises, so I want to make sure everyone understands and can do them well. Finally, I’ll do something similar to the beginning and summarize the day’s activities then give a little preview of what I hope we’ll accomplish next time.

My goal is for us to all contribute so we can learn from each other’s expertise and perspectives that all may be edified of all. So, I will equally call on students to come up and lead the discussion of the material or exercise. As a discussion leader, you can present your own work or understanding of the material, or you can bring together the expertise you know exists around the room. If you can’t lead the discussion on something, there’s no shame in that, just ask for the next person to be called. We’ll move on and you’ll get another opportunity later. Leading a discussion constitutes participation in class.

In order to help you be able to lead discussions, I will require that you submit your exercises for each day before class. It will not be requisite that the work be fully complete and correct, instead you are simply required to have made a diligent effort on each exercise.

5 Turn-In and Grading

I highly recommend that you read this article about grading. I also recommend you read this article about the stress that you may experience in a computer science program. Please try to make healthy productive choices in your life. I would love the opportunity to help you in any ways I can.

5.1 Turn-in

5.1.1 Exercises

You should email your exercises to me before class starts. If you send an assignment late (even by a single second), it will not be graded. Send it before you start towards class!

Your email should have [CS241] date exercises as the subject, where date is the date of the exercises as mm/dd. Do not send multiple emails, if you do, I’ll count the oldest one.

Your email should contain one PDF file. Include the numbers of every exercise assigned, regardless of whether you complete them. I recommend producing PDFs with LaTeX.

For a (cont) exercise, please Reply to your previous turn-in, so I can easily compare the two versions.

5.1.2 Projects

You should email your projects to me before 6PM Poughkeepsie time on the due date listed.

If you send an assignment late (even by a single second), it will not be graded. This is a real due date and due time. Please use this early due time to get a good night’s sleep and enjoy your evenings.

Your email should have [CS241] code as the subject, where code is the code listed on the assignment table. Do not send multiple emails, if you do, I’ll count the oldest one.

Your email should contain one Zip file with your files inside it, such that they extract to a directory with the same name as the code of the assignment. Any non-code documents should be submitted as a PDF. I recommend producing PDFs with LaTeX.

5.2 Exercise Scores

As mentioned above, exercise sets will be graded based on diligent effort. I will give you a score of (/ n m) where n is the number of diligently attempted exercises and m is the number of assigned exercises. In the end, I will average all these together with no weighting.

5.3 Participation Points

I will give you one participation point per discussion you lead. There are about 24 classes with content and I hope to have about 4 topics per class and there are about 24 of you, so you should aim for about 4 participations. This goal may change depending on how much we tend to do in a day. I apologize for this slightly unpredictable aspect of the grading.

5.4 Project Scores

Each project’s page describes how it will be graded. All projects will receive a grade from the closed interval between 0 and 1.

5.5 Numeric Grade

I will take your various points and combine them with this function to get a numeric grade:

A few things to notice about this function: Your final score can be more than 1, which means you can consider pieces of various assignments as extra credit. The first projects are weighted significantly less than the later ones, so you can get used to how things are graded in the class. Finally, I am committed to faithfully removing my whims from this scoring function, so you can count it. This means, for instance, if you don’t need to do the final to get the score you want, then feel free to skip it.

5.6 Letter Grade

6 Help

My job is to help you.

If you need a "shallow" amount of help, then look at the Google Group. First, see if I have already answered your question. Then, send your own email.

Only send me personal email if you need to talk about something private, such as your grades. Anything else is best discussed in public, so others can benefit. If you do send personal email, put [CS241] as a prefix in the subject.

If you need a "deep" amount of help, please come to my office or call me (801-361-0732) and we’ll talk and try to resolve whatever ails you.

7 Readings

We’ll be using the book Introduction to Algorithms, third edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. (The second edition may work too, but I can’t guarantee that the exercises are all present with the same numbers.)

8 Software

If we write programs for assignments, feel free to use whichever language you want. I slightly recommend that you try to go a little outside your comfort zone and use this course as an opportunity to learn a new language.

9 Fine Print

I support and implement all the general policies of Vassar, including but not limited to those related to students with disabilities, plagiarism, and respectful classroom etiquette. I expect you to always attend class. We’ll have an administration-scheduled final. And, from the administration:

"Academic accommodations are available for students registered with the Office for Accessibility and Educational Opportunity (AEO). Students in need of disability (ADA/504) accommodations should schedule an appointment with me early in the semester to discuss any accommodations for this course that have been approved by the Office for Accessibility and Educational Opportunity, as indicated in your AEO accommodation letter."