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

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

Lecture 18: Graphs

Introduction to graphs PS

Lecture 17: Quicksort

Quicksort PS

Lecture 16: Sorting

Introduction to sorting PS

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.

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.

Lecture 15: Burrows-Wheeler Compression

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

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: http://www.ece.cmu.edu/~xfu/grades.pdf

Practice Midterm Solutions

https://www.cs.cmu.edu/%7E211/content/sols_f07.pdf https://www.cs.cmu.edu/%7E211/content/sols_s07.pdf 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)

Practice Midterms

Note that the material covered varies per semester, and so not all of the problems on these exams will be relevant. https://www.cs.cmu.edu/~211/content/midterm_f07.pdf https://www.cs.cmu.edu/~211/content/midterm_s07.pdf

Asymptotic Handout

Made an asymptotic handout last semester, it is at: http://www.ece.cmu.edu/~xfu/ 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.