BIT 355 WITH EFFECTFROM THE ACADEMIC YEAR 2012-2013
DESIGN AND ANALYSIS OF ALGORITHMS
Instruction 4 Periods per week
Duration of University Examination 3Hours
University Examination 75Marks
Sessional 25 Marks
UNIT-I
Introduction:Space and Time Complexity, Amortized Complexity, Asymptotic Notation, Randomized Algorithms. Elementary DataStructures :Heaps and Heap sort. Sets representation, UNION, FIND Operations,Graphs.
UNIT-II
DivideandConquer :The general method, binary search, finding maximum minimum. Merge sort, quick sort, selection.
Greedy Method:Knapsack problem, Optimal Storage on Tapes, Job sequencing with Deadlines, Optimal Merge Pattern, Minimum Cost Spanning Trees and Single Source shortest Paths.
UNIT-III
Dynamic Programming and TraversalTechniques :Multistage Graphs, All pairs shortest Paths, Optimal Binary Search Trees, 0/1 Knapsack, Reliability Design Traveling Salesman Problem, BFS and Traversal, DFS and Traversal,BiconnectedComponents and Depth First
Search.
UNIT-IV
Backtracking and Branch and Bound:8-Queens Problem, Graph Coloring Hamiltonian cycles, Knapsack Problem. Introduction to LC Search, FIFO Branch and Bound, LC Branch and Bound, 0/I Knapsack Problem, Traveling Salesperson problem, Lower-Bound Theory.
UNIT-V
NP-hard and NP-Completeness :Basic concepts, Non Deterministic Algorithms, Cook’s theorem, NP hard graph problems and scheduling problem.N P-hard code generation problems.DeGisionProblem.Node covering problem.
SuggestedReading:
1.Horowitz E.,SahniS.RajasekaranS: “Fundamentals of ComputerAlgorithms”,2nd edition, Universities Press, 2007.
References :
1.AnanyLevitin,“Introduction to the Design & Analysis of Algorithms“,2003.
2.Aho,Hopcroft,Ullman, “The Design and Analysis of ComputerAlgorithms”,Pearson Education,2000.
3.ParagH.Deve,HimanshuB. Dave“Design acid Analysis of Algorithms“,PearsonEducation,2008.
4.UditAgarwal,“Algorithms DesignandAnalysis“,PhanpatiRai& Co., 2007.