Text: S. Dasgupta, C. Papadimitriou, U. Vazirani , Algorithms, MCGraw Hill
Alternative recommended text: Robert Sedgewick and Phillippe Flajolet, An Introduction to the Analysis of Algorithms, Addison Wesley, 1995.
Office Hours: MWF 12:00 - 1:00,
Office: RO 231
Phone: (510) 885 - 3886
URL: Home Page
I usually teach this course in my own way, and I will retain some of that, covering some topics which are not in the book, for example. You will get additional material for the topics that are not covered in the book.
Dasgupta et al. is a good introductory undergraduate text to the design and analysis of algorithms. Sedgewick and Flajolet is a more rigorous approach that gives a more thorough introduction to the art and traditional techniques of analysis of algorithms.
The Analysis of Algorithms is a mathematical subject, part of theoretical computer science. Though this material is theoretical in nature, it is very useful in practice and gives deep insight into why some algorithms are much better than others.
I will assign homework and collect it. If I get a reader for the class, the reader will grade your homework and the graded homework will be returned to you. If I do not get a reader for the class, your homework will be collected and graded by me on a random sampling basis. In this latter case the homework will not be returned to you because I might take a long time to have time to look at your homework. I will let you know after the first week in classes whether we have a reader for the class or not.
Some of the problems that I will give you for homework you can find solutions for on the Internet. You are strongly encouraged NOT to look up these solutions and hand it in as your own work. If I find out that you did that, you will get a zero grade and I will report you for academic dishonesty to the department and the appropriate University office. You are required to sign a contract in this class promising that you will not engage in conduct that is considered cheating in an academic environment. That includes plagiarism, copying the homework of a colleague, cheating in tests, etc.
Start the homework well in advance. Do not wait until the last moment. If you find the homework hard to complete on your own, that is a sign that you may need help in the class. Come to my office hours and I will try to help you. As a last resort, you may look up a solution on the Internet, but you must clearly state in the homework that you did so and give the exact source. If the solution is correct, (there are solutions on the Internet which are NOT correct), you will get 70% on the assignment, provided that you can explain it if challenged to do so. So you are required to at a minimum understand the solution of someone else, state clearly that the solution is of someone else, give credit to where you found the solution explicitly, and explain it to either the reader or me if challenged to do so.
All handouts for the course will be available on-line, on the web. You may view this with any web browser. There will be a midterm and a final exam.
Midterm February 6, 2017 Monday during regular class
Final March 13, 2017 Monday 9:00 - 10:50
Homework 20%, Midterm 40%, Final 40%.
You are expected to attend the lectures, though attendance will not be taken. There will be no makeup for the Midterm. If you miss the midterm then your midterm grade will be the same as your grade on the final. More generally, if your grade on the final is larger than on the midterm then your midterm grade will be automatically raised to the grade on the final.
SLO's: study of algorithms and mathematical techniques for their worst case and/or average case analysis, including quicksort, bipartite matching, max flow in networks, Dijkstra's algorithm, Kruskal's algorithm, Prim's algorithm, etc.
By enrolling in this class the student agrees to uphold the standards of academic integrity described in Academic Dishonesty Policies. If you have a documented disability and wish to discuss academic accomodations, or if you need special assistance in the event of an emergency evacuation, please contact me as soon as possible, and Accessibility Services. Information on what to do in an emergency situation (earthquake, fire, etc.) may be found in Emergency information