Instructor: Pavel Pevzner (CSE) phone: (858) 822-4365, e.mail: ppevzner@cs.ucsd.edu
http://www-cse.ucsd.edu/users/ppevzner/
Time: 11:10-12:30 T/TH
Place: CTR 105
Office hours: Wednesday 3:00 - 5:00 and by appointment APM 4802
Discussion section: F: 12:20- 1:10 room CTR 212
Teaching assistants: Victor Gidofalvi (gyozo@cs.ucsd.edu, APM 3337A)
and Eric Hall (emhall@cs.ucsd.edu, APM 3337A)
Teaching assistants office hours: Victor (Monday 2-4), Eric (Tuesday 1-3)
Section ID: 434152
Textbook: Cormen, Leiserson, Rivest and Stein, "Introduction to Algorithms", SECOND Edition. The MIT Press
Grading: There will be 5 in-class quizzes and 4 homeworks. The short quizzes will be given in the end of the class. No make up quizzes will be given in case you miss a class but only your best 4 (out of 5) quiz scores will be counted in the overall grade. No late homework will be accepted. The homeworks must be the results of your own work rather that group efforts. There will be one midterm on May, 7. Grades will be determined by Quizzes (25%), Homework (25%), Midterm (20%), and Final (30%).
Logistics. The class may include material that is not covered in the textbook. Discussion sections may include material that is not covered in lectures. All material covered in lecture, in the assigned reading, in the homework, and in discussion sections may appear in the exams. Prerequisites include: CSE 12, CSE 21 or Math 15B, CSE 100 or Math 176. Other restrictions: (1) Majors only; (2) credit not offered for both Math 188 and CSE 101; (3) equivalent to Math 188. There will not be any substantive programming assignments but homeworks may involve (minimal) programming. There will be no hints provided on the homeworks during the office hours or via E.mail. There will be a discussion board http://discus.ucsd.edu/ for this course. The discussion board should mainly serve as a tool to clarify the the homework questions rather than a way to post hints and approaches to the homework problems. The discussion board will be shut down if inappropriate use occurs. "Inappropriate" includes any distribution of homework hints, solutions, or any offensive material.
Academic honesty. Cheating is not only dishonest, but also self-destructive. Plagiarism is a very serious violation. All the writing in your homeworks, quizzes, and exams must be your own work. You may not copy sentences or paragraphs from books, web pages, or any other source. If you quote anything written by anyone else, you must indicate very clearly that it is a quotation, and provide a full citation. Each student is responsible for knowing and abiding by the UCSD Policy on Integrity of Scholarship. A student violating this policy will be reported to the appropriate dean for administrative action, such as probation or expulsion from UCSD, in addition to any academic penalty imposed by the instructor in the course.
Syllabus. This is subject to change, as we go through the quarter.
Examples of simple algorithms and their analysis. Asymptotic growth. Sorting. Lower bounds for sorting on worst and average cases under the comparison model (CLRS Chapters 1-4, 6, 7, 8.1). Quicksort. The "Master Method" of solving recurrences. Inductive proofs (CLRS Chapters 4.3, 8, 9). Divide and Conquer. Multiplication algorithms. Greedy Algorithms. Single-processor job scheduling. The Minimum Spanning Tree. Prim's and Kruskal's algorithms, and use of data structures in efficient implementation. (CLRS Chapters 16, 23, 21) Graph traversal and Topological Sorting (CLRS Chapter 22). Dynamic Programming and Shortest Paths. Applications in computational biology. Single-source shortest paths . All-pairs shortest paths. Matrix Chain Product. Knapsack problem (CLRS Chapters 15, 24, 25). Intractability. Examples of hard problems. Approximation algorithms. Vertex cover. NP-Completeness. Examples of NP-complete problems, and NP-completeness proofs. (CLRS Chapters 34, 35).