National University of Sciences and Technology
• Nust Home
• • ALUMNI
• • Contact Us
 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
 1 Preliminaries: Mathematical Notation, Proof Techniques, Basic Combinatorics, Elementary Probability 2 Elementary Algorithmics: The efficiency of algorithms, Average and worst-case analysis 3 Asymptotic Notation: A notation for “the order of,” Conditional asymptotic notation, Asymptotic notation with several parameters, Operations on asymptotic notation 4 Data Structures: Arrays, Stacks, Queues, Records and pointers, Lists, Graphs, Trees, Associative Tables, Heaps, Binomial Heaps, Disjoint set structures 5 Greedy Algorithms:  General Characteristics of greedy algorithms, Minimum Spanning Trees (Kruskal’s and Prim’s), Shortest paths, The Kanpsack problem, Scheduling 6 Dynamic Programming: The principle of Optimality,  The Knapsack Problem, Chained matrix multiplication, Approaches using recursion, Memory functions 7 Exploring Graphs: Traversing trees, Depth-first search (Undirected graphs, Directed graphs), Breadth-first search, Backtracking, Branch-and-bound, The minimax principle 8 Probabilistic Algorithms: Pseudorandom generation, Numerical probabilistic algorithms, Monte Carlo algorithms, Las Vegas algorithms 9 Parallel Algorithms: Basic Techniques, Parallel evaluation of expressions, Parallel sorting networks, 10 Computational Complexity: Information-theoretic arguments, Linear reductions, NP-completeness 11 Heuristic and Approximate Algorithms:  Heuristic Algorithms, Approximate algorithms, NP-hard approximation problems, Approximation schemes
Text/Ref Books
 TextBook: 1. Fundamentals of Algorithms, Gilles Brassard & Paul Bratley,  Prentice Hall, 1996 Reference: 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