CSC 440: Algorithms and Data Structures
Course Syllabus
Fall 1998

Instructor:

B.Ravikumar. Office: 257, Tyler Hall
Office phone: 874-5009. Email: ravi@cs.uri.edu. Office hours: T Th 11 to 12, W 2:30-3:30.

Class Time:

Tue, Thur 9:30 - 10:45, Room: WALE 224.

Teaching Assistant:

Ling Ma. Office: 134 Tyler Hall. Office hours: W Th 2 - 3. Email: maling@cs.uri.edu.

Course Overview:

This course deals with the design of computer algorithms, proving their correctness, and analyzing their running times. Topics include mathematical analysis of algorithms (summations and recurrences), sorting and searching, algorithm design techniques (such as backtracking, divide-and-conquer, depth-first search, dynamic programming, and greedy algorithms), graph algorithms (breadth-first and depth first search, biconnectivity, minimum spanning trees, shortest paths, network flow and matching), algebraic algorithms (FFT, polynomial interpolation, matrix problems using Guessian elimiation), string matching algorithms and geometric algorithms. Although the main focus of this course is on well-defined computational problems of technical nature, we will attempt to present a broader context of computational modeling and software design process of which algorithm design is an important component.

Text:

T. Cormen, C. Leiserson, R. Rivest, Introduction to Algorithms, McGraw Hill and MIT Press, 1990.

Other useful books:

• Skiena, Algorithm Design Manual. Springer-Verlag.
• Manber, Introduction to Algorithms: A Creative Approach. Addison-Wesley Inc.
• Brassard and Bratley, Fundamentals of Algorithmics. Prentice-Hall Publishing Company.
• Basse, Computer Algorithms: An Introduction to Design and Analysis. Addison-Wesley Inc.

Prerequisites:

This is a revised version of the course CSC 440 Design and Analysis of Algorithms I which has been taught every fall for the past 8 years. The major change is the inclusion of advanced data structures (reflected in the change of title) such as balanced search trees, priority queues and hashing which were covered in CSC 331. This transition year is a bit unusual since many of you have already taken CSC 331; so we will assume this prerequisite. You can do the course even if you have done CSC331. However, you should have completed CSC 212 and CSC 340 and be prepared to self-study the data structures topics and basic algorithm analysis.

Course Work:

Course work will consist of about 6 homework assignments, and 3 exams (two midterm tests and a comprehensive final exam). Some home work problems will involve program implementation. The tests and the final exam will be open-book/open-notes and in class. The tests will be announced at least one week in advance. The final exam will take place at the prescheduled time slot (given below). Please follow the guidelines below regarding the home work problems.

Homeworks are to be turned by the start of class on the due date. No late homeworks will be accepted.

All class work is to be done independently. You may discuss homework problems and general solution strategies with classmates, but when it comes to formulating/writing/programming solutions you must work alone.

Grading:

Grading will be based on home work problems, two mid-semester tests, and a final exam. The Home Work sets willweigh about 30 points, the two tests will weigh about 25 points, and the final exam about 35 points. The home work sets and the tests will have some challenging problems indicated with a (*). These problems can be omitted except by those who aspire for an A. To determine the final grade, the rest of the score will be used to assign a letter grade of up to A-. The score obtained in the challenging problems will be used as a basis for upgrading A- or B+ to A. (Note that a grade of B or below can't be upgraded to A, irrespective of the performance in the (*) problems.)

Topics covered:

The text covers the background topics on Discrete Mathematics and Data Structures in detail. We will not cover these topics, and will expect you to read them on your own. Specifically, chapter 5, 7, 8, 11, 12, 13, and parts of Chapters 23, 24, 25 and 26 will be assumed. The main focus of the course will be on units IV, VI and VII with secondary focus on units I, II and III.

Course Outline and Background Review	1 Lecture
Growth of functions and Summation Techniques (Ch. 2 & 3)	1 Lecture
Recurrence Relations (Ch. 4)	2 Lectures
Counting and Probability (Ch. 6)	2 Lectures
Sorting and Selection (Ch. 8-10)	2 Lectures
Geometric Data Structures (Ch. 15)	2 Lectures
Dynamic Programming (Ch. 16)	2 Lectures
Greedy Method (Ch. 17)	2 Lectures
Backtracking and related heuristics	1 Lecture
Review of basic graph theory, DFS and BFS (Ch. 24)	1 Lecture
Minimum Spanning Tree (Ch. 25)	1 Lecture
Shortest Path Problem (Ch. 26 and 27)	1 Lecture
Network Flow	2 Lectures
Algebraic Algorithms (Ch. 31 and 32)	4 Lectures
String Matching (Ch. 34)	2 Lectures

Some Important Dates

September 10, 1998. First meeting of this course.
September 22, 1998. Final day to add the course.
October 26, 1998. Mid-Semester. Last day to drop the course. (By this date, the first mid-semester test would be graded and returned to the students.)
December 10, 1998. Last lecture for this course.
December 19, 1998. Final Examination. (8 A.M. to 11 A.M.)
For a more detailed calendar maintained by the Registrar's office, please see http://www.uri.edu/registrar/academic_calendar.htm

Useful Links

The Stony Brook Algorithm Repository
Algorithms Information and Course materials on the Net.
An interview with Knuth, a pioneer in the study of algorithms design and analysis. You need Realaudio Player to listen.
The list of bugs in the text book.