AKTU Basics of Data Structures and Algorithms (BOE306 / BOE406) Syllabus PDF – B.Tech Open Elective

Course Outcome ( CO) Bloom’s Level (KL) At the end of course , the student will be able to understand CO 1 Describe how arrays, linked lists, stacks, queues, trees, and graphs are represented in memory, used by K K 1, 2 the algorithms and their common applications.

CO 2 Discuss the computational efficiency of the sorting and searching algorithms. K 2 CO 3 Implementation of Trees and Graphs and perform various operations on these data structure. K 3 CO 4 Understanding the concept of recursion, application of recursion and its implementation and removal of K 4 recursion.

CO 5 Identify the alternative implementations of data structures with respect to its performance to solve a real K K 5, 6 world problem.

Course Content

Unit Topic Lecture I Introduction: Basic Terminology, Elementary Data Organization, Built in Data Types in C, 08 Efficiency of an Algorithm, Asymptotic notations, Abstract Data Types (ADT) Arrays: Definition, Single and Multidimensional Arrays, Representation of Arrays: Row Major Order, and Column Major Order.

Linked lists: Array Implementation and Pointer Implementation of Singly Linked Lists, Doubly Linked List, Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal, Polynomial Representation and Addition Subtraction & Multiplications of Single variable & Two variables Polynomial.

II Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Array and Linked 08 Implementation of Stack in C, Application of stack: Prefix and Postfix Expressions, Evaluation of postfix expression, Iteration and Recursion- Principles of recursion, Tail recursion, Fibonacci numbers, and Hanoi towers, Tradeoffs between iteration and recursion.

Queues: Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, Array and linked implementation of queues in C, Dequeue and Priority Queue.

III Searching: Concept of Searching, Sequential search, Index Sequential Search, Binary Search. 08 Concept of Hashing & Collision resolution Techniques used in Hashing.

Sorting: Insertion Sort, Selection, Bubble Sort, Quick Sort, Merge Sort, Heap Sort and Radix Sort.

IV Trees: Basic terminology used with Tree, Binary Trees, Binary Tree Representation: Binary Search 08 Tree, Strictly Binary Tree, Complete Binary Tree, Extended Binary Trees, Tree Traversal algorithms: Inorder, Preorder and Postorder, Constructing Binary Tree from given Tree Traversal, Insertion , Deletion, Searching & Modification of data in Binary Search tree.

V Graphs: Terminology used with Graph, Data Structure for Graph Representations: Adjacency 08 Matrices, Adjacency List, Graph Traversal: Depth First Search and Breadth First Search, Minimum Spanning Trees, Prims and Kruskal algorithm.

Text Books

1. Aaron M. Tenenbaum, Yedidyah Langsam and Moshe J. Augenstein, “Data Structures Using C and C++”, PHI Learning Private Limited, Delhi India
2. Gilberg ,Forouzan, Data Structures: A Pseudocode Approach with C 3rd edition , Cengage Learning publication
3. Horowitz and Sahani, “Fundamentals of Data Structures”, Galgotia Publications Pvt Ltd Delhi India.
4. Lipschutz, “Data Structures” Schaum’s Outline Series, Tata McGraw-hill Education (India) Pvt. Ltd.
5. Thareja, “Data Structure Using C” Oxford Higher Education.
6. AK Sharma, “Data Structure Using C”, Pearson Education India.
7. Rajesh K. Shukla, “Data Structure Using C and C++” Wiley Dreamtech Publication.
8. Michael T. Goodrich, Roberto Tamassia, David M. Mount “Data Structures and Algorithms in C++”, Wiley India.
9. P. S. Deshpandey, “C and Data structure”, Wiley Dreamtech Publication.
10. R. Kruse etal, “Data Structures and Program Design in C”, Pearson Education.
11. Berztiss, AT: Data structures, Theory and Practice, Academic Press.
12. Jean Paul Trembley and Paul G. Sorenson, “An Introduction to Data Structures with applications”, McGraw Hill.
13. Adam Drozdek “Data Structures and Algorithm in Java”, Cengage Learning