Computer Science 4625 : Advanced Algorithms
Course Outline Fall 2000

Make up classes
Friday March 30, 10:00-11:00, E519
Monday April 02, 10:00-11:00, D635

 
 

Time of Lectures:	TuTh 9:25-10:40		Room: PE254
Instructor:	Dr. M. Mouhoub		Office: D520
Office hours:	MF 2:00-4:00,  or by appointment
Text Required:	Introduction to Algorithms,
	T. H. Cormen, C. E. Leiserson and R. L. Rivest
Text Recommended:	Data Structures and Algorithms Analysis in C++,
	2nd edition, by Mark Allen Weiss
Method of Evaluation:	Assignmentsand projects	30%
	Midterm Exam(02/27/01, 9:25-10:40)	30%
	Final Exam(04/23/2001, 2-5pm)	40%
Grade Assignments:	F<50<=D-,D,D+<60,C-,C,C+<70<=B-,
	B,B+<80<=A-,A,A+.

Topics(as time permits)

1. Introduction
2. Mathematical Fundations and Algorithm Analysis
3. Sorting and Order-Statistics
4. Advanced Design and Analysis Techniques
• Devide and conquer, Dynamic Programming, Gredy Algorithms, Randomized Algorithms, Backtracking Algorithms, Amortized Analysis.
5. Graph Algorithms
• Depth-first search, Breath-first search, Backtracking, Branch-and-bound, Minimum Spanning Trees, Single-Source Shortest Paths, All-Pairs Shortest Paths, Network Flow Problems.
6. Advanced Data Structures
• Binomial Heaps, Fibonacci Heaps, Disjoint Sets, Red-Black Trees, Deterministic Skip Lists, AA-Trees, Treaps, k-d Trees, Pairing Heaps
7. Introduction to Complexity Theory : NP and NP-Completeness
8. Heuristic and Approximation Algorithms
9. Algorithms for Parallel Computers
10. If time permits, topics chosen from : Probabilistic Algorithms, Linear Programing, Polynomials and Matrices, String Matching, Arithmetic Circuits, Number-Theoretic Algorithms, Sorting Networks, Computational Geometry or any other topics in advanced algorithms.

 

Programming Resources
 

1. Gnuplot
2. ddd

Other Recommended References
 

1. S. Baase and A. V. Gelder. Computer Algorithms: Introduction to Design and Analysis. Addison-Wesle Reading, MA, 3rd edition, 1999.
2. G. Brassard and P. Bratley. Fundamentals of algorithmics. Prentice Hall, Englewood Cliffs, NJ, 1996.

Notes and Policies
 

1. Information about the course appears in this Web page. Changes will be made here and  posted to the course newsgroup and  mailing list (cpsc4625a@uleth.ca).
2. Late assignments are not accepted for any reason and will receive 0 points, except for extension granted to the entire class.
3. You can discuss the assignment with other students but MAY NOT read, copy, or exchange other student's code.
4. Out-of-class help is available from your instructor and  can take one of the following ways of communication:
1. face to face: please respect in this case the office hours posted in this web page and on office door,
2. through email to the instructor or using the course mailing list,
3. or on the course newsgroup.
5. Attendence is expected in lectures. Little time is available to assist those who have

     missed relevant classes.
6. The midterm exam is closed-book and will be given during the regular lecture meeting time in the regular classroom.
7. The final exam is open-book and will be cumulative, but with more emphasis on material covered after the midterm.

About the slides

Notes   are in Compressed("gzipped") Postscript format (.ps.gz).
 

• For MS-Windows you need to install :

1. Ghostscript:  the interpreter of the Postscript language
2. and  gsview :  the  corresponding previewer .

• For other systems/platforms see the following web page  : Ghostscript and GSview

2000-08-08