DS final

Data Structures Study Set

Fundamentals

• Data Structure: A systematic way of organizing and accessing data.

• Algorithm: A generic step-by-step set of instructions for solving a problem.

• Program: An implementation of an algorithm in code.

Abstract Data Types (ADTs)

• ADT (Abstract Data Type): A theoretical model of a data structure that specifies what operations are allowed but not how they are implemented.

Big O Notation

• Big O Notation: Describes the worst-case complexity of an algorithm.

  • O(1): Constant time – operations take the same time regardless of input size.

  • O(n): Linear time – performance scales directly with input size.

  • O(n²): Quadratic time – performance scales with the square of input size.

  • O(log n): Logarithmic time – performance scales logarithmically with input size.

  • O(bⁿ): Exponential time – performance doubles with each additional input.

  • O(n!): Factorial time – performance grows extremely fast with input size.

Python Object-Oriented Concepts

• Inheritance: A class can inherit attributes and methods from another class.

• Constructor (__init__): A special function that initializes an object.

• Import: Brings in external modules to use functions or classes.

• Functions: Blocks of reusable code that perform a task.

• Access Control:

  • Public attributes (self.attribute): Accessible from anywhere.

  • Protected attributes (self._attribute): Conventionally private but still accessible.

  • Private attributes (self.__attribute): Name-mangled to prevent direct access.

• __str__ Method: Defines how an object is represented as a string.

• Naming Conventions: Use snake_case for variables/functions and PascalCase for class names.

• self Keyword: Refers to the instance of the class.

Stack (LIFO - Last In, First Out)

• Definition: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, where the last element added is the first to be removed.

• Functions:

  • push(item): Adds an item to the top.

  • pop(): Removes and returns the top item.

  • peek(): Returns the top item without removing it.

  • size(): Returns the number of elements.

  • is_empty(): Returns True if stack is empty.

Queue (FIFO - First In, First Out)

• Definition: A queue is a linear data structure that follows the First In, First Out (FIFO) principle, where the first element added is the first to be removed.

• Functions:

  • enqueue(item): Adds an item to the back.

  • dequeue(): Removes and returns the front item.

  • size(): Returns the number of elements.

  • is_empty(): Returns True if queue is empty.

Deque (Double-Ended Queue)

• Definition: A deque (double-ended queue) is a data structure that allows insertions and deletions from both the front and back.

• Functions:

  • add_front(item): Adds an item to the front.

  • add_rear(item): Adds an item to the back.

  • remove_front(): Removes and returns the front item.

  • remove_rear(): Removes and returns the back item.

  • size(): Returns the number of elements.

  • is_empty(): Returns True if deque is empty.

Node

• Definition: A node is a fundamental building block of linked data structures, consisting of a data field and a reference (pointer) to the next node.

• Attributes:

  • data: Stores the value of the node.

  • next: Points to the next node in a linked list.

O(n) to find item in unsorted list

O(log n) is fastest Big O to find item in sorted list

Maximum height of a binary heap is O(log n)

Maximum height of a bairy search tree is O(n)
Maximum height of AVL tree is O(log n)

A stable sort maintains order of two teams with the same value

recursive function calls itself

Collision in a hash table is avoided through techniques such as chaining or open addressing, which allow multiple values to be stored without sacrificing performance. - open address next thing

collions in hash functions are when two items are placed in the same slot on the table

If you want a sorting algorithm that runs quickly and doesn't use a lot of memory, the best choice is: Quick Sort

Q: How can you tell if a graph is directed or undirected?
A: A graph is directed if its edges have arrows showing direction; it's undirected if edges connect nodes both ways with no arrows.

Q: What’s the key difference between directed and undirected graphs?
A: Directed graphs show one-way relationships, while undirected graphs show two-way (mutual) relationships.

Here are some flashcard-style notes specifically on AVL deletion rotations:

Q: What happens after deletion in an AVL tree?
A: The tree may become unbalanced, so rotations are used to restore balance.

Q: When is a rotation needed after deletion in an AVL tree?
A: A rotation is needed if the balance factor of any node becomes less than -1 or greater than 1.

Q: What are the 4 types of AVL rotations?
A: LL (Left-Left), RR (Right-Right), LR (Left-Right), and RL (Right-Left).

Q: What causes an LL rotation during AVL deletion?
A: LL rotation is needed when the left child of a node has a balance factor ≥ 0, and the node is left-heavy.

Q: What causes an RR rotation during AVL deletion?
A: RR rotation is needed when the right child has a balance factor ≤ 0, and the node is right-heavy.

Q: What causes an LR rotation during AVL deletion?
A: LR rotation is needed when the left child is right-heavy, so we first do RR on the child, then LL on the node.

Q: What causes an RL rotation during AVL deletion?
A: RL rotation is needed when the right child is left-heavy, so we do LL on the child, then RR on the node.

Q: Why can deletions cause multiple rotations in AVL trees?
A: Because imbalances can propagate upward, so each ancestor node may need rebalancing.