Data Structures and File Organization

Unit No.

CONTENT

1

Algorithm Basics ⇗:

• Basic Terminology, types and characteristics, Algorithm Complexity and Time-Space trade-off.

Introduction to Data Structure ⇗:

• Elementary Data Organization, Data Structure operations, Pointers Review; Static and Dynamic Memory Allocation;

Arrays ⇗:

• Definition, Representation and Analysis, Single and Multidimensional Arrays, address calculation, application of arrays, Character, Array as Parameters, Ordered list, Sparse Matrices, and Vector.

2

Stack ⇗:

• Array Representation and Implementation of stack, Operations and Stacks: Push and POP, Array Representation of Stack, Linked Representation of stack, Operations Associated with Stacks, Application of stack, Conversion of Infix to Prefix and Postfix Expressions, Evaluation of postfix expression using stack.

Queue ⇗:

• Array and linked representation and implementation of queues, Operations on Queue; Create, Add, Delete, Full and Empty, Circular queue, Dequeue, and Priority Queue.

3

Linked List (s) ⇗:

• Representation and implementation of Singly linked lists, Header Linked List, Insertion and deletion to from Linked Lists Traversing and Searching of Linked List, Overflow and Underflow, , Insertion and deletion Algorithms, Doubly linked list, Polynomial representation and addition, Generalized linked list, Garbage Collection and Compaction.

4

Searching ⇗:

• Linear and Binary searching

Recursion ⇗:

• definition, types of recursion, call stack, iteration - recursion difference.

Sorting ⇗:

• Sorting: Bubble sort technique, Selection sort technique, Insertion sort technique, Merge sort technique, Quick sort technique.

5

Trees ⇗:

• Basis termonology, types

• Binary Trees
  • Binary Tree, Binary Tree Representation Algebraic Expressions, Complete Binary Tree, Extended Binary Tree, Array and Linked Representation of Binary Trees, Traversing Binary Trees;

• Binary Search Trees
  • Insertion, Traversing, Search, Deletion Operations; Threaded Binary Tree, AVL Tree

• Huffman Tree
  • Huffman Tree and Codes

• Multiway Search Tree
  • B –Trees, B+ Tree;

File Organization ⇗:

• Introduction to File System, Sequential File Organization, Index Sequential Organization, Relative File Organization, Multi-Key File Organization.

Hashing ⇗