CSC 465 - 3 Semester Hours

The Design and Analysis of Algorithms

Fundamental strategies of algorithm design; the analysis of computing time and storage requirements; algorithm and program implementation and verification; program testing and profiling; the theory of computational complexity.

CSC 365

A thorough grounding in algorithm construction and evaluation is necessary for any programmer seeking to create programs that are beyond mid-sized.

Upon successful completion of this course, students will be able to:

1. Martial the skills necessary to design and implement sophisticated algorithms.
2. Analyze time, space, and other efficiency measures of software.
3. Reason effectively about the complexity measures of various problems, known and new.
4. Describe some of the properties and mathematics of complexity theory.

1. The Nature of Algorithms
   1. Coding and representation of problems
   2. Algorithm analysis techniques
   3. Computational complexity
   4. Parallel algorithms
   5. The theory of NP-completeness
2. Algorithm Design
   1. Divide-and-conquer methods
   2. Greedy methods
   3. Local improvement methods
   4. Dynamic programming
   5. Backtracking
   6. Branch-and-bound
   7. Approximation methods

1. Lectures and demonstrations
2. Readings
3. Student participation

1. Readings
2. Written papers
3. Programming assignments
4. Examinations

1. Programming assignments
2. Written papers
3. Examinations

Only readily available computer and software systems will be needed.

A.V. Aho A. V., J. E. Hopcroft, and J. D. Ullman. Data Structures and Algorithms. AddisonWesley, Reading, MA, 1983.

A.V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.

G.S. Almasi and A. Gottlieb. Highly Parallel Computing. Benjamin/Cummings, Redwood City, CA, 1989.

C. Berge. The Theory of Graphs and Its Applications. John Wiley and Sons, New York, 1962.

G. Brassard and P. Bratley. Algorithmics: Theory and Practice . Prentice-Hall, Englewood Cliffs, NJ, 1988.

G. Brassard and P. Bratley. Fundamentals of Algorithms. Prentice-Hall, Englewood Cliffs, NJ, 1988.

D.F. Elliott and K. R. Rao. Fast Transforms: Algorithms Analyses and Applications. Academic Press, New York, 1982.

M. Hall. Combinatorial Theory, Second Edition. John Wiley and Sons, New York, 1986.

R.W. Hamming. Coding and Information Theory, Second Edition. Prentice-Hall, Englewood Cliffs, NJ, 1986.

E. Horowitz, S. Sahni and S. Rajasekaran. Computer Algorithms / C++ . Computer Science Press division of W.H. Freeman, New York, 1996.

E. Horowitz, S. Sahni. Fundamentals of Computer Algorithms . Computer Science Press division of W.H. Freeman, New York, 1978.

T.C. Hu. Integer Programming and Network Flows . Addison-Wesley, Reading, MA, 1969.

D.E. Knuth. The Art of Computer Programming, Volume 1 Fundamental Algorithms, Third Edition. Addison-Wesley, Reading, MA, 1997.

D.E. Knuth. The Art of Computer Programming, Volume 2 Seminumerical Algorithms, Third Edition. Addison-Wesley, Reading, MA, 1997.

D.E. Knuth. The Art of Computer Programming, Volume 3 Sorting and Searching , Second Edition. Addison-Wesley, Reading, MA, 1998.

U. Manber. Introduction to Algorithms: A Creative Approach . Addison-Wesley, Reading, MA, 1989.

R. Sedgewick. Algorithms, Second Edition. Addison-Wesley, Reading, MA, 1988.

R. Sedgewick. Algorithms in C, Third Edition. Addison-Wesley, Reading, MA, 2001.

R. Sedgewick. Algorithms in Java. Addison-Wesley, Reading, MA, 1988.

R.E. Tarjan. Data Structures and Network Algorithms. SIAM, Philadelphia, PA, 1983.