4050 Design and Analysis of Algorithms I.

Syllabus

Overview:    This course reviews and extends earlier work with linked structures,
    sorting and searching algorithms, and recursion. Graph algorithms,
    string matching, combinatorial search, geometrical algorithms, and
    related topics are also studied.

Textbook:    T. Cormen and C. Leisorson and R. Rivest, and C. Stein, Introduction to Algorithms, Second Edition.    MIT Press.    

Prerequisites:    CS 2050 and Math 226  (new number ?)

Topics:    1. Introduction to Algorithm design and analysis            (1 lecture)
    2. Mathematical Foundations: Asymptotic notations, summations,
    and recurrence relations                                                            (2 weeks)
    3. Various sorting and order statistics algorithms                        (2 weeks)
    4. Data Structures: Elementary linked structures, hash tables, binary
    search trees, red-black trees                                                    (3 weeks)
    5. Advanced Design and Analysis Techniques: Dynamic programming,
    greedy algorithms, amortized analysis.                                    (3 weeks)
    6. Selected Topics: Graph algorithms, number theoretic algoithms,
    and string  algorithms.                                                            (As time permits)                

Prepared by:    Youssef Saab

Date:    September 2004

This course reviews and extends
earlier work with linked structures, sorting and
searching algorithms, and recursion. Graph
algorithms, string matching, combinatorial
search, geometrical algorithms and related
topics are also studied. Prerequisite: CS 2050
and MATH 2320.