Data Structures and Algorithms

• Data: Represents an organization's resources in forms like numbers, text, bits, and bytes
• Data Structure: Method for collecting, organizing, and accessing data efficiently in a computer's memory
• Abstract Data Type: Implementation-independent data type
• Algorithm: A finite set of instructions to solve a predefined task
• Time Complexity: Measures the time a program needs for completion
• Space Complexity: Amount of memory space an algorithm requires during execution; crucial for multi-user systems
• Instruction Space: Space needed to store the executable version of a program
• Data Space: Space required to store constant and variable values
• Environment Space: Space needed for environment information to resume suspended functions
• Primitive Data Structures: Basic, non-decomposable data types: integers, floats, pointers, Booleans, and characters
• Non-Primitive Data Structures: Complex structures derived from primitive data structures: strings, arrays, lists, records, and files
• Linear Data Structure: Elements connected and accessed sequentially: Stacks, Queues, and Linked Lists
• Non-Linear Data Structure: Data items not arranged sequentially: Trees and Graphs
• Class: Specifies an object's form, combining data and methods for data manipulation
• List: Collection of items in a specific order
• Linked List: Data structure using pointers to connect individual list elements (nodes)

Types of Linked Lists:

• Singly Linked List: Unidirectional list, allowing traversal in one direction only

• Doubly Linked List: Bi-directional list, allowing traversal in both directions

• Circular Linked List: Unidirectional list where the last node points to the head node

• Circular Doubly Linked List: Combines features of doubly linked lists and circular linked lists

• Head: Pointer to the first node of a linked list

• Null: Indicates the absence of a next node

• Pointers: Store addresses of variables

  • * to declare a pointer variable
  • & to declare an address

• Stack : Linear data structure following LIFO (Last In, First Out) or FILO (First In, Last Out) principle

  • Push: Adds an element to the top of the stack
  • Pop: Removes the top element from the stack
  • IsEmpty: Checks if the stack is empty
  • IsFull: Checks if the stack is full
  • Peek: Examines elements in the stack without removing them

• Private: Restricts data and functions to be accessed within the class

• Public: Data and functions are accessible from outside the class

• Data Members: Variables inside a class

• Member Functions: Methods performing specific tasks in a class

• Constructor: Special member function executed when new class objects are created

• Destructor: Special class member that is executed when an object goes out of scope or delete expression is applied

• Queue: Linear data structure open at both ends, following FIFO (First In First Out) principle

• Rear/Tail: End of a queue where new elements are inserted

• Front/Head: End of a queue where existing elements are removed -Enqueue: Function to add a node with a specified value to the back of the queue -Dequeue: Function to remove the first node of a queue

• Circular Queue: A queue where the last position is connected to the first, forming a circle

• Memory Management: Utilizes unused memory locations in circular queues

• Traffic System: Computer-controlled traffic systems use circular queues to control traffic lights according to a set time

• CPU Scheduling: Operating systems use queues to manage processes waiting for execution or specific events

• Priority Queues: Elements are prioritized based on urgency

• Linear Search: Sequential search, examining each element one by one until a match is found

• Binary Search: Efficient search algorithm for sorted lists, repeatedly halving the search portion until the item is found

Sorting:

• Process of rearranging data in a logical order

  • Types: Selection, Insertion, Bubble, Merge, Quicksort

• Selection Sort: Repeatedly selects the smallest (or largest) element from the unsorted portion and moves it to the sorted portion

• Insertion Sort: Splits the array into sorted and unsorted parts, inserting values from the unsorted part into their correct position in the sorted part

• Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order

  • Best case complexity for Selection, Insertion, and Bubble Sort: O(n) or Linear Time Complexity
  • Worst case complexity for Selection, Insertion, and Bubble Sort: O(n²) or Quadratic Time Complexity

• Merge Sort: Divides array into smaller subarrays, sorts them, and then merges them back

  • Best and worst case complexity: O(n log n)

• Quick Sort: Divide and Conquer algorithm, picks a pivot, and partitions the array around it

  • Average case complexity: O(n log n)
  • Worst case complexity: O(n²)

• Recursion: A function calling itself directly or indirectly

Divide and Conquer Algorithm:

• Algorithmic paradigm using Divide, Conquer, and Combine strategies
  • Time complexities of sorting types:
    • Selection - Quadratic (n²)
    • Insertion - Quadratic (n²)
    • Bubble – Quadratic (n²)
    • Merge - Quasilinear (n log n)
    • Quick - Quasilinear (n log n)
• Time Complexities:
  • Constant O(1): Runtime is constant
  • Linear O(n): Time grows linearly with the number of input elements
  • Quadratic O(n²): Time grows linearly with the square of the number of input elements
  • Logarithmic O(log n): Effort increases approximately by a constant amount when the number of input elements doubles
  • Quasilinear O(n log n): Effort grows slightly faster than linear because the linear component is multiplied by a logarithmic one
  • Exponential O(2ⁿ): Running time growth rate doubles with each addition to the input
  • Factorial (n!): Running time grows in a factorial way based on the size of the input data
• Asymptotic Analysis:
  • Big Oh (O): Upper bound and worst-case complexity
  • Big Omega (Ω): Lower bound and best-case complexity
  • Big Theta (Θ): Both upper and lower bound and best-worst case