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

### 1Introduction

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.

### 2Meetings

 Day Date Topic Links Exercises 1 09/02 Ch 1: Introduction code 2 09/04 Ch 2: Getting Started code 2.1-3 (p22), 2.1-4 (p22), 2.2-2 (p29), 2.2-3 (p29), 2.2-4 (p29), 2.3-3 (p39), 2.3-4 (p39), 2-2 (p40) 3 09/09 Ch 3: Growth of Functions code 3.1-1 (pg73), 3.1-2 (pg73), 3.1-3 (pg74), 3.1-7 (pg74), 3.2-1 (pg81), 3.2-8 (pg81), 3-4 (pg83) 4 09/11 (cont) code (cont) 5 09/16 Ch 4: Divide-and-Conquer code 4.1-4 (pg95), 4.1-5 (pg96), 4.2-1 (pg103), 4.2-6 (pg104), 4.3-1 (pg108), 4.3-5 (pg108), 4.3-6 (pg108), 4.4-1 (pg113), 4.4-6 (pg114), 4.4-8 (pg114), 4.5-1 (pg117), 4.5-2 (pg118), 4.5-4 (pg118), 4-5 (pg130) 6 09/18 (cont) code (cont) 7 09/23 Ch 5: Probabilistic Analysis and Randomized Algorithms code 5.1-1 (pg138), 5.2-1 (pg143), 5.2-2 (pg143), 5.2-5 (pg143), 5.3-2 (pg149), 5.3-3 (pg149), 5.3-4 (pg150), 5.4-1 (pg163), 5.4-2 (pg163) 8 09/25 (cont) code (cont) 9 09/30 Ch 6: Heapsort (in SP309!) code 6.1-1 (pg174), 6.1-3 (pg174), 6.1-5 (pg175), 6.2-1 (pg177), 6.2-3 (pg177), 6.2-6 (pg177), 6.3-2 (pg180), 6.4-2 (pg181), 6.4-3 (pg181), 6.5-4 (pg186), 6.5-5 (pg187), 6.5-9 (pg187), 6-1 (pg187) 10 10/02 (cont) code (cont) 11 10/07 Ch 7: Quicksort code 7.1-2 (pg195), 7.1-3 (pg195), 7.2-1 (pg199), 7.2-2 (pg199), 7.2-3 (pg199), 7.2-4 (pg199), 7.3-1 (pg201), 7.3-2 (pg201), 7.4-2 (pg205), 7.4-3 (pg205), 7.4-5 (pg206) 12 10/09 (cont) code (cont) 13 10/14 Ch 8: Sorting in Linear Time code 8.1-1 (pg214), 8.1-4 (pg215), 8.2-2 (pg217), 8.2-4 (pg218), 8.3-2 (pg221), 8.3-4 (pg221), 8.4-2 (pg225), 8.5-abc (pg228) 14 10/16 Midterm 15 10/28 Ch 9: Medians and Order Statistics code 9.1-1 (pg2136), 9.2-1 (pg240), 9.2-4 (pg241), 9.3-1 (pg244), 9.3-5 (pg244), 9.3-8 (pg244), 9-1 (pg245) 16 10/30 Ch 11: Hash Tables code 11.1-1 (pg276), 11.1-2 (pg276), 11.2-1 (pg282), 11.2-3 (pg282), 11.2-4 (pg282), 11.2-6 (pg282), 11.3-1 (pg289), 11.3-2 (pg290), 11.4-1 (pg298), 11.4-3 (pg298) 17 11/04 Ch 12: Binary Search Trees code 12.1-2 (pg310), 12.1-4 (pg310), 12.2-4 (pg314), 12.2-5 (pg314), 12.3-2 (pg320), 12.3-4 (pg320) 18 11/06 Ch 13.1: Balanced Binary Tree code 13.1-1 (pg332), 13.1-3 (pg332), 13.1-4 (pg332), 13.1-5 (pg333), 13.1-6 (pg333), 13.1-7 (pg333) 19 11/11 Ch 15: Dynamic Programming code 15.1-1 (pg390), 15.1-5 (pg391), 15.2-1 (pg399), 15.2-3 (pg399), 15.3-2 (pg410), 15.3-4 (pg411), 15.4-4 (pg417), 15.5-2 (pg425) 20 11/13 (cont) code (cont) 21 11/18 Ch 22: Elementary Graph Algorithms code 22.1-1 (pg613), 22.1-6 (pg614), 22.1-8 (pg614), 22.2-1 (pg622), 22.2-4 (pg623), 22.2-7 (pg623), 22.3-1 (pg631), 22.3-8 (pg632), 22.3-11 (pg633), 22.4-4 (pg636), 22.5-1 (pg641) 22 11/20 Midterm Review * 23 11/25 Ch 23: Minimum Spanning Trees code 23.1-1 (pg650), 23.1-3 (pg650), 23.1-10 (pg651), 23.2-1 (pg658), 23.2-2 (pg658), 23.2-4 (pg658) 24 12/02 Ch 24: Single-Source Shortest Paths code 24.1-1 (pg675), 24.1-3 (pg675), 24.1-4 (pg675), 24.3-1 (pg683), 24.3-2 (pg684), 24.3-4 (pg684) 25 12/04 Ch 34: NP-Completeness code 34.1-1 (pg1081), 34.1-5 (pg1082), 34.2-1 (pg1086), 34.3-1 (pg1098), 34.4-1 (pg1106), 34.5-2 (pg1121) 26 12/09 Final Prep 27 12/16 Final @ 5-7pm in RH 312

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

### 3Projects

 Project Code Out Due Algorithm Experiment the First alg1 09/02 10/14 Midterm midterm 10/16 Algorithm Experiment the Second alg2 10/16 12/09 Final final 12/16

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

This schedule may change.

### 4Meeting 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:

 Start End Activity 16:35 - 16:45 Brief Recap 16:45 - 17:10 Reading Discussion 17:10 - 17:40 Exercise Discussion 17:40 - 17:50 Brief Preview

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.

### 5Turn-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.1Turn-in

##### 5.1.1Exercises

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.2Projects

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.2Exercise 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.3Participation 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.4Project 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.

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

 > (define (combine exercises participation alg1 midterm alg2 final) (+ (* 0.25 (/ participation 4)) (* 0.2 exercises) (* 0.1 alg1) (* 0.2 midterm) (* 0.15 alg2) (* 0.3 final)))

Examples:

 > (combine 0.0 0 0.0 0.0 0.0 0.0) 0.0 > (combine 1.0 4 0.0 0.5 1.0 1.0) 1.0 > (combine 1.0 4 1.0 1.0 1.0 1.0) 1.2

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.

I will then run the following function to convert it to a letter:
 > (define (convert-to-letter ng) (cond [(> ng 0.93) "A"] [(> ng 0.9) "A-"] [(> ng 0.86) "B+"] [(> ng 0.83) "B"] [(> ng 0.8) "B-"] [(> ng 0.76) "C+"] [(> ng 0.73) "C"] [(> ng 0.7) "C-"] [(> ng 0.66) "D+"] [(> ng 0.6) "D"] [else "F"]))

Examples:

 > (convert-to-letter 1) "A" > (convert-to-letter 0.94) "A" > (convert-to-letter 0.899999) "B+" > (convert-to-letter 0.81) "B-" > (convert-to-letter 0.74) "C" > (convert-to-letter 0.6999999) "D+" > (convert-to-letter 0.62) "D" > (convert-to-letter 0.57) "F"

### 6Help

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.

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

### 8Software

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.

### 9Fine 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."