Analysis of Algorithms

The course covers core material in data structures and algorithm design, and also helps students prepare for research in the field of algorithms. The topic covered will include Algorithm Analysis, Models of Computation: Random Access Machines, Stored Program Model and Turing Machine, Limits to Computation and Hashing. Due to the limitations of sequential algorithms, students will learn how to use parallel algorithms.

This course aims to introduce students to the design of algorithms as a means of problem-solving. Students will learn how to analyze the complexity of algorithms. Major algorithm design techniques will be presented and illustrated with fundamental problems in computer science and engineering. Students will also learn the limits of algorithms and how there are still some problems for which it is not known whether there exist efficient algorithms.

Upon the successful completion of this course, students should be able to:

• prove the correctness and analyze the running time of the basic algorithms for those classic problems in various domains.
• develop the skills of using standard algorithm design techniques to develop efficient algorithms for new problems.
• analyze algorithms belonging to those algorithmic paradigms for their asymptotic worst-case behavior in terms of time and space.
• apply prior knowledge of standard algorithms to solve new problems, and mathematically evaluate the quality of the solutions.
• contrast efficient and inefficient solutions and apply these distinctions to the complexity classes of problems, namely P, NP, and NP-Complete.
• analyze parallel algorithms belonging to those algorithmic paradigms for their asymptotic worst-case behavior in terms of time and space.

Textbooks:

1. UIT Lecture Slides

References:

1. “Design and Analysis of Computer Algorithms” By Alfred V. Aho, John E. Hopcroft, Jeffery D. Ullman
2. “Data Structures and Algorithm Analysis”, Edition 3.2 (Java Version) by Clifford A. Shaffer
3. “Data Structures and Algorithm Analysis in Java (3rd Edition)” by Mark Allen Weiss
4. “Design and Analysis of Parallel Algorithms” by Selim G. Akl
5. “Introduction to Parallel Computing: Design and Analysis of Algorithms” by Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar (2003)
6. “Introduction to Parallel Algorithms” by C.Xavier, Sundararaja s.lyengar