Monday, December 17, 2007

Exam grades

We have released the grades. The min,max,mean,median,mode, and std were 54,142,103.4,104,104, and 17.2, respectively. If you see a 0 in FD, and you took the exam, you need to contact us (Prof. Scherlis and me) immediately. We will be setting the final grades for the course over the next few days. So, we cannot, at this time, tell you what exactly scores will qualify for A,B,C, etc. We will have all grades entered by Friday afternoon.


Professor Scherlis taught the lecture on concurrency. You would be surprised how many people missed that question. Now I don't feel so bad that I didn't learn everyone's names. Have a nice break, whoever you are.

Saturday, December 15, 2007

Last recitation

PDF: 211Rec12-Last.pdf

Some lecture PDFs

You can get PDFs for most of my lectures at Note that these duplicate what you already have on paper and in the "thumbnail" view of the video tab. --Bill

Friday, December 14, 2007

The final

You may bring one page of notes, just like the midterms.

Thursday, December 13, 2007

Average Scores

For those of you curious about how you are doing in the course, I've posted some stats about all of the graded items. They can be found at Note that the stats are raw scores, not percentages. Also note that anyone scoring a zero on an item will not count towards the stats.

Chess Scores

I wrote a few scripts to parse the chess output and upload to FrontDesk. There are numerous places for errors in these scripts and although I looked at a few cases for correctness, you should check to make sure your scores are correct. If you have any questions or concerns, email me.

Wednesday, December 12, 2007

Exam detail

This is from the latest HUB posting, but please double check: 15211 1 FUND DATA STRUCT ALG Mon. December 17 08:30AM-11:30AM MCCONOMY. --Bill

Sample exam

Here is an sample exam and its solutions. Good Luck!

Review for Final

The review for the final will be at 4pm on Saturday, Dec 15 in Wean Hall 7500. Please post questions to the discussion board prior to the session so that the TAs know what to cover.

Recitation assignments -- IMPORTANT

It is the time of year when TAs are contemplating the assignment of TA discretionary points. If you are attending a section other than the one to which you are officially assigned in the HUB, please notify BOTH of the TAs involved, so the correct TA can assign you points for participation. Otherwise you may fall through the cracks and end up with no TA discretionary points.

Saturday, December 08, 2007

Monday Office Hours Canceled

I have an exam scheduled during my usual time for office hours on Monday. Please email me if you want to set up a meeting sometime later in the week.

Saturday, December 01, 2007

Chess Server Info

Here is a script that you can use to check to see how many times in a row you have beaten BachChoy and JackBach. It should be updated by the minute. And in case you missed it -- the account creation link. You will need to provide your andrew id, a handle for the chess server, and create a password for the chess server (not your andrew password)

Friday, November 23, 2007

Chess Fixes

It has come to our attention that there were a few minor errors in and I have fixed them and and updated the stubs, which you can use to update your code as desired. Also, I fixed up the section on the timers, which was a bit out of date. Sorry if this caused major confusion. Also, if you have questions about anything in the assignment, please check the bboard--Owen and I have been making an effort to clarify things there if they are asked.

Tuesday, November 20, 2007

Office Hours

My office hours tomorrow will be in WeH 3406 on the off chance that anyone wants to come for them.

No Office Hours Tuesday, Friday

Anthony will not be holding office hours this Tuesday due to the holiday. Also, my Friday office hours are canceled for the same reason. Happy Thanksgiving!

11/27 Anthony Office Hour canceled

Anthony's office hour tuesday (11/27) will be canceled due to break.

Monday, November 19, 2007

Quiz 4

Quiz 4 will be given during recitation next week (28th Nov). Don't forget to review your material for it! Happy holidays!

Saturday, November 17, 2007

Chess Server Account Signup

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 should not be the 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 me or Will.

Wednesday, November 14, 2007

Chess Fixed

The chess assignment should now be completely fixed. If you have any problems with FrontDesk, please email me. I made significant revisions to the assignment from last semester and obviously my testing was not sufficient the first time around. If you already started the assignment you may want to download the stubs again. Sorry for the inconvenience. Hope you have fun completely destroying the bot I wrote when taking the course as revenge!

The State of Chess

I incorrectly deployed the chess assignment to FrontDesk. We are working to correct the problem, and it will be fixed tonight. I will make another post to the portal when everything is fixed. There will be no changes to the code you need to implement (some files just need to get moved around and compiled correctly).

Exam Correction

For the compression question part c) on the exam: "For a given input, X = x1, x2, x3, ...xn, there is exactly one Huffman tree which will produce a maximal compression ratio." The official answer we graded by was "sometimes" The one instance where there is exactly one tree for the maximum compression ratio is for an empty file (only 1 such tree exists). Since we wrote "x1, x2, x3, ...xn", it is not clear that the length of the file could be 0. So if you wrote "sometimes" or "never" you should receive full credit. If you need a score correction for THIS part of the question, please contact YOUR TA for a score change.

Monday, November 12, 2007

Office Hours Pushed Back

Sorry I forgot to post this earlier, but I needed to change my office hours today and hold them from 6pm - 7pm. Sorry for the late notice!

Friday, November 09, 2007

Midterm 2 Grades Released

We have released the grades for the second midterm on FrontDesk. Both the mean and median on this exam were 64.5% (with a standard deviation of 14.0%). You can pick up your exam from Prof. Scherlis's office starting Monday. We will be devoting a portion of next recitation to going over the midterm, so pick it up before going for your recitation.

Wednesday, November 07, 2007

Additional DP and Code Analysis Questions

At the review session students requested additional practice problems on Code Analysis and Dynamic Programming. So here they are: Questions: Solutions: If you have not done so already, check out the practice midterm and the recitation material from today. Both of these have more problems on Code Analysis and DP. You can access the recitation material from the "Lectures" tab on the portal.

Recitation 9: DFA / DP

Handout: Solutions: Slides:

Compression Theory Solutions

Since your compression lab will not be graded and returned until after the midterm, here is a temporary link to the theory question solutions:

Saturday, November 03, 2007

Recitation 8: Dynamic Programming

Slides: PDF:

Suggested schedule

We have found that a small but significant number of students are having trouble meeting the deadline for the assignments, so we sat down and figured out a suggested timeline for doing the project. If you are very much behind the schedule we propose, we feel that you might run out of time towards the deadline.
  • General Graph - done by the weekend
  • Union-Find - done by Wednesday
  • Dijkstra - done by Friday evening/Saturday morning
  • Kruskal - done by Monday
  • Theory + last-minute fixups, additional comments, etc - done before the deadline on Tuesday
Good luck with the assignment!

Friday, November 02, 2007

Midterm Review

The midterm review will be on Wednesday, Nov 7, 6:30-8pm in Wean 7500. Please pose questions to the discussion board in advance of the review so that the TAs know what to cover.

Partner assignments

There were a number of people who wanted partners for the last assignment, but couldn't find one. If you do not have a partner for the current assignment, and would like one, please post a request on the discussion board. Be sure that you work together; do not simply split up the work. Also, whenever you find that you are having trouble with an assignment you should talk to one of the TAs or the professors about it immediately. There is little we can do if you come to us the day an assignment is due.

Thursday, November 01, 2007

Exam Nov 8

The second midterm will be on Nov 8th. It is in-class and cumulative. Do not bring cell phones, PDAs, computers, or any other such device. Bring your student ID. You may bring a single 8.5"x11" page of notes (both sides). We will be announcing a review session shortly. Please check the portal for the announcement. We will also post an exam from a previous semester so that you have a sense of what to expect. Here is a sample midterm and its solution set.

Lecture 20: Dynamic Programming 2

Lecture 20, Dynamic Programming 2

Wednesday, October 31, 2007

Cell Phone

Cell phone was found in 15211 recitation E. Email me at if you lost it.

Tuesday, October 30, 2007

Extra office hour

Since assignment is due today, holding extra office hour to cover time lapse between Lawrence's and Anthony's + a bit extra on both sides.

Friday, October 26, 2007

Mid-semester grades

These are posted to the HUB. If you have any questions, please visit Chris or me. --Bill

Thursday, October 25, 2007

Tuesday, October 23, 2007

Lecture 17: Graphs 3

Lecture 17, Graphs part 3

Office Hours

Due to considerable amount of work, I will not be holding office hours this week.

Monday, October 22, 2007

Debugging Tutorial

On Wednesday, Oct 24, there will be an optional session on debugging tools and strategies in Wean Hall 7500. This is meant to help people who are not yet comfortable with debugging tools, or find it hard to locate bugs. Bring your laptops so that you can participate. EDIT: The session will run from 6:30-8:00pm

Friday, October 19, 2007

Course syllabus

The course syllabus (lecture schedule and readings) has been updated. Click on the "Lecture" link to the right. --Bill

Tuesday, October 16, 2007

Quiz Tomorrow

In case you have been missing lectures and recitations recently, there will be a Quiz tomorrow, (Wednesday Oct 17) in recitation. Anything from the semester is fair game. We are more likely to test you on material (a) that we haven't tested before or (b) that we think was problematic for students. With respect to point (b), note that you will have received feedback on such problematic material.

Lecture 15: Connected Components, Minimum Spanning Trees

Lecture 15, Graphs part 2

Thursday, October 11, 2007

Off-by-one error in lecture 14

I had an off-by-one error in my lecture today. Using the definitions I gave in class for the length of a path/cycle, the maximum length of a simple path is n-1, the maximum length of a simple cycle is n. Sorry for the confusion.

Lecture 14 : Graphs Part 1

Lecture 14, Graphs part 1

Lecture 13 :Compression

Lecture Lecture 13, Compression

Monday, October 01, 2007

Midterm Review

The review for the first midterm will be this Wednesday in Wean 7500 from 6:30-8 pm. Please post questions to the discussion board that you would like the TAs to go over during the review. Here is a sample midterm and its solution set.

Friday, September 28, 2007

Reminder: Late Days

If you aren't familiar with the 'late day' policy on homeworks, please read the policy You may use up to 2 days on the snakes assignment, if you need it.

Thursday, September 27, 2007

Exam next thurs

The first midterm will be on Oct 4th. It is in-class and cumulative. Do not bring cell phones, PDAs, computers, or any other such device. Bring your student ID. You may bring a single 8.5"x11" page of notes (both sides). We will be announcing a review session shortly. Please check the portal for the announcement. We will also post an exam from a previous semester so that you have a sense of what to expect. Note that, in general, we will NOT ask you to do complicated proofs. For example, you won't be asked to prove that a skip list has O(log n) complexity for finds. However, you should know a) how a skip list works, and b) the complexity of the dictionary operations on a skip list.

Lecture 10 Slides

Lecture 10, Tries and Skip Lists

Wednesday, September 26, 2007

Lost (and Now Found) Laptop Cable

I left my laptop cable by the 8th floor couches during my office hours on Monday. If anyone happened to pick it up, please email me. Thanks, --Owen EDIT: Thanks to whoever returned to cable to the recitation room before I got there... I could have sworn it wasn't in the room when I checked yesterday.

Wednesday, September 12, 2007

Recitation Slides Posted

The slides have been posted. You can get to them via the lectures tab of the 211 portal.

Recitation 2: Trees and Rotations

Slides: PDF:

Recitation 1: JUnit + Asymptotics

Slides: PDF:

Recitation Slides Coming Soon

Some students have been asking for us to post the recitation slides that have been presented up until this point. They should be up later tonight. And when they do go up, we'll let everyone know where to find them.

Monday, September 10, 2007

Office Hours Cancelled Friday

I am going to have to cancel my office hours this Friday because I will be out of town interviewing. If you need any help, please feel free to contact me via email earlier in the week.

Union-Find demo applet

If you want to play with the UnionFind demo applet, click here. The less interesting Graph Draw applet is here. (Please send me suggestions for improvement.) Enjoy -- Bill

Friday, September 07, 2007

Office Hours Switch

Sorry if this caused some confusion today, but Will and I (Owen) have switched office hours. Mine are now Monday, and Will's are Friday. There shouldn't be any more changes.

Tuesday, September 04, 2007

Lecture slides and video

Lecture slides and video are reachable from the "Video" button just to the right of this post on the portal. You'll need to do a WebISO authentication. Click "thumbnails" to see all the PowerPoint slides. The good news: If you click on any of the thumbnails, you will be navigated directly to that point in the lecture. And the bad news: you need to do this in Internet Explorer. -- Bill

Monday, September 03, 2007

Expired license in VM image

Some of you who're using the VM may be running into errors exporting your project due to an "expired academic license". The replacement license can be downloaded here. Replace the existing license with the downloaded file and you should be good to go. N.B. Use find /usr | grep clover.license to find the existing license.

Friday, August 31, 2007

Office Hours Pushed Back

Due to an unexpected event, I have to push back my published office hours today. I will be holding them from 5:30pm-6:30pm by the Wean 8th floor couches. It also appears that FrontDesk is back up.

Thursday, August 30, 2007

FD Down

Due to the water main break, SCS Facilities has decided to turn off most CS related computers. Hopefully, we'll be back up soon.

Wednesday, August 29, 2007


The CMU bookstore didn't order copies of the textbook for 211. If you want a new copy, we recommend using Amazon. You might want to try entering the promo code tb7chase, it gives an additional 10% off.

Tuesday, August 28, 2007

Welcome to 15-211

We're glad to have you in 15-211 this semester! In order to get you started, we have created a list of places you should look at in the course portal.

  1. This is the announcements area. You'll want to keep on top of announcements by either visiting the course portal or subscribing to the news feed.
  2. To the right of the announcements area is a course calendar. In addition to posting the lecture schedule, we'll post review sessions, office hours and other events that you might be interested in. Consider using the iCal feed (eg, view the calendar using Google Calendar) to keep on top of this.
  3. Below the calendar is a sampling of recent discussion board posts. You should subscribe to this so that you can search for answers and post questions. Clicking Older Posts will get you to the discussion board interface from which you can subscribe.
  4. To the left of the announcements area is a list of links. You should read the course policies and course information links.
  5. In the list of links is a Get Started guide. This will help you set up your programming environment and guide you through a sample assignment. Completion of this is required. The sample assignment is intended to help you get familiar with the infrastructure, so you can focus on the content of the course in later assignments.

Thursday, May 10, 2007

The finals have been graded, and the grades are released. The average is 67.5. The median is 67. The standard deviation is 15. Below is a histogram for the exam.

Monday, May 07, 2007

Extra Office Hours for Last Minute Questions

I'll have some extra office hours tonight for last minute questions about the exam from 7-9 PM in WeH 3130.

Thursday, May 03, 2007

Monday, April 30, 2007

Office Hours Change

I have a project meeting this Thursday afternoon and can not be at my regular office hour. I am changing my office hour for this week to Tuesday from 7pm to 9pm. Sorry for any inconvenience. Joy

Office Hours Change

I have to work on a group project tomorrow afternoon, so I'm going to have to leave my office hours around 2:00PM instead of 3:30PM. Sorry for any inconvenience.

Saturday, April 28, 2007

Graph Assignment Average

The average on the graph assignment so far is an 83.75

Friday, April 27, 2007

Final Exam Review Session

We'll have a final exam review session on Sunday, May 6 from 3-5 pm in WeH 7500. Practice exams are posted below. Please come with specific questions from previous exams or material as trying to cram 30 lectures into 2 hours is impossible.

Thursday, April 26, 2007

Old Final Exams

I posted some old final exams under Documents. This includes the last two 211 finals, which should be very similar to this semester's. I've also posted a zip of some really old finals for further practice problems. Where we had them, I posted the solutions. Remember the final is Tuesday, May 8.

Old Final Exams

S06Final S06FinalSol F06Final F06FinalSol Many more old exams ( | practice.tar.gz)

Recitation 14: Parallel Computing


Recitation 13: Game Trees and Alpha-Beta


Lecture 27: Parallel Algorithms II


Monday, April 23, 2007

Lectures in DH 2315

Lectures for both sections will be in DH 2315 this week. I'll be covering parallel algorithms.

Wednesday, April 18, 2007

My Office Hours

I did not hold office hours the past Monday due to my 36-226 midterm held in the evening. However, I forgot to make an announcement to that effect before the date. My sincerest apologies for any inconvenience caused to anyone due to my oversight.

Tuesday, April 17, 2007

Lecture 25: Chess Programming

Lecture Notes (txt)

Averages so far

We've been behind on posting averages, and I forgot what we've posted, so here it is: quiz1: 78.97 quiz2: 66.46 quiz3: 87.58 quiz4: 88.32 expr-tree: 89.45 snake: 83.89 dp-part-a: 17.75 dp-everything-else: 65.29 compression: 81.02 midterm: 70.91 These averages are computed with the people who were in the class at the time, so they might be a bit inflated after people drop. There weren't enough graph assignments graded yet [including my own section :-) ] to merit posting an average, but I'll post one soon. If I forget and it's been a while, shoot me an email. Hope everyone has a fun Carnival!

Monday, April 16, 2007

Chess Assignment Released

In case you have not noticed, the chess assignment has been released. It is due May 5 at 11:59 pm, the last day of classes. Be aware, you cannot use late days for this assignment. As this assignment is open ended and there is room for extra credit, start early and have fun with it!

Tuesday's lecture in DH 2315

Reminder: Lecture for both sections on Tuesday, April 16, will be DH 2315.

Tuesday, April 03, 2007

Lecture 21 slides

Slides (non-majors)

Office Hours Moved

I have to move my office hours tomorrow, so they will now be 7:30-9pm, instead of 4:30-6pm. They will still be in Wean 3130. Sorry for any inconvenience.

Friday, March 30, 2007

Graph Assignment Released

The graph assignment is now available on FrontDesk. It is due April 12 at 11:59PM, so you have two weeks to complete it. As many of you noticed last night, the job queue on FrontDesk can get quite long right before the deadline when a lot of people are submitting. Start early and this won't be a problem.

Thursday, March 29, 2007

Lecture 20: Minimum Spanning Tree and Union Find

Slides (non-majors)

office hour change

I have permanently shifted my office hours by 30 minutes, to 3-430, starting today.

Tuesday, March 20, 2007

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 19, 2007

Stuck in Chicago

To cut a long story short, I won't be back in Pittsburgh until late Monday night, and I need to cancel my office hours. If you have any pressing concerns, please try to contact another TA as I will not have internet access until I get back to school. Thank you

Wednesday, March 07, 2007

Midterm Graders

The following questions were graded by the people listed below. Please approach them if you have any problems/questions with the grading. Thanks
  • BST - Brett, Ryan, Joy
  • Dockyard - Danny, Lawrence, Scott
  • Stones - Jon, Alex
  • MC - Klaus, Jon
  • R/B Trees - Margaret, Will, Drew

Course Portal Updated

We have just added a 'Documents' tab to the course website. Any new materials we post that are not lecture slides or recitation slides will go in this tab. The course schedule and spring 05 midterm have been moved to the new tab.

Tuesday, March 06, 2007

Midterms are Graded!

Midterms are graded. They will be returned in recitation tomorrow (Wednesday). There was a mean of 70.42 with a median of 72.

Monday, March 05, 2007

Test Tomorrow

For the test tomorrow, can those in sections G & H show up to DH 2315 rather than the original room. 2315 is a more comfortable room so should be better to take the test if we distribute people this way. Please spread the word.

Sunday, March 04, 2007

Office Hours Moved

I'm going to move my office hours to tomorrow (Monday) since having them on Tuesday makes no sense. I'll have them from 10-11 PM in WeH 3130.

Office Hours Cancelled

I have an interview on Monday (tomorrow), so I have to cancel my office hours.

Saturday, March 03, 2007

Burrows-Wheeler Lecture Notes Posted

Lecture notes for this algorithm have been posted in the lectures area (tab to the left). You'll need this description for the just-released data compression assignment.

Lecture 16: Burrows-Wheeler Compression

Sleator (html)

Spring 05 Midterm

The spring 05 midterm has been posted online and is available under the "Lectures" tab to the left.

Spring 05 Midterm

Spring 05 Midterm (pdf)

Friday, March 02, 2007

Midterm Review

This Sunday at 3:00 in WeH 7500 there will be a review session for Tuesday's midterm. Bring your questions!

Wednesday, February 28, 2007

Monday, February 26, 2007

DP Assignment Reminder

This is a reminder that the DP assignment is due this Thursday. If you haven't started yet, you might want to think about doing so. Also, you are required to implement one of the problems bottom up and one of them top down. Each class (SubsequenceCounter, ConsoleEditor, ...) constitutes one problem.

Sunday, February 25, 2007

Cancelled Office Hours

I have to cancel my office hours this week to fly to California.

Office Hours Tomorrow Cancelled

Reminder: My office hours tomorrow are cancelled as I have a midterm to sit for at that time. Any pressing questions can be posted to the board or emailed to me. There is also a help session tomorrow from 8-10pm in WeH 5207 that you can go to if you have any problems with the homework assignment.

Saturday, February 24, 2007

Quiz 2 and Snake Average Grades

With most of them graded, the average for the dynamic programming quiz is 64.9. The average for the snake assignment is 83.3

Friday, February 23, 2007

Office Hours Reschedule

I will be rescheduling my office hours from today (Friday) to the extra help session on Monday. I am still available by email for questions.

Thursday, February 22, 2007

Lecture 12: Heaps


Cancelled office hours

I have to cancel my office hours today scheduled for 330-5. I will hold additional hours next week on Tuesday from 12-130. Sorry for any inconvenience.

Tuesday, February 20, 2007

Moving Office Hours

I have to move my office hours back on Wednesday 2/21, so they will now be 5:30 pm - 7:00 pm. Sorry for any inconvenience.

Lecture 11: Splay Trees


Monday, February 19, 2007

Class Tuesday, 20 February 2007

Reminder: Both sections will be in DH 2315 for a lecture on Splay Trees by Danny Sleator.

Saturday, February 17, 2007

Cancellation of Office Hours

My office hours for Monday 26 Feb will be cancelled as I have a mid-term to sit for at that time. Please send me an email if you have any pressing questions or concerns. Thank you.

Monday, February 12, 2007

HW 2 Reminder

This is a reminder on the Snake assignment that's due on Thursday night. There are theory questions worth 30% of your grade that you need to answer. Do not put these off until the last minute. If you're struggling, see someone during office hours.

Recitation 4: Iterators and Analyzing Runtime


Friday, February 09, 2007

Average Grades for Quiz and Expression Trees

So far the average grade for the quiz is 79.8. So far the average grade for the expression tree assignment is 89.7 Both grades are logged in frontdesk (some are still ungraded). The quizzes will be returned back in recitation next Wednesday, and there is feedback posted under Frontdesk about the assignment (please read the feedback). If you have any questions or concerns, please see someone in the course staff.

Thursday, February 08, 2007

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 20. You may not use late days for this homework and you must print out this worksheet and work on it.

Lecture 8: Greedy & Dynamic Programming III

Slides (corrected Feb 8, 4pm)

Saturday, February 03, 2007

Office Hours Change

I have a meeting this Monday during my office hours, so I'll be in and out of the office (Wean 3108) during my scheduled time. If I'm not there when you show up, you can either come back later or email me and set up a different time to meet this week.

Friday, February 02, 2007


The class schedule (subject to change) includes lecture topics and homework, quiz, and midterm dates.

Lecture 6: Dynamic Programming I


Sunday, January 28, 2007

Error in Expression Tree Assignment

If you downloaded the expression tree assignment after Friday afternoon, there is an ExponentiateExpression class in it. This was a mistake and you can just delete it. I apologize for the inconvenience.

Also, the course staff is getting alot of emails asking the same question. While we love answering your emails, we don't like answering the same question 160 times. If you have a question, you can feel free to use the discussion boards, that is what they are there for.

Wednesday, January 24, 2007

Tuesday, January 23, 2007

Class room change for the majors

The lecture room for the majors has been changed from WeH 7500 to HH B103.