CSEN 703 Analysis and Design of Algorithms

Course Information

Abstract

  • The course covers main concepts and principles of the design and analysis of algorithms. It begins with a thorough introduction of the rates of growth of functions followed by the techniques to solve recurrence relations. These techniques are used to evaluate the running time of various algorithms. Among the computational problems covered are dynamic programming and greedy algorithms, graph algorithms, string matching and NP-completeness.

     

Outline

    1. Mathematical preliminaries
    2. Divide and conquer
    3. Master Theorem
    4. Dynamic Programming
    5. Greedy algorithms
    6. Graph algorithms
    7. String matching algorithms
       

Goals

  • This course will teach the students to develop the skills required to precisely present and analyze algorithms. Students will be able to prove tight asymptotic bounds on the time complexity of algorithms. This subsumes being able to solve recurrence equations in the case of recursive algorithms. By presenting them to a host of examples and exercises, students should be able to design algorithms using any of the algorithm design methods covered in the course.

Objectives

  • By the end of this course, the student will have learned:

    • How to compute and analyze the running time of algorithms.
    • How to design efficient algorithms to solve various computational problems.
    • The fundamental concepts of complexity of algorithms.

     

     

Textbooks

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, McGraw-Hill Book Company, Second Edition, ISBN#: 0-07-013151-1

     

     

RenewSession