When I used the collab email list to email the final to everyone, collab hijacked the attachment and made it into a link. Here is a triple back-up of the final file: [pdf] and here is the tex template [tex].

Updated at 7.05p on Mon.

Unfortunately, the lecture recording software for L25 crashed.  This means that both the annotated PDF and the webcast are not available. I have posted the original slides under the syllabus.

H9.3: You may use any NP-complete problem identified in the CLRS textbook or presented in class for this proof.

Simplification to H9.4: If you have not already solved this problem, you can solve the following one which is identical:  Let MUL(a,b) = a*b and SQR(a) = a^2.  Show that MUL(a,b) <= SQR(a) and SQR(a) <= MUL(a,b).  On the surface, it seems like multiplying is more general than squaring, but this problem shows that they are infact equivalent up to small factors.

You *can* use late days for the extra credit submission (everyone in your group will be deducted the late day).  However, you *will not* be able to use late days for the take home final exam.  This is an issue of fairness to make sure that everyone gets the same amount of time on that assignment.  Also, please be aware that the deadline will be brutally enforced by a computer.

Reminder: If you miss class, you are still responsible for keeping up with the materials by either asking your class mates for their notes, or by reviewing the posted slides and/or webcast. The class participation exercises often cover material covered in the previous classes.

Files: [pdf] [tex]

You can find more information about the beer-water problem that was discussed in class yesterday at this link.

Here are the files: [pdf] [tex]

It is due on Mon the 17th.

As I mentioned in class several weeks ago, you can submit in any pdf format on collab for H7-10. Reserve extra time to handle scanner problems and other technical issues that might arise. Use 2 pages for each answer even if the second page is blank.

Also, many people have asked about the slides and webcasts. They are now linked from the syllabus page instead of here.

Here are the files: [pdf] [tex] [clrscode.sty]

Note: the due date has been extended until Sunday @ 5p.

Here are the file: [pdf] [tex] [clrscode.sty]

Note: two typos corrected on Monday, Oct 27.

Note: H6, problem 4 corrections made on Wed, Oct 29.

Here is the pdf for P2,3,4 on the midterm. The latex template is here.

Based on requests, I can extend the deadline until 5p on Friday. However, you cannot use any late days for this submission. We want to start the grading right after.

The average was 37.5. Median was 36.

Histogram by problem for 2,3,4:

You should be able to retrieve your graded midterm via the placeholder assignment named “GradedMidterm” in Collab.

This was a “high dynamic range” exam. I have spoken to many of you, and I understand that many of you were nervous during the exam and therefore did not perform your best. I also admit that the exam format was intimidating and too long for the time period. But as Dave Evans says, exams should be learning experiences.

Therefore, to make this exam more of a learning experience, you have the opportunity this week to resubmit solutions to some of the problems. Here are the rules: You can (but do not have to) resubmit solutions to Problems 2, 3, and 4. We will re-grade your second submissions with much more scrutiny than we did the exam itself (be clear and concise). Your final score on those problems will be a weighted average between your original score and your resubmitted score. Therefore, students who did well on the original exam will still have an advantage. As I wrote in email last Thursday, you should not have discussed any of the midterm exam problems after you read my email on Thursday. If you did discuss solutions after reading the email, then you should not resubmit a solution. (Discussion includes consulting online references such as google or other textbooks for the answers.) This exam is an assessment of individual understanding. Therefore, you cannot consult external references, or give or receive unauthorized aid for this exam (with the exception of discussions you had immediately after the exam and before the email). The re-submissions are due on Friday at noon via the Collab assignment “CorrectedMidterm”. You must write each answer on a separate page.

Office hours this week will be by appointment. (I.e., the normally scheduled times are canceled).

Your exams have been graded; we are entering them in now, and working on a way to distribute them back to you. You will have this week to submit corrected solutions. More on this policy in the next post.

Averages are 24.5, 26.1, 28.4, 32.1, and 29.2.

Medians are 26, 28, 29.5, 36, 30.

The TAs are working to grade all of H5 by the office hours this evening.  You can pick up H5 solutions from Chih-hao’s desk (235 #6).   See you tomorrow!

Just to confirm, H5 is due on Friday at noon (instead of today at noon).

I have posted the L12 materials on the syllabus page, and will continue doing that instead of making individual posts from now on.

For H5, on problem 3, you can assume that a person weighs at most M pounds. As a hint, this problem uses dynamic programming; the insight is to define the right type of sub-problem. The seam carving problem might give you some ideas about the structure of the answer (i.e., define sub-problems, solve them, then review a subset of them to find the solution). On problem 1, the READ and WRITE procedures that you devise should run in O(1) time. Thus, k read and write operations would take O(k) time.

Here is the code from written in class:

import java.io.*;
public class ttt {
  public static void main(String args[]) {
    if (args.length < 2) { System.exit(1); }
    try {
        BufferedReader bin = new BufferedReader(new FileReader(args[0]));
        String line = bin.readLine();
        int M = Integer.parseInt(args[1]);
        String words[] = line.split(" ");
        int n = words.length;
        int infty = M*n;
        int lens[] = new int[n+1];
        for(int i=1; i<=n; i++) { lens[i] = words[i-1].length(); }
        //
        // first step
        int S[][] = new int[n+1][n+1];
        S[0][0] = 0;
        for(int i=1; i<=n; i++) {
           S[i][i] = M - lens[i];
           for(int j=i+1; j<=n; j++) {
             S[i][j] = S[i][j-1] - lens[j] - 1;
             if (S[i][j]<0) { while(j<=n) { S[i][j++] = infty; } }
           }
        }

        // second step: best

        int best[] = new int[n+1];
        int choices[] = new int[n+1];
        best[0] = 0;
        for(int i=1; i<=n; i++) {
          int min = infty;
          for(int j=0; j<i; j++) {
            int t = best[j] + S[j+1][i]*S[j+1][i];
            if (t<min) { min = t;  choices[i] = j;}
          }
          best[i] = min;
        }

        for(int i=1; i<=n ;i++) { System.out.println(i + " " + best[i] + " choice was " + choices[i]); }
        System.out.println("best is  " + best[n]);

        int end = n ;
        int start = choices[end]+1;
        while(end>0) {
          for(int i=start; i<=end; i++) {
            System.out.print(words[i-1] + " " );
          }
          end = start-1;
          start = choices[end]+1;
          System.out.println();
        }

    } catch (Exception e) {
       e.printStackTrace();
    }

  }
}

Slides for L11 are now posted [pdf]. The [webcast] and [ipod] movies will be posted as soon as they finish rendering.

H5 is due on Thu Oct 9. [pdf] [tex]

Please answer the following poll question about classes for Spring’09: [poll]

L10 materials are here: [slides] [webcast] [ipod]

In Tuesday’s lecture, I announced that H4’s due date was extended to Monday, Sep 29th.  Based on an excellent student suggestion, the due date will be 3p (after afternoon office hours that day).

Here are the slides, the podcast and the ipod versions of L9.

Here at 432, we take extraordinary measures to ensure that your homeworks are graded consistently and returned in a timely fashion. One TA grades each problem for all of the students; this method takes a lot more time since it involves at least three swaps of assignment packages between the TAs before they make it back to you. Handling the late assignments requires even more swaps. I also ask each of the TAs to make a written grading standard for how they plan to grade before they start marking papers. Despite all of these measures, we are still human, and some mistakes are inevitable.

You may feel temporary indignation when this happens to you. I understand. To address this, I have thought about how to construct a fair correction mechanism. Using an ad-hoc protocol in which you just complain to one of the teaching staff will not be fair. Some of you will be more pro-active and aggressive about complaining when such events occur; others may feel too shy or intimidated to raise such issues with me. Thus, an ad-hoc approach would introduce a grading bias—a side effect I am loathe to accept.

Instead, I have in mind a better mechanism that reduces the bias and also encourages you to self-check your answers. First, there are three classes of errors that are in scope:

1. Fault of fact. Your solution to a problem has been penalized. You have read the solution set and understand the solution completely. You believe your solution is correct, but that the grader has unfortunately misunderstood what you have written. (You understand the difference between what you have written and what you intended to write/mean.)
2. Fault of opinion. There is an error in your solution and you have been penalized. You believe the penalty is not commensurate with the error. If there was an error in your solution, even a small one, you probably lost one or two points. This standard is applied universally, so anyone who made an error on this problem, even a small one, lost the same points. You should have a really good reason for why the penalty is not commensurate.Another case might be that your partner did not receive the same penalty. I have received some feedback about this, and have randomly probed a few group solutions in which students received different scores. Even though you might work together and have the same idea about the solution, I have noticed that some write-ups are noticably more clear than others. Be certain this is not the case before you grieve.
3. Fault in your favor. There is an error in your solution, but you were not penalized. You have read the solution, and now understand that your original answer was incorrect.

If one of these situations has occurred, here is how you can respond:

1. Create a document -gX.pdf where X is the hw number.
2. For each grievance, on one line, clearly indicate (a) the type of error, (b) the point value of the error, and (c) your original total homework score. Below this first line, summarize in no more than three sentences why you believe an error has occurred. You may include an appendix if your case requires more description, but this summary must be convincing enough for me to understand your issue.
3. Submit this document under the optional “Grievance” assignments on collab within 2 weeks of the due date of hw X.

At the end of the semester, when I decide your grade, I will review these grievances. You must still pick your battles. If most of your grievances are “Fault of Opinions,” and say, none of your partners indicate “Fault in favor”, I will weigh them less. If you indicate a “Fault of Fact,” but your answer is indeed wrong, then you have illustrated a lack of comprehension: I will discredit your grievances. Thus, it is important for you to be sure that your case is correct, and to state your case clearly! If you indicate “Faults in your favor,” I will be duly impressed by both your understanding and your intellectualism, and be more inclined to improve your grade if you are borderline. You will also be helping me evaluate your fellow students in fair manner. If you want grading to be more fair (for those cases when you are the victim), you must be willing to acknowledge a windfall.

Finally, if your issue is that you do not understand why your solution was incorrect, even after you have read and re-read the solution set, then please come to office hours and discuss with the course staff. We would be happy to explain the solution.  Just keep the discussion oriented towards understanding the solution and not testing your grievance.

Please ignore the denominator in collab:gradebook.

For example, in H1, the gradebook indicates the assignment is out of 4 points. Unfortunately, I am presently unable to change this value from 4 to 40. I have filed a report with collab about this. Similarly, H2 is reported out of 40 points instead of 30.

For now, only rely on collab as a method of recording your raw score. If there is an error in this record, please bring your hw to a TA as evidence of a transcribing error.

Here are the slides, the podcast, and the ipod version of L8.

H4 has also been posted in pdf and in tex.

The due date for H3 is being extended until Friday (Sep 19) at noon. Enjoy!

Here is the podcast from L7. It is also available as a quicktime movie for download there, and as lecture slides.

There are small updates to H3: [pdf] and [tex].

If you have not picked up your H1 or H2, please come to office hours Wed evening. If it has been graded (you can check this on the gradebook on collab), it should be there.

Here is the podcast from L6. It is also available as a quicktime movie for download there.

HW3 files are also here: [pdf] and [tex]