CIS 675 home page

CIS 675
 Design and Analysis of Algorithms  

Tuesday 17.30 -- 21.00, 4-201 Center for Science and Technology

Prof. Howard A. BLAIR

Rainbow Line

Office: 3-185 Center for Science and Technology
Clinic Hours :
Tuesday 19.30 - 20.00
Tuesday 21.00 - 22.00
and by appointment.
Syracuse University
Syracuse, New York 13244-4100 USA
Phone: 315.443.3565
Fax: 315.443.1122
Email: blair at ecs.syr.edu

UPDATES and NOTICES:

  • Midterm Answer and Final Study Guide (.pdf)

  • DivideAndConquer.pdf

  • Jim Royer's Homework number 1

  • Answers to Homework number 1

  • Jim Royer's Homework number 2

  • Answers to Homework number 2

  • Jim Royer's Homework number 3

  • Answers to Homework number 3

  • Jim Royer's Homework number 4

  • Answers to Homework number 4

    • Workbook


    Course Objective and Purpose

    • The Objective of this course is to equip participants the tools to assess the resource complexity of algorithms, the complexity consequences arising from choice of data structures, and methods of design and verification.

    Course Outcomes

    Upon completion of the course participants will:

    • be familiar with fundamental computational compexity classes and reducibilities (program transformations).

    • be able to asymptotically characterize the resource complexity of algorithms.

    • have knowledge of Divide and Conquer, Dynamic Programming, Greedy algorithms, and basic data structures such as queues, stacks, binary search trees, hashing.

    • be able to analyze resource complexity of search and sort algorithms, greedy algorithms and dynamic programming algorithms.

    • be familiar with the use of invariants in verifying algorithms.

    Syllabus


    Bibliography

    • (Required) S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algorithms. McGraw-Hill, 2008. (The 2006 edition - which is adequate - is available on the internet.)

    • (Required) Ian Parberry and William Gasarch. Problems on Algorithms, (2nd edition), 2002. (Available on the internet.)

    • (Recommended): Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms. The MIT Press; 2nd edition. ISBN-10 0262032937

    • (May be helpful): Richard E. Neapolitan and Kumarss Naimipour: Foundations of Algorithms. D C Heath & Co, 1996. ISBN-10: 0669352985

    • (Helpful review of undergraduate discrete mathematics for computer science. An edition is currently used in CIS 275. Consult the SU Bookstore. Earlier editions are OK. Lots of exercises on discrete math, graph theory, proof techniques. Expensive.): Rosen, Kenneth H.: Discrete Mathematics and Its Applications with MathZone, McGraw-Hill Science/Engineering/Math; 6 edition (July 27, 2006) Eariler editions are OK. ISBN 0073312711. 910 pages!!

    • (May be helpful): Gilles Brassard and Paul Bratley: Fundamentals of Algorithmics. Prentice Hall, 1995. ISBN-10: 0133350681

    • (Advanced text. Deeper material on models of computation, formal languages, computability and computational complexity.): John Hopcroft and Jeffrey Ullman: Introduction to Automata Theory, Languages and Computation (1st ed.). Addison-Wesley, 1979. ISBN 0-201-02988-X

    • (Very advanced text. Material on computable functions, degrees of undecidability, computability. This book is the single most important mathematical introduction to the theory of computation yet written. ): Hartley Rogers: Theory of Recursive Functions and Effective Computability (Paperback edition: MIT Press, 1987. ISBN-10: 0262680521)

    Grading

    MAX(AVG(Exam1,Final), Final) defines the minumum course grade which you can earn. All parts of all questions on exams are graded on a scale of 0.0 to 4.0 i.e. F through A. Exam scores are then obtained by weighted averaging. Increasing grade trends are taken into consideration.