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.

The slides have been uploaded.

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.

Read More…

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

HW10 Grading Rubric

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.

Few comments:

  • The same final is exactly last year’s final exam. It was I think the hardest final exam over last three years. So the actual final this year should not be harder than this one.
  • As usual, do not use the sample final to glean anything about the coverage of topics: the sample final is just to get your familiar with the format and get an idea of the level of difficulty.
  • As we discussed earlier (and since there seemed to quite a bit of interest), you can submit Q4 on HW as a practice for T/F type questions on the finals. I will grade them and hand them back during exam week (but at least one day before the 331 exam). Also to get the maximum out of this, I would recommend that you simulate the exam situation as well as possible: Time yourself (maybe no more than 50 mins) and do not peek at the questions before you start. A clarification: Q4 is optional. Whether you do it or not will not (directly) affect your grade.
Posted by: atri | November 28, 2012

Lect 35: Weighted Interval Scheduling

Today we started with dynamic programming and the weighted interval scheduling problem. Next lecture, we will first develop the recursive algorithm and then see how to use memory to improve the runtime. The material is from Section 6.1 in the textbook.

The slides and notes have been uploaded.

« Newer Posts - Older Posts »

Categories