15CS33 Data Structures and Applications syllabus for IS

Introduction:
Data Structures, Classifications (Primitive & Non Primitive), Data structureOperations, Review of Arrays, Structures, Self-Referential Structures, and Unions.Pointers and Dynamic Memory Allocation Functions. Representation of Linear Arrays inMemory, Dynamically allocated arrays.
Array Operations:
Traversing, inserting, deleting,searching, and sorting. Multidimensional Arrays, Polynomials and Sparse Matrices.
Strings:
Basic Terminology, Storing, Operations and Pattern Matching algorithms.Programming Examples.Text 1: Ch 1: 1.2, Ch 2: 2.2 -2.7
Text 2: Ch 1: 1.1 -1.4, Ch 3: 3.1-3.3,3.5,3.7, Ch 4: 4.1-4.9,4.14
Ref 3: Ch 1: 1.4

Stacks and QueuesStacks:
Definition, Stack Operations, Array Representation of Stacks, Stacks usingDynamic Arrays, Stack Applications: Polish notation, Infix to postfix conversion,evaluation of postfix expression,
Recursion -
Factorial, GCD, Fibonacci Sequence, Towerof Hanoi, Ackerman\'s function.
Queues:
Definition, Array Representation, QueueOperations, Circular Queues, Circular queues using Dynamic arrays, Dequeues, PriorityQueues, A Mazing Problem. Multiple Stacks and Queues. Programming Examples.Text 1: Ch 3: 3.1 -3.7
Text 2: Ch 6: 6.1 -6.3, 6.5, 6.7-6.10, 6.12, 6.13

Linked Lists:
Definition, Representation of linked lists in Memory, Memory allocation;Garbage Collection. Linked list operations: Traversing, Searching, Insertion, and Deletion.Doubly Linked lists, Circular linked lists, and header linked lists. Linked Stacks andQueues. Applications of Linked lists – Polynomials, Sparse matrix representation.Programming Examples
Text 1: Ch 4: 4.1 -4.8 except 4.6
Text 2: Ch 5: 5.1 – 5.10

Trees:
Terminology, Binary Trees, Properties of Binary trees, Array and linkedRepresentation of Binary Trees, Binary Tree Traversals - Inorder, postorder, preorder;Additional Binary tree operations. Threaded binary trees, Binary Search Trees – Definition,Insertion, Deletion, Traversal, Searching, Application of Trees-Evaluation of Expression,Programming Examples
Text 1: Ch 5: 5.1 –5.5, 5.7
Text 2: Ch 7: 7.1 – 7.9

Graphs:
Definitions, Terminologies, Matrix and Adjacency List Representation OfGraphs, Elementary Graph operations,
Traversal methods:
Breadth First Search and DepthFirst Search.
Sorting and Searching:
Insertion Sort, Radix sort, Address Calculation Sort.
Hashing:
Hash Table organizations, Hashing Functions, Static and Dynamic Hashing.Files and Their Organization:
Data Hierarchy, File Attributes, Text Files and BinaryFiles, Basic File Operations, File Organizations and Indexing
Text 1: Ch 6: 6.1 –6.2, Ch 7:7.2, Ch 8:8.1-8.3
Text 2: Ch 8: 8.1 – 8.7, Ch 9:9.1-9.3,9.7,9.9
Reference 2: Ch 16: 16.1 - 16.7