CS 4820: Introduction to Analysis of Algorithms

We will have a final exam review session on Sunday, May 12, 4-6pm, tentatively in Upson B17 (pending confirmation).

Hi,
I thought I posted this already, but I guess not. I'll be cancelling my Saturday office hours for the rest of the semester because I'm traveling and don't know what days I'll be in Ithaca.
If you have a question, or would like me to hold office hours on a particular day, please send me an email (my netID is hpm36). If I get a request for OH at a time that I'm in town, I'll be glad to hold them.

Also, I might be able to hold a final review if enough people are interested (although I'm going to be out most of this week so I'm not sure when)
#office_hours

Hi Everyone,
Starting this week I'll be moving my office hours from Sunday 12-2:30pm to Saturday 9:00am-11am because of a scheduling conflict.
Also, I'll be out of town from 4/18-4/21 so my OH on 4/20 will be cancelled.
#office_hours

Hi Everyone,
I have noticed that many students are making a mistake in proving correctness of their algorithms, and that proofs are incomplete.
Please note that when you are proving that your algorithm is correct, you need to make some sort of an 'if and only if' argument.
You need to argue that if there is a solution to the problem you are trying to solve that your algorithm finds it (most of you know how to do this by now), and you also need to show that if your algorithm returns an answer, that this answer is in fact a solution to the problem you are trying to solve. Many of you are forgetting to do the second part of the proof, please make sure you do so, this is especially important when you are solving a problem by reducing it to another problem (such as in the case of max-flow/min-cut or NP-completeness).

#proofs
#homework
#exams

Hi Everyone,
Just as a note, in this course you are allowed to use any data structures and the associated runtimes for operations that are covered in the Textbook, or during lecture. Furthermore you can use basic data structures such as lists, arrays etc. without proof.

However, note that you are not allowed to use anything involving hashing (such as Hash Tables, Hash Sets etc.) unless you provide a rigorous proof of the runtime of these structures. Eg. if you want to use Hash Tables at any point in this course, you need to provide me a hash function, prove that it doesn't have a lot of hash collisions, and what it means to be amortized O(1) and analyze the cases where it isn't O(1) operation separately.
Bottom line is, if you use Hash functions, you will most likely get points off on homeworks and exams for your runtime analysis and proof of correctness.

#exams
#proofs
#runtime_analysis #homework

I have tentatively added a class that conflicts with my current office hour (tues 12-1). If I decide to keep the class I will find a new office hour time. #officehours