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).

- Homework 1 pdf and ps . Solutions in pdf and ps .
- Homework 2 pdf and ps . Solutions in pdf and ps .
- Homework 3 pdf and ps . Solutions in pdf and ps .
- Homework 4 pdf and ps . Solutions in pdf and ps .

- Quiz 1 pdf and ps and a solution sketch in pdf and ps .
- Quiz 2 pdf and ps and a solution sketch .
- Quiz 3 pdf and ps and a solution sketch .
- Quiz 4 solution sketch in pdf and ps .

- For additional information please visit the course webpage for the previous quarter taught by Prof. Andrew Kahng.
- Some introductory notes on algorithms.
- This is a page that contains some very useful links to simulations, demonstrations, definitions, source code, lecture slides and some audio lectures.
- A usefull link for examples on mathematical induction(MI) .