Teaching Scheme

Course Credits Assigned

Course Name (Contact Hours)
Code
Theory Pract. Tut. Theory Pract. Tut. Total
Advance Data 03 – -- -- -- 03
03
2343112 Structure & Analysis

Theory Term Pract / Total

Course Internal Assessment End Exam work Oral
Code Course IAT-I IAT-II IAT-I + Sem Duration
Name IAT-II Exam (in Hrs)
Advance
2343112 Data 20 20 40 60 02
-- -- 100
Structure &
Analysis

Course Objective: Students will able to learn:

Sr. No. Course Objectives
1 To learn mathematical background for analysis of algorithm
2 To learn various advanced data structures.
3 To learn greed approach to solve problems.
4 To learn backtracking algorithm and maximum flow networks.
5 To learn dynamic programming methods.
6 To understand the concept of pattern matching.

Course Outcomes:

On successful completion, of course, learner/student will be able to:

Cognitive Levels of
[Link]. Course Outcomes Attainment as per
Bloom's Taxonomy
1 Understand methods for analysis of algorithms and solve recurrence problems. L1, L2
Choose appropriate advanced data structures for a given problem and calculate its
2 L2, L3, L4
complexity.
3 Analyze the greedy programming technique to solve problems. L2, L3, L4, L5
Evaluate and analyze the backtracking algorithm and understand maximum
4 L2, L3, L4, L5
flow networks.
5 Analyze the dynamic programming technique to solve problems. L2, L3, L4, L5
6 Select a proper pattern matching algorithm for a given problem. L3, L4, L5

Detailed Syllabus:

Sr. Name of Detailed Content Hours CO

No. Module Mappings
0 Prerequisite Overview of Data Structures: Revision of basic data structures (arrays, 01
stacks, queues, linked lists, trees).
I Introduction Fundamentals of the analysis of algorithms: Time and Space 03 CO1
to Analysis of complexity, Asymptotic notation, Recurrence Relations: Methods
Algorithms to solve recurrence relations in algorithms (Substitution, Recursion
tree, Master theorem).
Self-learning Topics: Solve problems on analysis of algorithms.
II Advanced Introduction. AVL trees, B tree, B tree operations, B+ tree, Red- 08 CO2
Data Black Trees, tries data structures, time complexity analysis of all
Structures problems. Graphs, Representation, Graph Traversals: Breadth First
Search, Depth First Search.
Self-learning Topics: Solve problems on AVL trees, B tree, B+ tree etc.
III Greedy Introduction and properties of greedy algorithms, Fractional 06 CO3
algorithms Knapsack problem, Minimum Spanning Trees (Prim’s and
and Kruskal’s algorithms), Job sequencing with deadlines, Optimal
Applications storage on tapes, Analysis of All problems.
Self-learning Topics: Solve problems on Spanning Trees, Knapsack etc.
IV Backtracking Backtracking Techniques: Introduction, N-Queens problem, sum 07 CO4
and of subsets problem, graph coloring, Hamiltonian cycles.
Maximum Introduction to flow networks, Augmenting Paths Residual
flow Network, Ford Fulkerson method, Applications of Flow Networks in
Networks real-world problems.
Self-learning Topics: Solve problems N-Queens, Hamiltonian cycles,
Augmenting Paths Residual Network etc.
V Dynamic Introduction Dynamic algorithms, Greedy vs. Dynamic algorithms, 08 CO5
Algorithms Single source shortest path- Dijkstra's Algorithm, Bellman Ford
Algorithm, All pair shortest path- Floyd Warshall Algorithm, 0/1
knapsack problem, Travelling salesman problem, Analysis of All
problems.
Self-learning Topics: Solve problems on shortest path- Dijkstra's
Algorithm etc.
VI String Introduction. Naïve string matching algorithm, Rabin-Karp 06 CO6
Matching algorithm, Knuth-Morris-Pratt(KMP) algorithm, Longest
Algorithms common subsequence(LCS), Analysis of All problems,
Applications: Text searching, DNA sequencing, and data
compression.
Self-learning Topics: Solve problems on DNA sequencing, and data
compression.
Note: No questions will be asked in the end-semester exam from self-study topics. However, students are encouraged to
explore these topics for a better understanding of the subject.

Text Books and References:

Sr. No Title Authors Publisher Edition Year

1 Introduction to Cormen, PHI 3rd Edition 2011
Algorithms Leiserson, Rivest,
Stein
2 Algorithm Design Jon Kleinberg, Pearson 1st Edition 2006
Éva Tardos

3 Data Structures and Mark Allen Pearson 4th Edition 2013

Algorithm Analysis in Weiss
C++
4 Introduction to the Design Anany Levitin Pearson 3rd Edition 2011
and Analysis of
Algorithms

5 Algorithms Robert Addison- 4th Edition 2011

Sedgewick, Wesley
Kevin Wayne
 Online Resources:

S. Website Name URL Modules

No. Covered

1 NPTEL [Link] M1
2 NPTEL [Link] M2
3 NPTEL [Link] M3
4 Coursera [Link] M1-M3
5 MIT [Link] M1-M6
OpenCourseWare science/6-006-introduction-to-algorithms-fall-2011/

Assessment:
Internal Assessment Test (IAT) for 20 marks each:
 IA will consist of Two Compulsory Internal Assessment Tests. Approximately 40% to 50% of the syllabus
content must be covered in the IAT-I and the remaining 40% to 50% of the syllabus content must be covered in
the IAT-II.

End Semester Theory Examination:

 Question paper format

 Question Paper will comprise a total of six questions each carrying 15 marks Q.1 will be compulsory and
should cover the maximum contents of the syllabus

 Remaining questions will be mixed in nature (part (a) and part (b) of each question must be from different
modules. For example, if Q.2 has part (a) from Module 3 then part (b) must be from any other Module
randomly selected from all the modules)

 A total of four questions need to be answered.