Java: Data Types and Abstract Data Types

• A type defines the set of all possible values a variable can hold
  • Example:
    • int type includes -100, 0, and 1000
    • string type includes "hello", "world", and "123"
• Data type defines what kind of data a variable holds and the set of operations possible on that data
  • Example:
    • int allows for operations like addition and subtraction
    • string allows for concatenation or finding the length

Java Abstract Data Type (ADT)

• An ADT defines what operations can be performed but not how the data is implemented internally
• Stack is an ADT
  • push(item): Adds to the top
  • pop(): Removes the top item
  • peek(): Views the top item
  • isEmpty(): Checks if the stack is empty

Data Structure

• A data structure is how data is stored and organized in memory, it's how an ADT is implemented
  • Stacks, for instance, use arrays, linked lists and hash tables

List Abstract Data Type (ADT)

• Allows storing elements in a specific order, enabling access, insertion, or removal at specific positions
• Operations:
  • get(index): Returns element from index
  • size(): Returns number of elements in the list
  • isFull(): Returns true if the list is full
  • removeAt(index): Removes the element at the specified index

Stack

• Stack contains similar elements in a sequence, where only the last element added is accessible first (LIFO - Last In, First Out)
  • Only plates from the top can be added or removed
• Operation:
  • push(E e): Inserts an element at the top

Priority Queue

• Processes elements based on priority, not arrival order
• Heap Sort is often implemented using a Heap, which is a specialized version of a priority queue
• Operations:
  • peek(): Returns the front element with the highest priority
  • isFull(): Checks if the queue is full
  • isEmpty(): Checks if the queue is empty
  • offer(E e): Adds an element to the queue, returns false if full
  • remove(): Removes a specific element
  • poll(): Removes and returns the highest-priority element

Binary Heap

• A complete binary tree with the Heap Property
  • Max-Heap: Parent node is greater than or equal to its children
  • Min-Heap: Parent node is less than or equal to its children
• Heap Sort is an efficient sorting algorithm that uses the heap structure to sort data

Search Algorithms

• Techniques to find an element in a data structure
  • Linear Search: Iterates through each element until the target is found (slow for large lists)
    • Example: Searching for a number in an unsorted list.
  • Binary Search: Efficient search for sorted lists by repeatedly dividing the search range in half.
    • Example: Searching for a number in a sorted array by halving the search space each time

Sorting Algorithms

• Organize data in a specific order
  • Stability: A sorting algorithm is stable if it maintains the relative order of records with equal keys
• Types of Sorting Algorithms:
  • Insertion Sort: Like sorting playing cards, insert one item at a time into the correct position
  • Merge Sort: Divides the data into smaller parts, sorts them, and then merges them back together
  • Bubble Sort: Repeatedly swaps adjacent elements that are out of order
  • QuickSort: Divides the data into two parts and sorts them recursively
  • Selection Sort: Selects the smallest element and swaps it with the first unsorted element

Set

• A set is an unordered collection of distinct elements, meaning no duplicates
  • Example: A set of unique numbers: {1, 2, 3, 4}
• Operations:
  • add(E e): Adds an element
  • remove(E e): Removes an element

Dictionary

• A dictionary is a collection of data that stores key-value pairs
  • Word is the key, and the definition is the value
  • Implemented using Map interface (e.g., HashMap) in Java

Recurrence Relation

• Describes a sequence in terms of previous terms
  • Example: Fibonacci sequence: F(n) = F(n-1) + F(n-2)
• Useful for analyzing recursive algorithms

Data Compression

• Reduces the size of data
  • Huffman Coding assigns shorter codes to more frequent elements and longer codes to less frequent ones

Study Tips

• Explain concepts out loud
• Applying each data structure or algorithm with examples from real life helps provide context
• Draw diagrams for data structures like trees, heaps, and queues to understand their structures better