Data structures and Algorithms Contents

• 1. Introduction
  • 1.1. Problem to Solution
  • 1.2. Abstract Data Types
    • 1.2.1. An ADT for rational numbers
    • 1.2.2. Advantages of ADTs
      • 1.2.2.1. Encapsulation
      • 1.2.2.2. Localization of Change and Isolation from Implementation
      • 1.2.2.3. Flexibility
    • 1.2.3. Complexity Considerations for an ADT
  • 1.3. What is an Algorithm?
  • 1.4. Complexity of an Algorithm
    • 1.4.1. An Alternative Definition
  • 1.5. Examples of Asymptotic Complexity Computation
  • 1.6. Simplicity
  • 1.7. More on Asymptotic Notations
    • 1.7.1. Little o Notation
    • 1.7.2. Little \(\omega\) Notation
  • 1.8. Problems on Complexity
  • 1.9. Mathematical Induction
  • 1.10. Some Basic Mathematics
• 2. Recursion
  • 2.1. Types of Recursion
    • 2.1.1. Single and Multiple Recursions
    • 2.1.2. Indirect Recursion
    • 2.1.3. Anonymous Recursion
    • 2.1.4. Structured and Generative Recursion
  • 2.2. Tail Recursion
  • 2.3. Recursive Algorithms
    • 2.3.1. Factorial Computation
    • 2.3.2. Fibonacci Series
      • 2.3.2.1. Tail Recursive Version
    • 2.3.3. Ackermann’s Function
      • 2.3.3.1. Naive Implementation
  • 2.4. Binary Search
  • 2.5. A Simple Problem of Average Calculation
    • 2.5.1. Complexity Analysis of Binary Search
  • 2.6. Towers of Hanoi(Brahma)
    • 2.6.1. Time and Space Complexity
• 3. Linear Structures
  • 3.1. Singly Linked List
    • 3.1.1. Insertion at the Beginning
    • 3.1.2. Insertion at Some Position
    • 3.1.3. Insertion at the End or Append
    • 3.1.4. Searching an Element
    • 3.1.5. Deleting an Element
    • 3.1.6. Counting the Size
  • 3.2. Singly Linked List vs Array
  • 3.3. Questions on Singly Linked Lists
  • 3.4. Doubly Linked Lists
• 4. Linked List Solutions
• 5. Stacks
  • 5.1. Array Based Implementation
    • 5.1.1. Stack.c
    • 5.1.2. Stack.c
  • 5.2. Linked List Based Implementation
    • 5.2.1. stack_ll.h
    • 5.2.2. stack_ll.c
  • 5.3. Usage of Stack
  • 5.4. Problems on Stacks
• 6. Queues
  • 6.1. Array Based Implementation
    • 6.1.1. queue.h
    • 6.1.2. queue.c
  • 6.2. Linked List Based Implementation
    • 6.2.1. queue_ll.h
    • 6.2.2. queue_ll.c
  • 6.3. Problems on Queues
• 7. Doubly Linked Lists and Circular Lists
  • 7.1. Doubly Linked Lists
  • 7.2. dll.c
  • 7.3. Circular Lists
    • 7.3.1. Advantages and Applications of Circular Linked Lists

Indices and tables

• Index