Fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their complexity. General topics include sorting, selection, graph algorithms, and basic algorithm design paradigms (such as divide-and-conquer, dynamic programming and greedy algorithms), lower bounds and NP-completeness.
syllabus (Midterm: in class Wednesday, March 31, Makeup Miterm: in class Wednesday, April 14, Final exam: Monday, May 17, 1:30-3:30pm.)
Homeworks are due at the start of class.
An example of suggested format when you present your algorithm pdf
Clarification: Our favorite method means to assume that algorithm doesn't return an optimal solution and show by cotradiction that it can improve the optimal solution.
Hints:For problem 2, form two vectors Q = (q1, ..., qn, 0, 0, ... 0) with n-1 zeros P = (-1/(n-1)^2, ..., -1/2^2, -1/1^2, 0, 1/1^2, 1/2^2, ..., 1/(n-1^2))
compute the convolution R = Q * P here * means convolution using FFT which takes O(nlogn). After getting the convolution, try to use that to get the result we want.
The following tips are borrowed from CMSC754, instructed by Dr. Dave Mount.
Some tips about writing algorithms: Henceforth, whenever you are asked to present an "algorithm," you should present three things: (1)the algorithm(60%),(2)an informal proof of its correctness(20%), and (3)a derivation of its running time(20%). Remember that your description is intended to be read by a human, not a compiler, so conciseness and clarity are preferred over technical details. Unless otherwise stated, you may use any results from class, or results from any standard algorithm text. Nonetheless, be sufficiently complete that all critical issues are addressed, except for those that are obvious. (See the lecture notes for examples.)