CS702 - Advancd Algorithms Analysis and Design
Course Page
Q & A
Course Category: Computer Science/Information Technology
Course Level: Graduate
Credit Hours: 3
Pre-requisites: CS301 CS502

Course Synopsis

This is a graduate level course. The major objective of this course is providing comprehensive knowledge of modern computer algorithms and solving scientific and engineering problems efficiently and accurately. The students will be guided, how to analyze complex algorithms comparing efficiencies of these algorithms. Students will not only be taught the design of the existing algorithms but on the other hand it will be focused to teach them designing techniques using rigorous mathematical approaches. The students will be motivated to think about procedures solving real world problems optimally and correctly. Real world problem will be taken as examples to create feelings about the usefulness of this course.

Course Learning Outcomes

Upon successful completion of this course, students should be able to:
  • Argue and prove the correctness of algorithms using rigorous mathematical techniques taught in this course.
  • Analyze average and worst-case running times of given algorithm.
  • Describe the divide-and-conquer technique and arguing when an algorithmic design calls this approach.
  • Derive and solve recurrence relations describing performance of divide-and-conquer algorithms.
  • Describe advanced topics such as dynamic programming and greedy approach and reason to use these approaches for a particular situation.
  • Integrate dynamic programming and recursive approach improving efficiency of an algorithm.
  • Know the importance of graph theory in problem solving.
  • Employing graphs to model science and engineering problems, and to reason about when it is appropriate to use it optimally.
  • Analyze and design algorithms on further advanced topics such as computational geometry, operations research, cryptography, number theoretic, algorithms etc.
  • Analyze several other algorithms of importance such as string matching, NP completeness, approximation algorithms etc.

Course Contents

Introduction, Underlying mathematical theory, Induction and recursion techniques in analyzing algorithms, Asymptotic notations, Search techniques, Divide-and conquer technique, Randomized algorithms, Heuristic algorithms, Brute Force approach, Backtracking, branch-and-bound, Optimization techniques in algorithms designing, Dynamic algorithms, Greedy algorithms, Graph Theory, Searching algorithms, Minimal spanning tree algorithms, Polynomials and FFT, Number theoretic notations, Number theoretic algorithms, RSA cryptosystems, String matching, pattern matching, NP completeness and NP completeness proofs.

Course Related ‌Links

Useful link for course related material, taught by Moses Charikar at Princeton University
Course Related valuable link provided by University of Wisconsin Madison
Course Related valuable link provided by University of Tennessee Department of Electrical Engineering and Computer Science
Useful link for course related material, taught by Kamesh Munagala at Duke University
Course Related Video Lectures provided by MIT, USA at OCW
Course Instructor

Dr. N. A. Zafar Ph.D
Computer Science Kyushu University, Japan

Introduction to Algorithms by T. H. Cormen, C. E. Leiserson and R. L. Rivest

Introduction to Formal Languages and Automata by Peter Linz

Fundamentals of Algorithmics by Gilles Brassard and Paul Bretly

Discrete Mathematics and Its Applications by Kenneth Rosen

Computers & Intractability, Guide to the Theory of NPC by M. R. Garey