CS 5800: Algorithms

Hi all,
I was a great pleasure teaching such a strong group of students. Keep up the good work in your future CS classes. If you ever have any questions about CS classes or research, I will always be happy to hear from you and my door is always open. A few reminders:

1) Please, please, please log onto TRACE and fill out evaluations. TODAY IS THE LAST DAY. Only half of you did it so far, let's make it 100% ;-) It would be invaluable for me and the College to get all your input.

2) If you are around, you can pick up your exams and left-over homework during my regular office hours, this Thursday 2:45 to 4pm. Otherwise send me an email after you are back.

Hope to see you around the department next term! Happy holidays!
Emanuele
#final

Many of you have asked about the final quiz grade. The grade you see on blackboard is only a preliminary grade entered by the TA. It is not your final grade on that quiz. Please ignore it. I will do a careful pass on each homework, taking into account every request I have received. I will not be done before Monday.

From a quick glance, that class has done very well, and I am very happy with the overall performance.

Please remember to fill the TRACE evaluation. We need 100% of those, but we have 38% right now.
#quiz

Some of you have asked me to provide with extra practice problems, so here you go. Note that solving these problems it is *NOT* necessary for the next quiz. The material on the homework and seen in class should be enough. However thinking about these problems may be a good excuse to review some material.

-QUAD-PROG asks, given a system of quadratic inequalities in the variables x_1,...,x_n, whether it is possible to substitute real values to the variables so that each variable in the system is satisfied. Give a polynomial-time reduction of 3SAT to QUAD-PROG.

-A vertex cover of size k of a graph G is a set of k nodes such that every edge in G touches at least one node. VERTEX-COVER = { (G,k) | G has a vertex cover of size k}.
Show that VERTEX-COVER is NP-complete. (Hint: from each clause create a triangle.)

-Give an O(n^2 log n) algorithm for 3SUM.

-Give an O(n^2) algorithm for 3SUM.

-4SUM is like 3SUM except we look for sums of 4 numbers. Give an O(n^2 log n) algorithm for 4SUM.

-Give an algorithm that, on input a graph with m edges, lists all triangles in the graph in time O(m^{1.5}), ignoring logarithmic factors. (That is, an algorithm with run time m^{1.5} log^{100000} m constitutes a correct answer.)

-BINARY SEARCH WITH NOISE. You have to look for an element x in the set {1,...,n}. You can ask questions of the form "is x > i?". Each such questions is answered with error probability 1/4. Show how to find x with error probability at most 1/4 in time O(log^2 n) (or better).

-Assume that 3SAT has a polynomial-time algorithm. Give a polynomial-time algorithm that on input a satisfiable 3SAT instance computes a satisfying assignment. Now assume instead that 3SAT has a randomized polynomial-time algorithm with error probability 1/4. Give a polynomial-time algorithm that on input a satisfiable 3SAT instance computes a satisfying assignment with error probability 1/4.
#final

I was just told that the final exam will be held on
Dec 10 Monday (First day of final exams)
during regular class hours (6-9).

It will be the same format as the previous quizzes.

I have informed the admin people that this information should have been spread earlier.

To answer questions that came up during office hours today:
1. There will be a quiz on Monday Nov 19.
2. The quiz will cover the same material as the most recent homework, namely from greedy algorithms up to the material covered in the Nov 5 lecture. There will be no sample quiz posted.
3. We will not be posting online the solutions to the most recent homework, but you can pick them up from 1-3pm on Fri Nov 16 in WVH266.

We will also be holding office hours in WVH266 on Fri Nov 16 from 1-3pm, so you can come by then with any other questions about the class.


#quiz3 #office_hour #solution

A number of you have asked me which day the final exam will be held on. Unfortunately, I do not know. We have access to the same information as it appears on myneu and on blackboard. You may want to try to ask the registrar directly, and share the information with us when you obtain it. In the past, they post this information only much closer to December.

Hi all,
if you have got points taken off Problem set 2 because you didn't write down explicitly the minimum distance and the closest pair, but your code does print this information correctly, please email Zahra and she will give you the points back.
Good luck preparing for Quiz 2!
#quiz2

Hi,

recall that the next Quiz 2 is in a week. Given that people have done extremely well in Quiz 1 and on the homeworks, we are making Quiz 2 just a tiny bit more challenging.

We will not post the questions beforehand in the quizsample file.
Instead, make sure to review all the slides. Quiz 2 will include questions from the beginning up to including dynamic programming.

Problem set 3 has just been posted. This problem set will help you review algorithmic techniques that will be on Quiz 2.
#quiz2