Syllabus of Andhra University BTech Information Technology - IT 2.1.3 - Data Structures

Second year - First Semester

Instruction: 3 Periods & 1 Tut /week
Univ. Exam : 3 Hours

Sessional Marks: 30
Univ-Exam-Marks:70

Introduction to Data Structures: Information and Meaning – Representation of Multi- Dimensional Arrays _ Review of C Programming.

The Stack: Primitive operations – As an Abstract Data Type – Implementing the Stack operations in C.

Infix, Postfix and Prefix: Definitions, Evaluation and Conversions using C.

Recursion: Recursive Definition and Processes, Recursion in C and Recursive Implementation of Applications. Simulation of Recursion – Efficiency of Recursion.

Queues and Lists: The Queue as Abstract Data Type – Sequential Representation _Types of Queues – Operations – Implementation in C.

Linked List: Operations – Implementation of Stacks, Queues and priority Queues in C.

Circular Lists: Insertion, Deletion and Concatenation Operations _ Stacks and Queues as Circular Lists _ Doubly Linked Lists _Applications.

Trees: Binary Trees Operations and Applications.

Binary Tree Representation: Node Representation – Implicit array Representation – Choice of Representation – Binary Tree Traversal – Threaded Binary Trees and their Traversal – Trees and their Applications

Sorting: General Background: Efficiency – The big 0 Notation – Efficiency of Sorting. Bubble Sort and Quick Sort and their Efficiency – Selection Sorting – Binary Tree Sort – Heap Sort – Insertion Sorts – Shell Sort – Address calculation Sort – Merge and Radix Sorts.

Searching: Basic Searching Techniques: Dictionary as an Abstract Data Type – Algorithmic Notation – Sequential Searching and its Efficiency – Binary Search – Interpolation Search.

Tree Searching: Insertion into a Binary Search Tree – Deleting from a Binary Search Tree – Efficiency of Binary Search Tree operation

Graphs and Their Application: Graphs: Application of Graphs – Representation of Graphs in C – Transitive closure – Warshall’s Algorithm – Shortest Path Algorithm.

Linked Representation of Graphs: Dijikstra’s Algorithm – Organizing the set of Graph Nodes – Application to Scheduling and its implication.

Graph Traversal and Spanning Forests – Undirected Graph and their Traversals, Applications and Efficiency – Minimal Spanning Trees –Prim’s and Kruskal’s Algorithms.

Textbooks:

1. Data Structures Using C and C++ Yddish Langsam, Moshe J. Augenstein and Aaron M. Tanenbaum, Prentice Hall Of India (2nd Edition) (Chapters 1 to 8)

2. Data Structures, Algorithms and Applications with C++, Sahani Mc-Graw Hill.

Note: All Implementation are Using C Language only.