Thursday, December 18, 2008

Grade Statistics File Updated has been updated to include all graded items in the course.

Sunday, December 14, 2008

Additional Code Analysis Practice

I posted the problems I came up with in the review session but didn't have time to present. They can be found on the DBoard.

Thursday, December 11, 2008

Vote for review topics

There will be a review session on Sunday, 14 Dec, in Wean 7500 from 3:00-4:30. You can vote for the topics you would most like to see covered by going to this link:$=L5FA2AA9B6A73651C6C0&D$ See the current poll status here:$=any&S$=L5FA2AA9B6A73651C6C0&D$

Wednesday, December 10, 2008

Final Review Session

There will be a review session for the final Sunday, 14 Dec, in Wean 7500 from 3:00-4:30. TAs will be available to answer individual questions from 4:30-5:00. More details soon.

Tuesday, December 09, 2008

Practice Final

Last year's final is available for practice:

Videos available for exam prep/review

Videos are available, at last. Here is how to watch: Click on the "videos" link on the left. (This used to direct you to last fall's lectures.) Click student. You'll be asked to authenticate. The user name to use is "[yourandrewID]" along with your usual andrew password. Note the "ad" in the domain. Note also that if your authentication fails, go to myandrew and reset your password to itself. (Why this works I cannot explain.) Use the slide tray on the bottom to navigate. Videos that show powerpoint directly have a search function that you can use to find specific material -- the index is built from text on the slides. Try also the note-taking tab. Apologies for not getting these out sooner, but the video folks have had technical problems supporting us. let me know if any problems. --Bill

Chess Competition Scores on Frontdesk

You should check that your score was correctly entered; the script that processes the scores is known to get a few wrong each semester. Direct general questions to the discussion board. If you think an error was made in calculating your score, please contact your TA.

Tuesday, December 02, 2008

Grade Stats Updated

The grade statistics file has been updated to include midterm2, quiz4, compression, and socialnet grades.

Monday, December 01, 2008

Chess Split Submission

Since many students have been having trouble getting their competitive code to compile on Frontdesk along with the unit-tested classes, we are going to split the handin. The chess assignment that is on Frontdesk now needs to compile, pass the unit tests, and have the theory questions completed. On Wednesday, I will create an assignment on Frontdesk called chess_competition, where each pair will need to submit the final version of the code you used on the server (it does not need to compile). You will not recieve points for BachChoy/JackBach/211 pool without submitting the final version of your code to the chess_competition assignment. Direct questions to the discussion board.

Tuesday, November 18, 2008

Change of Office Hours

I have a meeting today that I fear will run late so I am moving my 5-6pm office hours to 6-7pm for tonight only. (still 8th floor wean) Leigh Ann

Sunday, November 16, 2008

Redownload Chess Stubs

There was a bug in the starter code for the chess assignment. You should redownload the stubs from FrontDesk and resubmit your code again (with the changed stubs). Thanks to the students who gave failure cases, and I apologize for the error. See the discussion board for more details.

Thursday, November 13, 2008

Chess Server Login and Results

The chess assignment will be released at midnight tonight. To play on the server you will need to create a handle: Passwords are stored in PLAIN TEXT on the chess server, so use a junk password. Once you start playing the bots, the games that count towards your score on the assignment will be displayed on on the results page:

Tuesday, November 11, 2008

Midterm 2 regrade

The answer to the Always Never Sometimes question that asked about the depth of complete binary trees should be "Never". If you answered "Never" but had points taken off, please bring your exam to any TA.

Thursday, November 06, 2008

Midterm 2 grades

The grades have now been released. The mean and median were 97.6 and 98, respectively. The min and max scores were 56 and 130 (out of 140 possible points), respectively. You can pick up your exam outside Dr. Scherlis' office daily before 3:30 pm.

Wednesday, November 05, 2008

Second Exam

The second 211 exam will be given in lecture Thursday, Nov 6. All material from the semester is fair game, but expect more material from content since the first exam. This includes basic material from Tuesday's lecture on sorting (sorry to the one person I told otherwise in recitation today). Remember, you are allowed 1 piece (front and back) of 8.5in x 11in paper with whatever you want on it.

Saturday, November 01, 2008

Practice Exam 2

We have put up the second exam from last fall as a practice exam. It is called midterm2.pdf. Answers and the practice test for the first exam are in the same directory.Link

Wednesday, October 29, 2008

Grade Stats

I have posted a file that contains the grade statistics for all quizzes, tests, and assignments that have been graded so far. It can be found here.

Graphs Due Date Confusion

There was some conflicting information about the due date of the Graphs assignment. It will be due (without the use of late days) on Thursday, Nov 13. Frontdesk and the portal should be fixed with the correct due date.

Sunday, October 26, 2008

Schedule Error

On the schedule, Quiz 4 was listed for this Wednesday (that's an error). It will occur at some point after the midterm. The course staff is deciding whether to give out 4 or 5 quizzes total (you will be able to drop the lowest either way).

Saturday, October 25, 2008

Tony's office hours

For the next two weeks, I will hold my office hours Monday at noon instead of Thursday at 1:30. Specifically, I will have office hours Oct 27 and Nov 3 instead of Oct 30 and Nov 6.

+/- for mid-semester grades

To give you a more precise view of your mid-semester grade, we have entered a new graded item in FrontDesk called "midsemester" that shows your grade with +/-. You will need to map the number reported on FrontDesk to the letter grade with the following table:
10: A+
9: A
8: A-
7: B+
6: B
5: B-
4: C+
3: C
2: C-
1: D
0: R

Wednesday, October 22, 2008

Theory question 5 removed from compression homework

Theory question 5 is now removed from the Compression homework. After several student questions about the problem, the course TAs and instructors decided that the question was poorly worded and unnecessarily confusing. All students will receive full credit for this question.

For those of you who are curious the answer is posted on the discussion page here.

- Kami

BW Transform Example

I've posted an example of transformed ASCII text to the discussion board:

Monday, October 13, 2008

Office Hours Relocated

Since there are a ton of people on the 8th floor, I'm moving my office hours to the 7th floor. Notes were left on the whiteboards of the 8th floor.

Sunday, October 12, 2008

Quiz 3 in Recitation

In this weeks recitation, Weds 15 Oct, the third quiz will be given. Anything from the semester is fair game, but expect the majority of the material to be from after the midterm.

Friday, October 10, 2008

Supplementary Burrows Wheeler Notes

I created some notes on Burrows-Wheeler compression which explain both the compression and decompression algorithms in depth (the BWTransform, Move-to-Front, and Huffman). The notes take an input of length 7 round-trip. Please post any questions regarding the notes on the discussion board.

Thursday, October 02, 2008

Exam grades

Grades have been posted. The mean and median were 95 and 97, respectively. Contact your TA to find out where to pick up your exam.

Wednesday, October 01, 2008

Midterm Topics

This is a gentle reminder that all topics covered, including red black trees, are fair game for the midterm. We have posted slides for the red black tree lecture that aren't the exact same as the ones used in class, but you may find the wiki article as a helpful resource.

Saturday, September 27, 2008

Office hours week of midterm

I will be holding my office hours Tuesday the 30th from 1:30-2:30 PM instead of Thursday the 2nd so that you have more office hours available to you before midterm 1.

Wednesday, September 24, 2008

First Exam

The first 211 exam will be given in class, Thursday, 2 October. For practice and familiarizing yourself with the format, here is last year's exam and its solution (note that not every question is answered... if you are unsure about something, ask on the DBoard or see a TA). Also, everyone is allowed to bring one 8.5x11" piece of paper (front and back) with whatever notes you want on it. You must write your own notes, but are free to discuss what is worth putting on the sheet with classmates.

Tuesday, September 23, 2008

Leigh Ann's Office Hours

Sorry all, I need to move my office hours to 7pm tonight. I have a very important meeting with the Pittsburgh Public Schools that got pushed a little later this afternoon. I will hold my office hours tonight from 7 - 8:30 tonight on the 8th floor of wean. I apologize for any inconvenience and have extended the office hours by a 1/2 hour hopefully to compensate.

Monday, September 22, 2008

FrontDesk & IE

If you are using Internet Explorer, you may have problems viewing comments on your assignment in FrontDesk. We recommend Firefox.

Friday, September 19, 2008

Quiz 2

Quiz 2 will be given during the September 24th recitation. The Lectures link on the 15-211 Portal now contains this semester's lecture and recitation slides, which you can use to help you study.

Tuesday, September 16, 2008

Homework 2: snake

Homework 2 is available on FrontDesk. It is due September 25 at 11:59 PM - please start early.

Wednesday, September 10, 2008

Lecture 5: Binary Search Trees

Slides from Lecture 5: Binary Search Trees are now available (PDF).

Lecture 4: Lists, mutability, representations

Slides from Lecture 4: Lists, mutability, representations are now available (PDF).

Lecture 3: Intro to the Analysis of Algorithms

Slides from Lecture 3: Intro to the Analysis of Algorithms are now available (PDF).

Lecture 2: Union Find

Slides from Lecture 2: Union Find are now available (PDF).

Lecture 1: Welcome and Introduction

Slides from Lecture 1: Welcome and Introduction are now available (PDF).

Friday, September 05, 2008

Quiz 1

Quiz 1 will be given during the beginning of the September 10 recitation so be sure to arrive on time. The quiz will primarily cover asymptotic analysis. This asymptotic worksheet and its solutions might be helpful for studying.

Recitation 1: Testing, Asymptotic Analysis, and Recurrences

Slides from Recitation 1: Testing, Asymptotic Analysis, and Recurrences have been posted (PPT, PDF). This recitation was given on 9/3/08. If your section did not finish the slides on recurrences and the Master Theorem, you will have the opportunity to go over these slides during the 9/10 recitation.

Recitation 0: Intro

Slides from Recitation 0: Intro have been uploaded (PPT, PDF). This recitation was given on 8/27/08.

Thursday, August 28, 2008

Using FrontDesk on Firefox 3

If you are using Firefox 3, you may get a warning that says "Secure Connection Failed. uses an invalid security certificate.". For right now, click the "Add an exception" button, and you'll be able to use the site.

Frontdesk Access Enabled

All students registered for the class should now have access to FrontDesk. Please email your TA if you do not have access and should. Homework Zero (Hello World) has been released and you should complete it to make sure there are no problems with the system.

Wednesday, May 07, 2008

Final Exam Grades

The final exam grades are up on FrontDesk. I have also updated the averages for all of the assignments in the course (including the final) on my AFS.

Sunday, May 04, 2008

Final Exam Office Hour

Office hour will be in Morewood clusters. Owen and I (Karl) will be there. Office hour will run from 8:00pm to 9:00pm (or 9:30pm if many people show up).

Saturday, May 03, 2008

Chess Results on FrontDesk

I ran the scripts and everyone should now have graded items on FrontDesk for bachchoy, jackbach, and the 211 pool extra credit. Please check that your grades are correct, and email me if there are any problems. Note that each of these items are just added to the rest of your score on the chess assignment (when we do final grades).

Friday, May 02, 2008


The chess assignment has been released. The chess server account sign-up page is now up and running. You will need to enter your andrew id, a handle for your chess server account, and a password for your chess server account. This password is not secure and should not be a password you use for anything else. Your server handle will be shown when you play games, on the ranking site (yet to be activated), and when people see who is online. You should receive a confirmation email (on andrew) after your account has been created. If you have any problems with account creation, email Owen. If you have any questions, please try ask in the appropriate thread on the DBoard.

Thursday, May 01, 2008

Old Finals

The 211 finals from 2007 and 2006 -- note that the course was slightly different then (PS, PDF).

Lecture 27: Physics and Computation

Physics, reversibility and computation(PS)

Wednesday, April 30, 2008

Professor Sleator's office hours

I'll be having office hours Thursdsay and Friday from 3pm to 5pm both days. My office is Wean 4128.

Tuesday, April 29, 2008

Chess Bot Results Page

You can determine your last 10 wins/losses/ties against BachChoy and JackBach by visiting Also, as discussed in the assignment documentation, we will be resetting the 211 pool ratings at 5pm today, Wednesday, April 30. If you wish to compete in the pool for extra credit, you will need to play at least 20 games in the pool by Friday, May 2 at 11:59pm. See the assignment documentation for how these metrics factors into your grade for this assignment.

Monday, April 28, 2008

Office hour moved

I'll have my office hour tomorrow (4/29) from 6:30-7:30 (30 mins earlier than usual) at WeH 7th floor couches. Sorry for any confusion this might cause.

Saturday, April 26, 2008

Errors in Non-Essential ArrayBoard Functions

A student recently found a bug in ArrayBoard.countOfColor() and ArrayBoard.countOfType(). If you do not use either function, then you don't have to change anything. If you do use either function (they are probably throwing exceptions), see the topic on the discussion board with the fix. I apologize for any problems this may have caused.

Friday, April 25, 2008

Office Hour Move 4/25

I have 3 project/poster/design review due within the next day so I'll be moving my office hour to Saturday (4/26) at 6:00pm-7:00pm in Morewood Clusters.

Thursday, April 24, 2008

Lecture 26: Randomized Algorithms

Primality testing, Treaps, n-queens, counting-solutions (TXT,PDF)

Lecture 25: More Chess Programming

Zobrist keys, killer moves, etc. (TXT)

Tuesday, April 22, 2008


To give you more time to work on chess, there will be no recitation this week (April 23rd), regardless of the sections. The week after will be a optional make-up quiz (April 30th), so don't forget to come to the recitation next week if you want to take the quiz. You will also be given an opportunity to complete TA evaluations on the 30th. And good luck on your chess assignment!

Cancelled Office Hours

Unfortunately, I need to cancel my office hours for today (4/22) due to a not so sudden illness. I apologize for any inconvience that this creates.

Monday, April 21, 2008

Offline TextChess Fixes

There were a few bugs with the interaction between the provided ArrayBoard class and the offline TextChess class. If you have already downloaded the stubs and want to use the TextChess class, please see the discussion board for the specifics of what was changed. If you have not yet downloaded the stubs or you only care about playing on the chess server (online), then you don't have to do anything. Sorry for the inconvenience. Direct questions about these fixes to Owen.

Wednesday, April 16, 2008

Tuesday, April 15, 2008

Lecture 24: Chess Programming

Chess Programming (TXT,PDF)

Lecture 23: Games II


Lecture 22: Games

Basic game searching and alpha-beta (TXT)

Tuesday, April 08, 2008

Tomorrow's recitation change

For tomorrow's section, Owen's going to be at section H, and Daegun's going to be at section D. Also, for those who didn't realize yet, we will have a quiz on graphs, so make sure you come to the recitation. Good luck!

Tuesday office hour change

I need to move my office hour today. I will be holding it 2 hours later at 9:00-10:00, at Wean Hall 8th floor couches.

Monday, April 07, 2008

Graphs Recitation Material

The slides and handout from last recitation on graph algorithms are now posted.

Thursday, April 03, 2008

Lecture 21: Graphs IV

A more detailed exploration of depth first search. (TXT, PDF)

Wednesday, April 02, 2008

Tuesday, April 01, 2008

Thursday Office Hour Change

I need to move my office hours this Thursday on account of an evening exam. I will be holding them 30 minutes earlier at 4:30-5:30, and will be unable to stay past 5:30.

Lecture 20: Graphs III

This is a lecture on all-pairs-shortest-paths, and on minimum spanning trees. (TXT PDF)

Lecture 19: Graphs II

Single-source shortest path algorithms (PS)

Monday, March 31, 2008

Late Days

Since some of you are going to be asking about late days for compression, here is our policy:

You are only allowed to use a late day if both partners can use a late day. If one partner has used all of their late days, even if the other partner has all five remaining, no late days can be used.

The other thing that you should be aware of is that there will be no late days allowed on the last assignment, so for compression and the next assignment, we will allow you to use up to three late days (rather than the standard two).

Wednesday, March 26, 2008

Possible Office Hour Location Change

There are 15-451 group presentations this week, which, as you may remember, were in my office hour room (WeH 3130) last time. If the room is occupied again, I'll be holding office hours near the Wean 7th or 8th floor couches (depending on which one is available).

Tuesday, March 25, 2008

Lecture 18: Graphs

Introduction to graphs PS

Lecture 17: Quicksort

Quicksort PS

Lecture 16: Sorting

Introduction to sorting PS

Wednesday, March 19, 2008

Recitation 9: LZW & Burrows-Wheeler

LZW Burrows-Wheeler

Burrows-Wheeler Transform Header

We did not fully specify the Burrows-Wheeler Header format in the assignment writeup, so please follow this addendum: Your header must be the first four bytes of the transformed files. It stores the start index value from highest order byte to lowest order byte. The provided example files reflect this header format for comparison purposes. Sorry for any confusion this caused.

Monday, March 17, 2008

Office hour moved for this week

I'm moving my office hour on 3/18 to 9:00 PM on Thursday, at WeH 8th floor couches. This change is for this week only.

Thursday, March 06, 2008

Lecture 15: Burrows-Wheeler Compression

We describe the Burrows-Wheeler compression algorithm (html, PDF)

Tuesday, March 04, 2008

Midterm Grades

Midterm grades are up, scores weren't all that bad.

Average: 65.8% Max: 95%

Tomorrow in recitation you will get your exams back and we will go over the questions. If you happen to put down the wrong section, there is a chance another TA will have your exam.

Here is a histogram:

Monday, March 03, 2008

Practice Midterm Solutions If you have any questions, please post them on the discussion board and/or email a TA.

Lecture 14: Compression II

This lecture reviewed Huffman trees, discussed Kolmogorov-Chaitin complexity,
and described the Lempel-Ziv-Welch (LZW) algorithm. (PS)

Saturday, March 01, 2008

Practice Midterms

Note that the material covered varies per semester, and so not all of the problems on these exams will be relevant.

Asymptotic Handout

Made an asymptotic handout last semester, it is at: Handout and answers are in there. Contains some sample problems on using masters theorem, solving recurrences. Explanations are quite thorough if you had trouble understanding some of it the first time.

Super Office Hour

UPDATE: Room = Wean 5419 cluster. We, the TAs, will be holding a very large "office hour" tomorrow, Sunday, from 3-4:30pm. There will be no formal review session for the exam. If you want us to go over material at the office hour, please come with specific problems or questions.

Office Hours Canceled #2

My office hours on Tuesday 3/4 will also be canceled in favor of grading the midterm. If anyone has questions, feel free to email me.

Friday, February 29, 2008

Office Hours Canceled

My office hours on Tuesday 3/4 will be canceled in favor of grading the midterm. I won't be rescheduling them for later in the week, due to Spring Break, but if anyone has questions, feel free to email me, otherwise I will hold them on my regular night and time after we get back.

Wednesday, February 27, 2008

Midterm Cheat Sheet

As has been typical of 211 in the past, we will be allowing students to bring one 8.5 x 11 standard sheet of paper to the exam with whatever you choose on it. You may use the front and back of said sheet; handwriting or typed is fine. Like the homework, we encourage you to discuss course material together, but you must make your own sheet. If you have questions, or need something clarified, please post in the topic on the Discussion Board.

Midterm Cheat Sheet

As has been typical of 211 in the past, we will be allowing students to bring one 8.5 x 11 standard sheet of paper to the exam with whatever you choose on it. You may use the front and back of said sheet; handwriting or typed is fine. Like the homework, we encourage you to discuss course material together, but you must make your own sheet. If you have questions, or need something clarified, please post in the topic on the Discussion Board.

Lecture Notes

Additional copies of the lecture notes are outside of Wean 4116.

Lecture 13: Huffman Compression

Lecture 13: information, codes, Huffman compression 6up

Lecture 12: Heaps

Lecture 12: Order statistics and heaps 6up

Lecture 11: 2-3-4 Trees

Lecture 11: 234-Trees 6up

Recitation 7: Huffman Compression


Friday, February 15, 2008

Additional Office Hour 2/15

I will hold an additional office hour Friday 2/15, 4:00-5:00+pm in Morewood Clusters.

Thursday, February 14, 2008

Lecture 10: Binary Search Trees II (Splay Trees)

Binary Search Trees II (PDF) (TXT)


If you are interested in Uri Dekel's improvements to Eclipse contact him at More information can be found at Uri's home page. Your cooperation is much appreciated.

Wednesday, February 13, 2008

Recitation 5: Dynamic Programming

Here are the solutions to the problem that we worked on in recitation. However the way to do dynamic programming problems is not to just look at solutions. The way to get good at them is to do a bunch of examples.

Tuesday, February 12, 2008

Lecture 5: Hashing (Open Addressing)

Hashing (Open Addressing)

Lecture 4: Hashing (Chaining)

Hashing (Chaining)
Professor Sleator also presented this implementation in java.

Lecture 3: Recurrences/Stacks/Queues

This lecture was based on pages 7 through 10 (panels 36 though 56) of Lecture 2.
Additionally these slides were used to cover stacks and queues.

Lecture 9: Binary Search Trees I

Binary Search Trees I (PDF) (TXT)

Friday, February 08, 2008

Homework 3 : Part A

Here is part A of the dynamic programming homework. This is due at 12:00 NOON (at the beginning of lecture) on Tuesday, February 19. You may not use late days for this part of the homework and you must print out this worksheet and work on it.

Sunday, February 03, 2008

Office hour changed

I'm changing my office hour permanently from Thursday to Tuesday, 7:00 - 8:00, starting from this week. So the next office hour will be on Feb 5th, at WeH 8th floor couch. There will be no change after this. I am sorry for any confusion.

Friday, February 01, 2008

Clarification of Snake Theory Question 2

One of the theory questions for snake says "State a tight Big-Oh bound for..." Please be sure to also explain your answer.

Thursday, January 31, 2008

Lecture 6: Dynamic Programming I

Dynamic Programming I Make sure to do all the exercises.

Wednesday, January 23, 2008

Tuesday, January 22, 2008

Sunday, January 20, 2008

HW0 Reminder

Just in case some of you have forgotten, you should submit your Hello World program to FrontDesk and familiarize yourself with FrontDesk's features before the first real assignment is released. You can access FrontDesk through the 211 Portal, or via