Introduction to Algorithms and Complexity Analysis
(Fall 2003, Lecture 01)



Paul Stelling (stelling@cs.ucla.edu)
Office:   4532M Boelter Hall
Office hours:   MW 07:00-07:45 (AM) and by appointment.
Telephone numbers:

Note: 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:

Teaching Assistant:

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:30
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!

Course Textbook:

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

Course Prerequisites

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

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 before taking 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.

Basic Grading Information

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.

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.


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.

Midterm and Final Examinations

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

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.

Related Pages

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