Aho, A. V., Hopcroft, J. E., Ullman, J. D.: The design and analysis of computer algorithms. Reading, Mass.: Addison-Wesley 1974.Google Scholar
Barr, R. S., Glover, F., Klingman, D.: The alternating basis algorithm for assignment problems. Mathematical Programming13, 1–13 (1977).Google Scholar
Burkard, R. E., Derigs, U.: Assignment and matching problems: solution methods with FORTRAN-programs, pp. 1–11. Berlin-Heidelberg-New York: Springer 1980.Google Scholar
Carpaneto, G., Toth, P.: Algorithm 548 (solution of the assignment problem). ACM Trans. on Mathematical Software6, 104–111 (1980).Google Scholar
Carpaneto, G., Martello, S., Toth, P.: Il problema dell'assegnamento. Tech. Rep. 13. 81, SOFMAT, Progetto Finalizzato Informatica del CNR, Roma (1981).Google Scholar
Kuhn, N. W.: The hungarian method for the assignment problem. Naval Res. Logist. Quart.2, 83–97 (1955).Google Scholar
Lawler, E.: Combinatorial optimization: networks and matroids, pp. 201–207. New York: Holt, Rinehart and Wilson 1976.Google Scholar
Ten problem sets will be assigned during the semester.
Problem sets should be submitted in PDF format. Formatting your problem set in LaTeX will make it easier for us to read; however, any method of generating the PDF is acceptable (including scanning handwritten documents), as long as it is clearly legible.
The problem sets include exercises that should be solved but not handed in. These questions are intended to help you master the course material and will be useful in solving the assigned problems. Material covered in exercises will be tested on exams.
Guide to Writing Up Homework
You should be as clear and precise as possible in your write-up of solutions. Understandability of your answer is as desirable as correctness, because communication of technical material is an important skill.
A simple, direct analysis is worth more points than a convoluted one, both because it is simpler and less prone to error and because it is easier to read and understand. Sloppy answers will receive fewer points, even if they are correct, so make sure that your handwriting and your thoughts are legible. If writing your problem set by hand, it is a good idea to copy over your solutions to hand in, which will make your work neater and give you a chance to do sanity checks and correct bugs. If typesetting, reviewing the problem set while typing it in often has this effect. In either case, going over your solution at least once before submitting it is strongly recommended.
You will often be called upon to "give an algorithm" to solve a certain problem. Your write-up should take the form of a short essay. A topic paragraph should summarize the problem you are solving and what your results are. The body of your essay should provide the following:
- A description of the algorithm in English and, if helpful, pseudocode.
- At least one worked example or diagram to show more precisely how your algorithm works.
- A proof (or indication) of the correctness of the algorithm.
- An analysis of the running time of the algorithm.
Remember, your goal is to communicate. Graders will be instructed to take off points for convoluted and obtuse descriptions.
The problem sets include both textbook exercises and problems from the course textbook:
Cormen, Thomas, Charles Leiserson, et al. Introduction to Algorithms. 3rd ed. MIT Press, 2009. ISBN: 9780262033848. [Preview with Google Books]
LaTeX Template for Problem Sets (ZIP) (This file contains: 1 .cls file, 2 .sty files, 1 .pdf file and 1 .tex file.)