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

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