Posted by: atri | December 7, 2012

## Lect 39: Wrapup

Today we did a quick overview of the P vs NP question and then I gave an overview of things that I am working on. Chapter 8 in the textbook has more details on the question.

During class I talked about a survey on the P vs NP question. Here is a link to the CACM survey by Lance Fortnow.

Also some of you asked for more details about the fingerprint project. Here are some relevant slides.

It was a pleasure teaching this course: hope you guys had fun too!

Posted by: atri | December 6, 2012

## Final exam blog post

In this post I will point out some things that *I* think would be useful to you guys in preparing for the finals (as well as score well on the finals). Just stating the obvious: these are my thoughts and they are not guaranteed to work for *everyone*

In case you were not aware the finals is from noon-2:30pm on Friday, December 14 in NSC 220. (Note that the exam is for 2.5 hours and not 3 hours.) If might be better if you come in by 11:50am.

Posted by: atri | December 5, 2012

## Lect 38: Bellman-Ford Algorithm

In today’s lecture, we finished talking about the Bellman-Ford algorithm. The material is from Section 6.8 in the textbook. We also very briefly talked about the P vs. NP question.

The slides and notes have been uploaded.

Posted by: jiunjiewang | December 3, 2012

## HW8 Statistics

HW8 Stats:

Mean: 23.69
Median: 0

Questions 1 and 2 were graded by me(Jiun-Jie) and question 3 was graded by Zihe. Any questions regarding the grading of a question should be directed at the appropriate TA. If there are any questions, you can come to our office hours, recitations, or email us.

Posted by: jiunjiewang | December 3, 2012

## HW7 Statistics

HW7 Stats:

Mean: 62.28
Median: 75

Questions 1 and 2 were graded by Zihe and question 3 was graded by me(Jiun-Jie). Any questions regarding the grading of a question should be directed at the appropriate TA. If there are any questions, you can come to our office hours, recitations, or email us.

Posted by: atri | December 3, 2012

## Lect 37: Shortest Paths with Negative Edge Wieghts

Today we deduced a recursive expression for computing the shortest path costs between any vertex and a given terminal vertex assuming that the graph has no negative cycle (though it can have negative edge weights). Next lecture, we will finish the dynamic programming based algorithm. All this material is from Section 6.8 in the book.

The slides and notes have been uploaded.

Posted by: jiunjiewang | December 3, 2012

1. (40 pts)
(10 pts) counterexample for part (a)
(10 pts) counterexample for part (b)
(4 pts) part (c) Dynamic programming algorithm idea
(4 pts) part (c) Dynamic programming algorithm
(4 pts) part (c) Proof idea (for correctness)
(4 pts) part (c) Proof of correctness
(4 pts) part (c) Runtime analysis

2. (45 pts)
(15 pts) counterexample for part (a)
(6 pts) part (b) Dynamic programming algorithm idea
(6 pts) part (b) Dynamic programming algorithm
(6 pts) part (b) Proof idea (for correctness)
(6 pts) part (b) Proof of correctness
(6 pts) part (b) Runtime analysis

3. (15 pts)
If you are proving this for alpha equal to 11 or 12 the most you can earn is 5 points (3 for proof idea an 2 for the proof)
If you are proving this for alpha less than or equal to 10, you can earn the full 15 points (8 for proof idea and 7 for proof)
No credit for alpha greater than 12

Posted by: atri | November 30, 2012

## Lect 36: Iterative Dynamic Programming

In today’s lecture, we designed a dynamic programming based algorithm for the weighted interval scheduling problem. This material was from Sections 6.1 and 6.2 in the textbook. On Monday we will start talking about designing a dynamic programming algorithm for the shortest path problem where edges can have negative weights. This material will be from Section 6.8 in the textbook.

The slides and notes have been uploaded.

Posted by: atri | November 30, 2012

## Homework 10 and Sample final exam

HW10 and a sample final exam have been uploaded.