Computer Science Department

Design and Analysis of Algorithms

CS 230 (Spring 2018)

Instructor Dr. Teofilo F. GonzalezOffice: 2119 Harold Frank Hall

Phone: 893--3849

Office hours: M: Noon - 1:00 PM and W: 2:30 PM - 3:30 PM

E-mail: teo+galg@cs.ucsb.eduThe Course Rules appear here

The Course Schedule appears here NEWS:

Using Mathematica

Under Construction DO NOT CLICK HERE

Course Outline TENTATIVE Introduction Approximation Algorithms Types Epsilon (Single Value) Approximations Polynomial Time Approximation Schemes Fully polynomial Time Approximation Schemes Methodologies Restriction Algorithmic Structural Relaxation Value Structure Local Improvement Rounding Problem Transformation NP-completeness and Reducibility Restriction, Local Replacement, Component Design Strong NP-completeness Turing Reductions and NP-hard problems Inapproximability Results (NP-hard Approximation) Amortized Complexity Skew Heaps (might not have time) Fibonacci Heaps (might not have time) Graph Algorithms Maximum Flow Algorithms Fastest Minimum Cost Spanning Tree Algorithms (might not be time) Lower Bounds (very little) Randomized Algorithms (very little) Monte Carlo and Las Vegas (very little)

Reference Books Total number of visitors to this page, since 1/7/2017, is .

[AHU(ALG)] Aho A., Hopcroft J. and Ullman J., "The Design and Analysis of Computer Algorithms",Addison-Wesley. (1976). QA 76.6 / .A36 / 1976

[AHU(DS)] Aho A., Hopcroft J. and Ullman J., "Data Structures and Algorithms",Addison-Wesley. (1983). QA 76.9 / D35 / A38

[CLR] Corman, T., Leiserson, C. E., and Rivest, R. L., "Introduction to Algorithms,"McGraw Hill, 1990. QA76.6 / .C662 / 1990

[GJ] Garey, M. and Johnson, D., "Computers and Intractability: A Guide to the Theory of NP-completeness,"W. H. Freeman and Company, San Francisco, 1983. QA76.6 / .G35 / 1983 (TEXTBOOK for second part of the course) (only available as used book).

[G] Gonzalez, T.F., (editor), "Approximation Algorithms and Metaheuristics,"Chapman-Hill/CRC Press, 2007, (TEXTBOOK for first part of course) (It is available on-line through the CS Libray for free to all UCSB students).

[G] Gonzalez, T.F., (editor), "Approximation Algorithms and Metaheuristics,"Chapman-Hill/CRC Press, 2nd Edition, May 2018 (to appear).

[H] Harel, D., "Algorithmics,"Addison-Wesley Publishing Co., 1987. QA76 / .H2833 / 1987.

[H] Hochbaum, D., "Approximation algorithms for NP-hard problems,"PWS Pub. Co., 1997.

[HS] Horowitz, E., Sahni, S. , and Rajasekaran, S., "Computer Algorithms in C++,"Computer Science Press, (1997). QA76.73.C153 / H666 / 1997

[K1] Knuth, D. E., "Fundamental Algorithms: The Art of Computer Programming,"Addison-Wesley, Menlo Park, CA (1973). QA 76.6 / K64 / v.1

[K3] Knuth, D. E., "Sorting and Searching: The Art of Computer Programming,"Addison-Wesley, Menlo Park, CA (1973). QA 76.6 / K64 / v.3

[R] Motwani, R., and Raghavan, P., "Randomized algorithms,"Cambridge University Press, 1995. QA274 / .M68 / 1995

[S] Sedgewick, R. "Algorithms,"Addison-Wesley 1983. QA76.6 / .S435 / 1983

[Sa] Tarjan, R. E., "Data Structures and Network Algorithms,"Society of Industrial and Applied Mathematics, 1983. QA 76.9 / D37 / T37 / 1983

[V] Vazirani, V.V., "Approximation algorithms,"Springer-Verlag, 2001.