CSE 340 Design & Analysis of Algorithms (3)

Instructor:  Hector Munoz-Avila

Current Catalog Description
Algorithms for searching, sorting, counting, graph and tree manipulation, matrix multiplication, scheduling, pattern matching, fast Fourier transform. Minimum time and space requirements are established, leading to the notion of abstract complexity measures and the intrinsic complexity of algorithms and problems, in terms of asymptotic behavior. The question of the correctness of algorithms is also treated.

Textbook
Anany Levitin , Introduction to the Design & Analysis of Algorithms, ISBN 0-201-74395-7, Addison-Wesley.

References
Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest,,Clifford Stein, Introduction to Algorithms, 2nd edition, ISBN 0262032937, MIT Press.

Course Goals
Teach students the notion of abstract complexity measures and the intrinsic complexity of algorithms and problems, in terms of asymptotic behavior, the correctness of algorithms, and techniques for design of algorithms.

Prerequisites by Topic
Math 22 (Calculus) and CSE 261 (Discrete Math).

Major Topics Covered in the Course
Computing the complexity of recursive procedures
Greedy Algorithms and their complexity
Brute-Force Algorithms and their complexity
Divide-And-Conquer Algorithms and their complexity
Sorting Algorithms and their complexity
Intractability: NP-Completeness
Decrease-and-Conquer Algorithms and their complexity

Laboratory projects (specify number of weeks on each)
 none
 
Estimate CSAB Category Content
                                                                   CORE       ADVANCED
Data Structures                                                                      1.0  
Computer Organization and Architecture
Algorithms Software Design                                                   2.0  
Concepts of Programming Languages   
 
Oral and Written Communications
Doesn’t apply; students have a weekly homework and students present their solutions in class)
Every student is required to submit at least  ____written reports (not including exams, tests, quizzes, or commented programs) of typically  ____ pages and to make  ___  oral presentations of typically  ___  minutes duration. Include only material that is graded for grammar, spelling, style, and so forth, as well as for technical content, completeness, and accuracy.
CSE 340 cont’d

Social and Ethical Issues
Doesn’t apply

Theoretical Content
NP-completeness, polynomial reductions: 10% of the course.
Correctness proofs of various algorithms (e.g., Djikstra’s shortest path, Prim’s Minimum Spanning Tree): 20% of the course.
Obtaining the complexity of algorithms: 25% of the course.

Problem Analysis
Study of lower bounds for solutions, extracting recursive equations for the complexity of algorithms: 20%

Solution Design
Design of algorithms by using: greedy techniques, divide-and-conquer, decrease-and-conquer, brute force: 25%