Data Structures and Algorithms - Laboratory

C Programming and Data Structures

Unit I: C Programming Fundamentals:

• C Programming Fundamentals
• Keywords, Variables and Constants
• Header Files
• Data Types
• Expressions using Operators
• Input and Output Operations
• Decision Making and Conditional Statements
• Functions
• Recursive Functions
• Arrays
• Simple C Programs
• Two Marks Questions with Answers

Unit II: C Programming – Advanced Features:

• C Programming - Advanced Features
• Structures
• Union
• Difference between Data Type, Structures and Unions
• Enumerated Data Types
• Pointers
• Strings and Pointers
• Arrays and Functions
• File Handling
• Preprocessor Directives
• Two Marks Questions with Answers

Unit III: a. Linear Data Structures - List:

• Linear Data Structures - List
• Introduction to Data Structure
• Abstract Data Types (ADTs)
• List ADT
• Array Based Implementation
• Linked List
• Difference between Array and Linked Listed
• Doubly Linked List
• Circular Linked List
• Applications of Linked Lists
• Two Marks Questions with Answers

Unit III: b. Linear Data Structures Stacks and Queues:

• Linear Data Structures Stacks and Queues
• Concept of Stack
• Stack ADT
• Implementation of Stack
• Applications of Stack
• Expression
• Infix to Postfix Conversion
• Evaluation of Postfix Expressions
• Concept of Queue
• Queue ADT
• Queue Implementation
• Priority Queues
• Applications of Queue
• Two Marks Questions with Answers

Unit IV: a. Non-Linear Data Structures - Trees:

• Non-Linear Data Structures - Trees
• Trees
• Binary Trees
• Representation of Binary Tree
• Tree Traversal
• Expression Trees
• Binary Search Tree
• C Programming Examples [Trees]
• Two Marks Questions with Answers

Unit IV: b. Hashing:

• Hashing
• Basic Concept of Hashing
• Hash Functions
• Properties of Good Hash Function
• Collision Handling
• Applications of Hashing
• Two Marks Questions with Answers

Unit V: Sorting and Searching Techniques:

• Sorting and Searching Techniques
• Sorting
• Insertion Sort
• Quick Sort
• Heap Sort
• Merge Sort
• Searching
• Two Marks Questions with Answers

Data Structure

Unit I: Lists:

• Data Structure
• Abstract Data Types (ADT)
• List ADT
• Array Based Implementation
• Concept of Linked List
• Linked List Implementation
• Difference Between Array and Linked Listed
• Circularly Linked List
• Doubly Linked List
• Applications of Lists
• Polynomial ADT
• Multilists
• Two marks Questions with Answers

Unit II (a): Stacks:

• Concept of Stacks
• Stack ADT
• Stack Operations
• Implementation of Stack using Linked List
• Applications of Stack
• Expression
• Infix to Postfix Conversion
• Evaluation of Arithmetic Expression
• Two marks Questions with Answers

Unit II (b): Queue:

• Concept of Queue
• Queue ADT
• Queue Operations
• Implementation of Queue using Linked List
• Circular Queue
• Priority Queue
• Dequeue
• Applications of Queue
• Two marks Questions with Answers

Unit III: Trees:

• Trees ADT
• Basic Terminologies in Trees
• Binary Tree ADT
• Types of Binary Tree
• Representation of Tree
• Tree Traversal
• Expression Trees
• Applications of Trees
• Binary Search Tree ADT
• Threaded Binary Trees
• Constructing Binary Search Tree from Traversals
• C Programming Examples on Binary Trees
• AVL Trees
• Binary Heap
• Priority Queue Heaps
• Two marks Questions with Answers

Unit IV : Multiway Search Trees and Graphs:

• B-Tree
• B+ Tree
• Graph Definition
• Basic Terminologies in Graph
• Representation of Graph
• Types of Graph
• Graph Operations
• Graph Traversal Methods
• Topological Sort
• Bi-Connectivity
• Cut Vertex
• Euler Circuits
• Applications of Graphs
• Finding Shortest Path
• Minimum Spanning Tree
• Two marks Questions with Answers

Unit V (a): Searching and Sorting:

• Searching
• Sorting
• Bubble Sort
• Selection Sort
• Insertion Sort
• Shell Sort
• Radix Sort
• Merge Sort
• Two marks Questions with Answers

Unit V (b): Hashing Techniques:

• Hashing
• Applications of Heap
• Hash Functions
• Properties of Good Hash Function
• Collision Resolution Techniques
• Applications of Hashing
• Two marks Questions with Answers

Data Structures using CPlusPlus

Chapter 1: Data Abstraction and Overloading:

• Difference between C and C++
• C++ Programming Structure
• Control Structures of C++
• Reference Variables
• Class Scope and Accessing Class Members
• Initialization, Constructors, Destructors
• Destructors
• Member Functions and Classes
• Friend Function
• Dynamic Memory Allocation
• Static Class Members
• Container Classes and Integrators
• Proxy Classes
• Function Overloading
• Operator Overloading
• Data Abstraction and Overloading: Two Marks Important Questions and Answers
• Data Abstraction and Overloading: Important Questions

Chapter 2: Inheritance and Polymorphism:

• Basic Concept of Inheritance
• Base Classes and Derived Classes
• Public, Protected and Private Inheritance
• Comparison between Public, Protected and Private Inheritance
• Types of Inheritance
• Casting Class Pointers and Member Functions
• Constructors and Destructors in Derived Classes
• Composition Vs Inheritance
• this Pointer
• Polymorphism
• Compile Time Versus Runtime Polymorphism
• Virtual Functions
• Overriding
• Abstract Base Classes and Concrete Classes
• Pure Virtual Function
• Virtual Destructors
• Binding
• Inheritance and Polymorphism: Two Marks Important Questions and Answers
• Inheritance and Polymorphism: Important Questions

Chapter 3: Analysis of Algorithms and Arrays:

• Introduction, Definition, Example and Types to Data Structures
• Introduction to Analysis of Algorithms
• Asymptotic Notations
• Best, Worst and Average Case Analysis
• Arrays and its Representations
• Analysis of Algorithms and Arrays: Two Marks Important Questions and Answers
• Analysis of Algorithms and Arrays: Important Questions

Chapter 4: Stacks and Queues:

• Introduction to Stacks
• Representation of Stack using Arrays
• Applications of Stack
• Stacks: Arithmetic Expressions
• Stacks: Evaluation of Expression
• Introduction to Queues
• Representation Queues using Arrays
• Circular Queue
• Applications of Queues in Data Structures
• Stacks and Queues: Two Marks Important Questions and Answers
• Stacks and Queues: Important Questions

Chapter 5: Linked Lists:

• Linked Lists
• C++ Representation of Linked List
• Implementation of linked list
• Other Linked List Operations
• Difference between Array and Linked List
• Circular Linked List
• Doubly Linked List
• Linked List based Implementation of Stacks
• Linked List based Implementation of Queues
• Linked Lists Polynomial Manipulation
• Linked Lists: Two Marks Important Questions and Answers
• Linked Lists: Important Questions

Chapter 6: Trees:

• Introduction to Trees
• Binary Trees
• Binary Tree Representation
• Traversals
• Operations of Binary Trees
• Binary Search Tree
• Threaded Binary Trees
• Application of Trees: Set Representation and Union, Find Operations
• Trees (Data Structures): Two Marks Important Questions and Answers
• Trees (Data Structures): Important Questions

Chapter 7: Graphs:

• Introduction to Graphs
• Representation of Graphs
• Representation of Graphs: Adjacency Matrix
• Applications of Graphs
• Graphs: Connected Components
• Graphs (Data Structure): Two Marks Important Questions and Answers
• Graphs (Data Structure): Important Questions

Chapter 8: Standard Template Library:

• Introduction to STL (Standard Template Library)
• Applications of Container Class: Vectors, Stack, List, Map
• Standard Template Library (C++ Program): Two Marks Important Questions and Answers
• Standard Template Library (C++ Program): Important Questions

Chapter 9: Searching, Sorting and Complexity Analysis:

• Concept of Sorting
• List of Sorting Algorithms
• Sorting Algorithm: Insertion Sort
• Sorting Algorithm: Merge Sort
• Sorting Algorithm: Quick Sort
• Sorting Algorithm: Heap Sort
• Searching Techniques
• Linear Search
• Binary Search
• Searching, Sorting and Complexity Analysis: Two Marks Important Questions and Answers
• Searching, Sorting and Complexity Analysis: Important Questions