CS 530: Design and Theory of Algorithms

Spring 2001

Description

Analysis of algorithms. Algorithm design techniques. Efficient algorithms for classical problems. Intractable problems and techniques to handle them. See also the full Lecture Schedule

Objectives

In this course, students will study:

Adavanced data structures
General principles in the design of algorithms which are fundamental to computer science
The implementation of algorithms and the effective use of data structures
The analysis of algorithm complexity.

The primary vehicles to achieve these objectives are the study of general concepts in this area, and the application of them to important computer science areas. Students will be required to write programs to gain experience at implementing these algorithms.

Textbook

Sara Base, Allen Van Gelder, Computer Algorithms Introdcution to Design & Analysis, Third Edition, Addison Wesley Longman 2000.

Class

M.Sc. Students. (Knowledge of at least one major programming language, basic data structures, and recursion). Saturday 2:00 – 4:30, room xxx

Instructor

Badie Sartawi, sartawi@science.alquds.edu

Office: Virtual and by appointment.

Communication: A class mailing list cs530@science.alquds.edu will be created for announcements and distribution of notes, assignments, etc.

Grading

40% homeworks, labs, project, and term paper, 15% ur exam, 15% 2^nd hour exam, 40% final exam (The final will be all-inclusive).

Homeworks

There will be several readings and problem solving homeworks over the course of the semester, a programing project, and one term paper, each contributing % of your final grade. Each homework may contain some programming component. On each homework assignment, only a subset of the problems may be graded.

The best way to learn the material is by solving problems. You are encouraged to work in groups of two or three; the best way to understand the subtleties of the homework problems is to argue about the answers. Each of you should look at all the problems independently, and not just divide the problems up each time. Don't be a leech and let your partners do all the work; unless you learn how to solve problems, I promise that you will get burned on the exams and thus for your final grade.

For the written portion of the homework, only one solution should be turned in, with the partners alternating who writes it up. The scribe for each assignment must label themselves as such. Unless announced otherwise in class, any solution to a part of a homework problem that takes more than one side of a sheet of paper will not be graded. This is to save you the ordeal of trying to impress with volume instead of quality.

Some homeworks will have a problem that requires a program to be coded. These programs must be written individually; you may not share source code even within your group. The programming portion of the assignment must be e-mailed to me before the class in which the homework is due.

Contents, format, size, organization of the programming project and term paper will be dicussed in class.

I understand that everyone gets into a time bind now and then, and that accidents and troubles befall even the most dedicated student. Thus every student will get one free extension on a homework for up to a week without a late penalty. You do not have to ask for this - just write that you are using your free extension when you turn it in. Don't waste this extension or feel obligated to use it, since you will get a very dirty look if try to get another one even with a good excuse.

Re-grades: Requests for re-grading can go in either direction; I'm often quite generous when I first grade something, so please be sure that I did make a mistake before you submit your request. On the other hand, I'll always be willing to explain to you how to do any problems that you have trouble with. All requests for re-grades must come within one week of the return of the graded item. Thereafter, no requests will be considered, so be sure to pick up your returned homeworks and exams on time.

Grading

Your numeric grade shall be determined by your scores on the homeworks and exams as described above. Beyond the grade you receive on your homeworks and exams, several other factors can affect your final grade.

Extra Credit: Throughout the course, you will have a variety of opportunities to receive extra credit points: homeworks will have difficult questions labeled as extra credit, exams will contain extra questions on special topics that I cover in class, and in general I reserve the right to reward particularly clever answers with extra credit points. Extra credit is not required, and I will construct the grade curve ignoring extra-credit points. Once grades are assigned, I will consider the extra credit to boost grades up one rank. If your grade is borderline, its always good to have some extra credit to sway my decision to your advantage.

Participation

Simply put, those who participate frequently in class provide me with another source of information as to how well they are learning the material, and how much effort they are putting into the course. I can use this information to help counterbalance a difficulty with exams or homeworks. So please, lets have an active class! Class participation will never harm your grade; always ask any questions you may have about the material.

Academic Dishonesty

Because a primary goal of the course is to teach professionalism, any academic dishonesty will be viewed as evidence that this goal has not been achieved, and will be grounds for receiving a faling grade.

Tentative Lecture Schedule

Date	Class	Reading	Topic
	1	Chapter 1	Analyzing Algorithms and Problems
	2		Quiz 1
		Chapter 2	Data Abstractiona and Basic DS
	3		Quiz 2
		Chapter 3	Recursion and Induction
	4		Quiz 3
		Chapter 4	Sorting
	5		Quiz 4
		Chapter 5	Selection and Adversary Arguments
	6		Quiz 5
	7	Chapter 6	Dynamic Sets and Searchning
	8	Chapter 7	Graphs and graps traversal
	9	Chapter 8	Graph Optimizationa nd Greedy Algorithms
	10	Chapter 9	Transitive Closure, All pairs Shortest Path
	11		*1^st hour exam*
		Chapter 10	Dynamic Programming
	12	Chapter 11	String Matching
	13	Chapter 12	Polynomial and Matrices
	14	Chapter 13	NP – Complete problems
			*2^nd hour exam*
	15, 16	Chapter 14	Parallel Algorithms (Term Paper)
			Presentation of projects & term papers