I submitted the grades for 331. I am assuming you can now view your grade via MyUB.

Below the fold are some of the jokes from the final exam. Almost  all of them were funny (though some of them I did not post below as I was not sure it was suitable for a public blog).

Again, it was a fun semester for me. Have a great winter break!

First of all, I had a blast teaching the course. Hope you all had fun. At the very least, hopefully you have learned stuff during the course (believe me it is going to be useful later on!)

The finals have been graded. Here are the two main statistics:

• Median: 59
• Average: 55.2

I guess the scores would have been lower if I had not goofed up, but I don’t think anyone has any reason to complain about that

You can go and pick up your finals from the CSE main office by showing your UB ID after 1pm, Friday, Dec 18.

If you have any questions/concerns on the grading of the final, please get back to me or Jeff by Tuesday as I will be submitting the grades on Wednesday. For questions 1 and 4 go to Jeff and for the rest go talk to Atri.

Now given all your scores, here is how you can calculate your grade:

1. Add up your 9 best homework scores (i.e. drop the lowest one) to get the number , which is at most . (Note that if you submitted a homework late, then it would be counted as a .)
2. Your midterm score , which can be at most a .
3. Your final exam score , which can be at most a . (Do not add the  bonus points.)
4. Your blog score , which can be at most a . If you submitted your post on time, then give yourself a . If you submitted a bit late (and I said you’ll get a late penalty), then give yourself a . Otherwise (i.e. you submitted your blog post very late, did not submit it, or did not sign up for it) give yourself a .

Your finals score out of a can be computed by the following formula:

.

Now depending on your score, you letter grade will be as follows:

• 80-100: A
• 64.3-79: A-
• 60-63.9: B+
• 54-59: B
• 49-53.3: B-
• 45-48.9: C+
• 43-44.9: C
• 39.4-42.5: C-
• 35-39: D+
• 28-34: D
• 27 and below: F

Please don’t come to me and argue about the boundaries: in a few cases the boundaries are clear but in most cases, they had to drawn somewhere.

Have a good  break!

I messed up: I thought I had an time algorithm to compute the values but I was wrong. ( time is not hard or is easy if the jobs are also sorted by their start times– i.e. in addition to being sorted by their finish times.) An time might still be possible (let me know if you find an algorithm) but Jeff and I could not figure out one after thinking about it for an hour or so today.

Given the above, I have decided to give everyone the full 15 points on that question, irrespective of whether you attempted the question or not.

The finals have been graded– they should be available for pick up tomorrow (Friday). I’ll put up another blog post later tonight/tomorrow morning with more details on the graded finals.

Sorry for the delay but the solutions to the sample final has now been posted. The solutions to the sample mid term has been online for a while.

Some of you have asked for solutions to the mid term. I wrote them down by hand on your graded mid terms individually, so go look for them there.

Good luck on the finals tomorrow.

Update (Dec 15, 8:40pm) There was a typo in the solution to 4(a). The answer should be (the last term was incorrectly stated as earlier). The link above has been updated with this change. Thanks to John K. for pointing this out.

(Guest post by Richard Carpenter)

In the final lecture we started out by finishing up the discussion on longest vs. shortest path. We came to the conclusion that while the shortest path problem can be solved in polynomial time, the longest path problem can only be done if there is a witness to state a path.  Then the path can be verified in polynomial time.

(Guest post by Dale Brosius)

In the last lecture of the semester we had a quick discussion on shrtest vs. longest path, followed by infomation on what professor Atri researches.

Shortest Vs. Longest Path

The shortest path problem can be solved by a polynomial time algorithm, but can we solve a problem asking us if there is a longest path of length in the graph?  As it turns out we can “solve” this in polynomial time, only if we are verifying a given path of length .  There is no known algorithm to solve the longest path without a witness.  This problem falls under the vs. problem.  If you find a algorithm to solve the longest path then you solved vs. and won one million dollars.

The statistics for the last two homework assignments are as follows:

HW 9:

• Average: 48
• Median: 47

HW 10:

• Average: 55
• Median: 60

For the people that did turn in HW 10, the grades were more in the right ballpark for what we’re hoping to see on the final.  Just keep in mind that you were able to earn almost half of the points from counterexamples…the exam will have a lower percentage of the points available for such straightforward answers.

Also remember that your lowest homework grade will be dropped.

Here are the slides.

My coding theory course next semester is CSE 545. Here is the webpage from the Spring 09 offering: it should give an overview of the course. You will need to get some paperwork done to get in as it is a graduate course: let me know if you are interested.

Here is an overview article on the P vs NP question by Lance Fortnow (who writes a popular theoretical computer science blog). Fortnow’s article was downloaded so many times that it even got a NYTimes article. Fortnow is now planning to write a book on   P vs NP.

(Guest post by Chienchung Huang)

Today’s lecture we continue the previous topic ” Shortest Path Problem” the following is the given Algorithm :

• Input: (Directed) Graph and for every edge has a cost (can be ) and
• Output: Shortest path from every to

(Guest post by Andrew Puleo)

As professor atri gave us at the end of last lecture, we discussed the shortest path algorithm:

• is the cost of the shortest path that uses  edges
• is the shortest path that goes through all neighbors