CS5084: Introduction to Algorithms

Fall semester 2017

Posted August 4, 2017
Welcome to CS 5084, a course designed to give graduate students the equivalent of an undergraduate "Introduction to Algorithms," while adding a sprinkling of more advanced concepts, to justify its graduate standing.
It also differs from the undergraduate course in assuming your programming ability is sufficient to program, on your own, the algorithms presented in class and in the text, and experiment with them. If you cannot do it---you are not ready for the course!  
There are many good reasons why this may be the case: either because your undergraduate degree is in a different area, or your CS degree is rusty---so much so that you are not familiar any more with the basic data structures needed, The specific reason matters little: if you cannot "play with the algorithms" easily. you are not ready for the course!  

There is a course for the needed preparation, CS5007, usually given in the Fall semester.

If you can do it, if you can implement algorithms and experiment with them, you will need to do it. Throughout the course! There are no set programming assignments; you owe it to yourself. I shall assume, in class and in tests, that you do this activity all the time.
It is a good place to adapt a warning by David Wells, in his book "Games and Mathematics: Subtle Connections"
"Students who do not `play around' with such new ideas, but stick to the textbook explanations and do no more than answer a few exercises, will never really become computer scientists."

The official syllabus is quoted below, from the catalog.

The unofficial word is that the syllabus is determined by (a) the catalog, (b) my preferences, (c) requests from students in the class to cover particular topics, if they are given early enough in the course and can be accommodated.

As you will see, this is not a hard course, but a seriously time-consuming one.

The time you need to invest in the course, beyond attending class, includes several activities:
---To prepare for each class meeting, Read the preparatory readings, both from the assigned text, as given in the schedule, and the class notes I post, ahead of each course meeting (normally on Friday).
---Do the Exercise Sets. They are homework, but they need not be turned in.
---Read the solution of the exercises which I prepare and post.
---Last, and it is impossible to exaggerate its importance: you need to find the time to experiment with the algorithms presented in the course, try variations, get to know them through using them.

The main component of grading made in the course is a bi-weekly test; every other week, and a final exam. The last 40--45 minutes of class time are used for a test which is based on your various readings of the past two weeks, and a comprehensive final exam.
Further details about the tests are in the page Grading Policy. (see at left).

A preliminary estimate of the schedule and readings is shown in the on-line schedule (denoted on the left as syllabus and schedule).
I expect this to change somewhat over the course duration.


Important notice: The format of the course as described above is very different from the way it was done in the past. It is likely to require changes as we go along....

From the Official Course Description:

This course covers the design, analysis and proofs of correctness of algorithms. Examples are drawn from algorithms for advanced data structures, set manipulation and searching, graphs and geometric problems. Analysis techniques include asymptotic worst case and average case, as well as amortized analysis. Average case analysis includes the development of a probability model. Techniques for proving lower bounds on complexity are discussed, along with NP-completeness. Prerequisites: an undergraduate knowledge of discrete mathematics and data structures. Note: Students with a strong CS background in design and analysis of computer systems, at the level equal to a BS in computer science, should not take CS 5084 and should consider taking CS 584 or CS 504 instead.


A suggestion: consult the material provided in the handouts (use the pointer on the left); this is likely to be of use at various stages of the course.


The following is a notice from the Director of Disability Support and Student Accommodation Services:

Policy on Americans with Disabilities Act accommodations:

If you need course adaptations or accommodations because of a disability, or if you have medical information to share with me, please make an appointment with [the instructor] as soon as possible. If you have not already done so, students with disabilities who believe that they may need accommodations in this class are encouraged to contact the Office of Disability Services(ODS) as soon as possible to ensure that such accommodations are implemented in a timely fashion. This office is located in the West St. House (157 West St), (508) 831.4908.

Provisions for student absence due to Religious Beliefs:

Massachusetts state law specifies that a student---
"who is unable, because of his/her religious beliefs, to attend classes or to participate in any examination, study, or work requirement on a particular day shall be excused from any such examination or study or work requirement, and shall be provided with an opportunity to make up such examination, study, or work requirement which he/she may have missed because of such absence on any particular day; provided, however, that such makeup examination or work shall not create an unreasonable burden upon such school."
If this applies to you, you must let me know of your need during the first week of classes.