National University of Sciences and Technology
Home | Back
SE -830 Adv Algorithm Analysis
Campus MCS
Programs PG
Session Summer Semester 2016
Course Title Adv Algorithm Analysis
Course Code SE -830
Credit Hours 3+0
Pre-Requisutes CS-250 Data Structure & Algo
Course Objectives The objective of this course is to provide the techniques and theory for designing and analyzing efficient computer algorithms. The design techniques include divide-and-conquer, transform-and-conquer, dynamic programming, greedy techniques, and so on. Algorithms designed by using the techniques for manipulating lists, trees, and graphs, and for solving other problems are described and analyzed. The mathematical methods for analyzing non-recursive and recursive algorithms are discussed. Also, the problems of NP-completeness are addressed.
Detail Content


Preliminaries: Mathematical Notation, Proof Techniques, Basic Combinatorics, Elementary Probability


Elementary Algorithmics: The efficiency of algorithms, Average and worst-case analysis


Asymptotic Notation: A notation for “the order of,” Conditional asymptotic notation, Asymptotic notation with several parameters, Operations on asymptotic notation


Data Structures: Arrays, Stacks, Queues, Records and pointers, Lists, Graphs, Trees, Associative Tables, Heaps, Binomial Heaps, Disjoint set structures


Greedy Algorithms:  General Characteristics of greedy algorithms, Minimum Spanning Trees (Kruskal’s and Prim’s), Shortest paths, The Kanpsack problem, Scheduling


Dynamic Programming: The principle of Optimality,  The Knapsack Problem, Chained matrix multiplication, Approaches using recursion, Memory functions


Exploring Graphs: Traversing trees, Depth-first search (Undirected graphs, Directed graphs), Breadth-first search, Backtracking, Branch-and-bound, The minimax principle


Probabilistic Algorithms: Pseudorandom generation, Numerical probabilistic algorithms, Monte Carlo algorithms, Las Vegas algorithms


Parallel Algorithms: Basic Techniques, Parallel evaluation of expressions, Parallel sorting networks,


Computational Complexity: Information-theoretic arguments, Linear reductions, NP-completeness


Heuristic and Approximate Algorithms:  Heuristic Algorithms, Approximate algorithms, NP-hard approximation problems, Approximation schemes

Text/Ref Books


1. Fundamentals of Algorithms, Gilles Brassard & Paul Bratley,  Prentice Hall, 1996


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

Time Schedule As per Student Feedback/ Summer Semester 2015
Faculty/Resource Person Respective TVF