Description

Prerequisites for this class are CS11a, or programming experience in C or Java. CS22a is a co-requisite.

Data structures and algorithm design are essential areas of study for computer scientists. This course focuses on the design and analysis of algorithms and the use of basic and advanced data structures.

Through the introduction of the most widely used data structures employed in solving commonly encountered problems (e.g., lists, trees, and graphs), students will learn different ways to organize data for easy access and efficient manipulation. Algorithms to solve classic problems (e.g., sorting, traveling salesman problem) will be presented, as well as classic algorithm design strategies (e.g., divide-and-conquer, greedy algorithms). Computational complexity theory will be introduced for studying the efficiency of the algorithms covered in the course.

Instructor & TA

Class meetings

Monday, Wednesday 2:10pm - 3:30pm
Location: Volen Center for Complex Systems, Room 105

Textbook

Introduction to Algorithms (Second Edition) by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, McGraw-Hill, 2001. ISBN: 0-07-0131151-1. This book is similar to the first edition, so you could probably get by with only the first edition. However, when homework problems are assigned from the book, they are referenced from the second edition. It is your responsibility to ensure that you reference the second edition problems, not the first edition! Lecture notes will be posted on the class website.

Online version: There is an online version of the book available through the the university library. Click on this link and on that page select ITPro. You will be requested to type in your UNET username and password. After that you will be taken to the ITPro website. Once there type in the name of the book "Introduction to Algorithms". The textbook should be the first item in the search results.

Grading

Problem sets:	25%
Exam 1:	15%
Exam 2:	15%
Final exam:	35%
Participation:	10%



Participation means taking part in the class discussion of the problem set solutions, when the problem set is due. Not coming to class that day will negatively impact your final grade.

Problem sets

Six problem sets will be assigned during this semester (see tentative schedule for the assignments and due dates).

Because of the in-class correction, late homework will generally not be accepted. If there are extenuating circumstances, you should make prior arrangements with the instructor.

Each problem should be handwritten or typed on separate sheets of letter paper.Mark the top of each sheet with the following:
    Your Name,
    Problem Number,
    The people you worked on the problem with, if any.

Staple all the sheets together.

On the back of the last page, write your First Name, Last Name, and Campus Address.

You can download the problem sets here.
You can download the solutions to the problem sets here.

Collaboration policy

The goal of the homework is to give you practice in mastering the course material. You can form study groups and collaborate on problem sets, but you must write up each problem solution by yourself without assistance.
If you collaborate with others to solve the problem, you are asked on the problem set to identify your collaborators. If you obtain a solution through research (e.g., the Web), acknowledge your source, but you still need to write up the solution in your own words. It is a violation of this policy to submit a problem solution that you cannot orally explain.