CS6301 PROGRAMMING AND DATA STRUCTURES II Syllabus Semester III IT BTECH Anna University-Regulation-2013

CS6301                                PROGRAMMING AND DATA STRUCTURES II                          L  T  P C
3 0  0 3
OBJECTIVES:
The student should be made to:

• Be familiar with the C++ concepts of abstraction, encapsulation, constructor, polymorphism, overloading and Inheritance.
• Learn advanced nonlinear data structures.
• Be exposed to graph algorithms
• Learn to apply Tree and Graph structures

UNIT I            OBJECT ORIENTED PROGRAMMING FUNDAMENTALS                                          9
C++ Programming features - Data Abstraction - Encapsulation - class - object - constructors - static members – constant members – member functions – pointers – references - Role of this pointer – Storage classes – function as arguments.
UNIT II         OBJECT ORIENTED PROGRAMMING CONCEPTS                                                       9
String Handling – Copy Constructor - Polymorphism – compile time and run time polymorphisms – function overloading – operators overloading – dynamic memory allocation - Nested classes - Inheritance – virtual functions.

UNIT III        C++ PROGRAMMING ADVANCED FEATURES                                                             9
Abstract class – Exception handling - Standard libraries - Generic Programming - templates – class template - function template – STL – containers – iterators – function adaptors – allocators - Parameterizing the class -  File handling concepts.

UNIT IV       ADVANCED NON-LINEAR DATA STRUCTURES                                                           9
AVL trees – B-Trees – Red-Black trees – Splay trees - Binomial Heaps – Fibonacci Heaps – Disjoint
Sets – Amortized Analysis – accounting method – potential method – aggregate analysis.

UNIT V        GRAPHS                                                                                                                             9
Representation of Graphs – Breadth-first search – Depth-first search – Topological sort – Minimum Spanning Trees – Kruskal and Prim algorithm – Shortest path algorithm – Dijkstra?s algorithm – Bellman-Ford algorithm – Floyd-Warshall algorithm.


OUTCOMES:
At the end of the course, the student should be able to:

• Design problem solutions using Object Oriented Techniques.

TOTAL: 45 PERIODS

• Apply the concepts of data abstraction, encapsulation and inheritance for problem solutions.
• Use the control structures of C++ appropriately.
• Critically analyse the various algorithms.
• Apply the different data structures to problem solutions.

TEXT BOOKS:

1. Bjarne Stroustrup, “The C++ Programming Language”, 3rd Edition, Pearson Education, 2007.
2. Mark Allen Weiss,  “Data  Structures  and  Algorithm  Analysis  in  C++”,  2nd   Edition,  Pearson

Education, 2005.

REFERENCES:

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, "Introduction to

Algorithms", Second Edition, Mc Graw Hill, 2002.

2. Michael T Goodrich, Roberto Tamassia, David Mount, “Data Structures and Algorithms in C++”,

7th Edition, Wiley Publishers, 2004.
#################################################################################################