Data exam

Here's a detailed study set for your data structures class based on your worksheets and requested topics:

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)

• 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)

• 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)

• 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 (Basic Building Block for Linked Structures)

• Attributes:

  • data: Stores the value of the node.

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

Let me know if you need any modifications or explanations! 😊