Introduction to Algorithms and Complexity Analysis

(Fall 2003, Lecture 01)

Syllabus

Paul Stelling (stelling@cs.ucla.edu)

Office:4532M Boelter Hall Office hours:MW 07:00-07:45 (AM) and by appointment. Telephone numbers:

310-206-2099

310-336-3537

310-378-6781Note: Please do not hesitate to call me if you have an urgent question, even if you fear it might not seem urgent to me. Also, note that I might not respond immediately to e-mail, particularly at the beginning of the quarter.

I will be off-campus most of the time. The best options for contacting me if you have questions are:

- Come to my office hours. It provides the best opportunity for us to discuss the issue, and if the question is regarding an algorithm, approach, or assignment then there may well be someone else there with the same question. I realize that the office hours I have selected are not the easiest for some (many/most(?)) students to wake up for, but since I am usually not on campus (and as a result cannot have a drop-in policy), I wanted to pick a time when there would be minimal conflict with other courses. I believe there are no courses during the selected time slot. ;-)
- I will usually be available for a short while after each class, but don't rely on this because there are some days when I will have to leave quickly for a meeting or an appointment.
- Call me at the phone numbers above. If I cannot discuss your question with you right away, then I will tell you a time when you can call me back or we can meet.
- Send e-mail to me and/or the TA. If I can answer the question quickly via e-mail I will, otherwise I may ask you to call me. I will often be unable to check class email during the day, but will check it most evenings.
- Check the announcements and the questions and answers at this web site. If a number of students have already asked your question, I may have posted an answer/explanation.
- Whatever else you do, make sure you get your questions answered. I cannot help you if you do not contact me. At the least, call or e-mail me, and if necessary we can make an appointment to meet to discuss your questions.

Shailesh Vaya (vaya@cs.ucla.edu)

Office:4428 Boelter Hall. Office hours:W 14:00-16:00 Telephone number:310-825-2518 If you cannot make it at the regularly scheduled times, appointments are welcome: simply e-mail the TA and propose a time!

Robert Nelson (rlnelson@cs.ucla.edu)

Office:4428 Boelter Hall. Office hours:

Tu 10:30-11:30

Tu 18:00-19:00

W 10:30-11:30Telephone number:310-825-2518 If you cannot make it at the regularly scheduled times, appointments are welcome: simply e-mail the TA and propose a time!

Required:Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Second Edition, McGraw Hill/MIT Press, 2001.Optional:Manber, Introduction to Algorithms, A Creative Approach, Addison-Wesley, 1989.

Junior standing in computer science, classes in or knowledge of the following topics:

- Discrete (Mathematical) Structures and proofs, as covered in Math 61, and
- Data Structures and Programming, as covered in CS 32 (Intro to Computer Science II).
These are definitely relevant and required. Skills from those courses such as the ability to do proofs by induction, to understand recursive programs, and to handle recurrence relations are crucial.

If you are weak in these skills, please review that material ASAP.

If you have not had these courses (or equivalent at another school) then I strongly suggest that you do so

beforetaking CS 180. Doing so will greatly improve your ability to both get more out of the course and to earn a better grade.

The purpose of the course is to introduce fundamental techniques and viewpoints for the design and the analysis of efficient algorithms, and to study important specific algorithms. The course relies heavily on mathematics and mathematical thinking in two ways. First, as a way of proving properties about particular algorithms such as termination and correctness. Second, as a way of establishing bounds on the worst case (or average case) use of some resource, usually time or space (memory), by a specific algorithm or by an optimal algorithm.

The objectives of this course are to first gain an understanding of the basics of complexity analysis and then to use that understanding in the analysis of known solutions and approaches to solving a variety of classical problems (e.g., sorting, some graph problems, string matching, dynamic programming). Our focus will be as much on tools and techniques for finding efficient algorithms (where possible) as on learning how to use known algorithms.

Daily Quizzes 10% Homework 20% Midterm Exam 30% (Date, Location TBA) Final Exam 40% (M 8 Dec 2003, 11:30-14:30, Location TBA) Classroom participation will also be taken into consideration in determining grades. (Up to 5% bonus may be awarded for classroom participation and office hours questions.)

There will be up to 9 homework assignments.

- I normally require that homeworks be done individually. However, you may work with a (one) partner, so long as you clearly state who your partner was on the top of the front of the first page of your turned in assignment. To the extent that homeworks are used for grading, this is essential.

I cannot recommend strongly enough that you do these assignments by yourselves.

Students who are not tackling the problems themselves will not get as much from the course. Working on the exercises, and sometimes knocking your head against them, is an integral part of the course.- Fold the completed homeworks in half vertically and put your name at the top of the outside. If the completed homework consists of multiple pages, then they
be stapled together, not folded at the corner. Otherwise we cannot be responsible for lost pages.must - Homework assignments should be turned in (preferably) by putting them in the homework box for the course in room 4428 Boelter Hall, or (alternatively) by bringing them to class on or before the due date.
- Each homework has a due date and time, and the homeworks are designed so that the due date is realistic. Recognizing that special circumstances do sometimes arise, each student is allowed one late homework, which must be turned in to the homework box (or given to the TA) by 17:00 the day after the assignment was due. This is a large class, and late homeworks can be very problematic for the grader, so
no other exceptions for late homeworks will be made.It is clearly not a good idea to consider the extension period as thede facto due date, since you can only use the late privilege once.- It may be that as few as two or three
arbitrarilyselected questions from each homework will be graded. Do not try to guess which problems will be graded and do only those. First, completing all of the assignments is an important part of learning to use the techniques and algorithms covered in the class. Second, the graded problems will bearbitrarily selected, notrandomly . Thus we may opt to grade the problem that the fewest of you turn in (or we might not). For further information on the difference between arbitrary and random, attend the first few lectures where we will cover (among other things) the concept of an adversary. Third, some of the quiz problems will be based on homework problems, consisting of a homework problem verbatim, or a homework problem with different values, or building on concepts presented in a homework problem.Solutions to the homeworks will be available at office hours and handed out at the discussion section following the due date.

Please read your homeworks soon after getting them. I sometimes make mistakes and the sooner you ask me about anything questionable, the better for all of us.

Thanks.

There will be a number of (unannounced) quizzes given during the normal class hours (not at discussion sections).

Quizzes are closed book and closed notes.

Quizzes are to be done individually (no collaborating!).

Each quiz will be short (usually ~5 minutes). Quiz problems will be based on the text material to be covered in the lecture, or on homework problems, consisting of a homework problem verbatim, or a homework problem with different values, or building on concepts presented in a homework problem. Thus, it is important that you do all of the homeworks, and that you review the posted answers before the next class.

The Midterm examination may have both "closed book" and "open book and open notes" sections.

The Final examination will have both closed book/notes and open book/notes parts.

I normally include two types of problems on examinations. The first type tests your understanding of concepts and algorithms covered in class, discussion, or the assigned readings in the text or handouts. This type of question usually appears on the closed book part of the examination. The second type of question requires that you develop an algorithm to solve a problem, or otherwise apply analytic skills to use and extend concepts covered in class or discussion. This type of question usually appears on the open book part of the examination.

The Midterm and Final examinations are to be done individually (no collaborating!).

In the past, the exams for this class have been long and difficult, the mean grade being around 65%. I try to make the exams interesting, but also difficult so a single dumb mistake will not make a big difference in one's final grade. Maybe as I approach senility, I will find it difficult to dream up new difficult problems, so I am not guaranteeing difficult exams.

Class attendance is not required. However, you are responsible for all material covered, assignments given, announcements made, etc. Also, this course is as much about learning approaches and techniques for finding efficient algorithms, i.e., the process of studying and understanding a type of problem, as it is about learning algorithms that others have already derived. As a result, the subject matter gets easier with increased exposure to the material and practice solving problems. Finally,

much of the material for this class is not in the text. (It's also hard to take the quizzes if you don't show up!)

Each student should do his or her work.

This applies to the quizzes, the exams, and also to all homeworks (with the exception of one allowed partner for each homework).

Homeworks done or submitted by groups of more than two will result in a 0 grade for all submitters in the group.

Anyone caught cheating on a quiz or test will be referred to Academic Affairs/Judicial Affairs, and will have their grade appropriately penalized.

*(c)2003 Paul F. Stelling
For information about these pages, contact
Paul F. Stelling.
*