Data Structures Using Python - Engineering Notes
1. Data, Data Types, and Data Structure
Data: Data refers to raw facts and figures which can be processed to generate meaningful
information. Example: Numbers, characters, images, etc.
Data Types: Define the type of value a variable can hold. In Python:
- int: Integer values (e.g., 10, -5)
- float: Decimal values (e.g., 3.14)
- str: String or text (e.g., "Hello")
- bool: Boolean values (True or False)
- list, tuple, set, dict: Data structures for collection handling.
Data Structure: A data structure is a particular way of organizing and storing data for efficient
access and modification.
Examples: Arrays, Linked Lists, Stacks, Queues, Trees, Graphs, and Hash Tables.
2. Abstract Data Type (ADT)
An Abstract Data Type defines a mathematical model for data types where only behavior is defined,
not implementation details.
Example:
- Stack ADT supports operations: push(), pop(), peek()
- Queue ADT supports: enqueue(), dequeue()
ADT helps in modular programming and data abstraction.
3. Representation of Information
Information is represented using data structures such as arrays, trees, or graphs. In computer
memory, data is stored in binary (0s and 1s).
Example:
Character 'A' → ASCII code 65 → Binary 01000001
Representation decides how efficiently we can store and access data.
4. Characteristics of an Algorithm
1. Input: Takes zero or more inputs
2. Output: Produces at least one output
3. Definiteness: Each step is precisely defined
4. Finiteness: Algorithm terminates after finite steps
5. Effectiveness: Each step is basic and executable
6. Generality: Should solve all instances of a problem
Example: Algorithm to find the maximum of two numbers.
5. Program and Program Analysis
A program is an implementation of one or more algorithms written in a programming language like
Python.
Analyzing a program involves measuring:
- Time Complexity: How execution time grows with input size
- Space Complexity: How memory usage grows with input size
Example:
O(1): Constant time
O(n): Linear time
O(log n): Logarithmic time
6. Arrays
An array is a collection of elements of the same type stored in contiguous memory locations.
Python uses lists to implement arrays.
Example:
arr = [10, 20, 30, 40]
Access: arr[2] → 30
Storage Representation: Each element has a fixed memory address based on index.
Address(A[i]) = Base Address + (i * Size of element)
7. Sparse Matrices and Transpose
Sparse Matrix: A matrix with most of its elements as zero.
Example:
[0 0 3]
[0 0 0]
[2 0 0]
To store efficiently, use triplet form → (row, column, value).
Transpose: Interchange rows and columns of the matrix.
Example:
Original: (1,3,5) → Transpose: (3,1,5)
8. Hash Tables and Hashing
Hashing is a technique to map keys to positions in a table using a hash function.
Hash Table: A structure that stores key–value pairs for fast lookup.
Hash Function: h(key) = key % table_size
Direct Address Table: Uses keys as direct indices (works if key range is small).
Open Addressing:
If collision occurs, probe for the next empty slot.
Techniques:
- Linear Probing: h(k, i) = (h(k) + i) % m
- Quadratic Probing: h(k, i) = (h(k) + i²) % m
- Double Hashing: h(k, i) = (h1(k) + i * h2(k)) % m
Perfect Hashing: A hash function with no collisions.
Used when all keys are known in advance.
