Advanced Algorithm Analysis

A Course to introduce the advanced algorithm design strategies for solving complex problems

 

Course Code:              CS6401
Credit Hours:                       3

Pre-requisite:              
An undergraduate level course in Data Structures with the knowledge of any one programming language.

Target Audience:
MS/Ph.D students wishing to pursue research in a field where they will be required to design, develop and/or analyze algorithms.

 

Synopsis:             

Algorithms are essentially required for solving a wide range of computational problems from a number of different fields such as Artificial Intelligence, Data Mining, Distributed Systems and Computer Networks. This is a graduate level course on the topic of algorithms and computational complexity and covers several advanced topics not studied in typical introductory courses on algorithms. It is especially designed for students interested in pursuing careers in the field of applied computer science where they will be required to design and implement new algorithms. Course contents include the study of algorithm analysis techniques and algorithm design strategies that are currently used in a variety of application domains. At the end of this course, students should be able to design and develop new and efficient algorithms, analyze existing algorithms and select suitable algorithms for complex problem solving.

Instructor:

The course will be taught by Dr. Faraz Zaidi (faraz@pafkiet.edu.pk) who holds a masters degree in ‘Algorithms, Complexity and Networks’ from the University of Montpellier 2, France. His doctoral research is concerned with the study and analysis of algorithms in the field of Complex Networks and Applied Graph Theory. He has extensive practical experience of developing cutting edge algorithms for Data Mining and Artificial Intelligence applications.

Course Outline:

 

  1. Introduction to Analysis of Algorithms
  2. Mathematical Preliminaries
  3. Computational Complexity
  4. Calculating Asymptotic Complexity: Sorting Algorithms
  5. Recurrence Relations
  6. P, NP and NP-Completeness
  7. Greedy Algorithms
  8. Divide and Conquer
  9. Dynamic Programming
  10. Satisfiability Problems
  11. Graph Algorithms and Trees
  12. Linear Programming
  13. Evolutionary Programming and Genetic Algorithms
  14. Approximation Algorithms
  15. Theory of Randomization

 

 

Recommended Books

  1. Introduction to the Analysis of Algorithms, Robert Sadgewick and Philippe Flajolet   Addison-Wesley Publishing, 1996.
  2. Computational Complexity, Oded Goldreich, Cambridge University Press, 2008.
  3. Algorithms and Complexity, Herbert S. Wilf, Internet Edition, 1994.