Course Code: Course Title: Introduction to Algorithms L P U
BCA 211
BCA II year (III Semester) 3 0 3
Course Objectives:
The aim of this course is to learn how to develop efficient algorithms for simple computational
tasks and reasoning about the correctness of them. Through the complexity measures, different
range of behaviors of algorithms and the notion of tractable and intractable problems will be
understood. The course attempts to cover topics like Worst and average case analysis.
Recurrences and asymptotic notations. Efficient algorithms for sorting, searching, and selection.
Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms.
Algorithms for fundamental graph problems: minimum-cost spanning tree, connected
components and shortest paths.
Course Outcomes:
After successful completion of the course student will be able to
1. Be able to check the correctness of algorithms using inductive proofs and loop
invariants.
2. Be able to compare functions using asymptotic analysis and describe the relative merits
of worst-, average-, and best-case analysis.
3. Be able to solve recurrences using the master, the iteration, and the substitution method.
4. Become familiar with a variety of sorting algorithms and their performance
characteristics (eg, running time, stability, space usage) and be able to choose the best
one under a variety of requirements.
5. Be able to understand and identify the performance characteristics of fundamental
algorithms and data structures and be able to trace their operations for problems such as
sorting, searching, selection, operations on numbers, polynomials and matrices, and
graphs.
6. Explain the major graph algorithms and their analyses. Employ graphs to model
engineering problems, when appropriate. Synthesize new graph algorithms and
algorithms that employ graph computations as key components, and analyze them.
7. Be able to use the design techniques introduced i.e. dynamic programming, greedy
algorithm etc. to design algorithms for more complex problems and analyze their
performance.
8. Become familiar with the major graph algorithms and their analyses. Employ graphs to
model engineering problems, when appropriate.
UNIT - I
Introduction to Algorithms and Algorithm Definition, Algorithm Specification and
Performance Analysis, Space Complexity and Time Complexity, Asymptotic Notation (Big
O, Omega, Theta), Introduction to Trees and Tree Terminology, Recursive Algorithms and
Master's Theorem, Binary Trees and Their Properties, Introduction to Graphs and Graph
Terminology.
UNIT - II
Binary Tree Techniques and Traversal Methods, Divide and Conquer - General Method and
Applications, Binary Search Algorithm, Introduction to Sorting Algorithms, Basic Sorting
Algorithms, Selection Sort and Complexity Analysis, Merge Sort and its Analysis, Quick Sort
and its Analysis, Applications of Graphs.
UNIT - III
Introduction to Greedy Method, Benchmark Problems, Job Sequencing with Deadlines,
Knapsack Problem and Greedy Solution, Minimum Cost Spanning Trees and Prim's
Algorithm, Kruskal's Algorithm for Minimum Spanning Trees, Single Source Shortest Path
Problem, Dijkstra's Algorithm for Shortest Paths.
UNIT - IV
Dynamic Programming - General Method and Applications, Matrix Chain Multiplication
Problem, Longest Common Subsequence Problem, All Pairs Shortest Path Problem -
Bellman-Ford Algorithm, Floyd-Warshall Algorithm for All Pairs Shortest Paths, Traveling
Salesperson Problem and Dynamic Programming, Introduction to Backtracking, N-Queen
Problem.
UNIT - V
Introduction to Branch and Bound Method, Solving Traveling Salesperson Problem using
Branch and Bound, Lower Bound and Upper Bound in Branch and Bound, FIFO Branch and
Bound Solution, Introduction to NP-Hard and NP-Complete Problems, Non-deterministic
Algorithms, NP-Hard and NP-Complete Classes, Advanced Algorithms Metaheuristic,
MCDM Techniques.
TEXT BOOKS:
1. Fundamentals of Computer Algorithms, Ellis Horowitz, Satraj Sahni and Rajasekharam,
Galgotia publications Pvt. Ltd. 2nd Edition, 2013.
R1. Introduction to Algorithms, Thomas H.Cormen, Charles E.Leiserson, RonaldL.Rivestand
Clifford Stein, PHI.
R2. Fundamental of Algorithms by Gills Brassard, PaulBratley, PHI.
REFERENCE BOOKS:
