Unit 1: Introduction and arrays
Data Structures-I notes · PTU syllabus (UGCC2506)
On this page
Unit summary
A data structure is a way of organising data in memory so that it can be used efficiently. Choosing the right data structure decides how fast a program runs. This unit introduces data structures, how to measure an algorithm's efficiency, and the most basic structure of all — the array.
After this unit you can
- Define and classify data structures and list their operations
- Analyse algorithm complexity using Big-O, Omega and Theta notation
- Perform traversal, insertion and deletion on linear arrays
- Represent two-dimensional, multi-dimensional and sparse matrices in memory
PTU syllabus topics
- Definition
- classification and operations of data structures
- algorithm complexity
- asymptotic notations
- time-space trade-off
- linear array representation and operations (traversing, inserting, deleting)
- two-dimensional arrays
- sparse matrices
- multi-dimensional arrays
- O(1)
Constant: array access by index
- O(log n)
Logarithmic: binary search
- O(n)
Linear: traversing an array
- O(n log n)
Merge sort, heap sort
- O(n²)
Bubble, selection, insertion sort
Topic 1
Data structures: definition, classification and operations
A data structure is a logical or mathematical model for organising data so it can be stored and processed efficiently.
Primitive
int, float, char, pointer
Linear
Array, linked list, stack, queue
Non-linear
Tree, graph
Static vs dynamic
Fixed size (array) vs grows at run time (linked list)
Common operations: traversing (visiting each element), searching, inserting, deleting, sorting and merging.
Topic 2
Algorithm complexity and asymptotic notation
The complexity of an algorithm is the amount of time (time complexity) and memory (space complexity) it needs as a function of the input size n.
| Notation | Meaning | Describes |
|---|---|---|
| Big-O, O(f(n)) | Upper bound | Worst case |
| Omega, Ω(f(n)) | Lower bound | Best case |
| Theta, Θ(f(n)) | Tight bound | Exact growth rate |
Common growth rates from fastest to slowest: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
Example
Linear search checks up to n elements, so it is O(n); binary search halves the range each step, so it is O(log n).
Time-space trade-off: we can often make a program faster by using more memory (for example a lookup table), or save memory at the cost of speed.
Topic 3
Linear arrays and their operations
A linear array is a list of a finite number of elements of the same type stored in consecutive memory locations.
- Address of an element: LOC(A[k]) = Base(A) + w × (k − LB), where w is the size of each element and LB is the lower bound.
Example
If Base = 1000, w = 4 bytes and LB = 0, the address of A[5] is 1000 + 4 × 5 = 1020.
- 1Check for overflow
Array must not be full
- 2Shift elements
Move A[N] … A[K] one place right
- 3Insert
A[K] = ITEM
- 4Increase N by 1
Deletion is the reverse: remove A[K], shift A[K+1] … A[N] one place left, and decrease N by 1. Both are O(n) in the worst case because of shifting; traversal is O(n).
Topic 4
Two-dimensional and multi-dimensional arrays
A 2-D array A[m][n] is stored in memory in one of two orders:
- Row-major order: row by row (used by C). LOC(A[i][j]) = Base + w × [n(i − LB₁) + (j − LB₂)]
- Column-major order: column by column (used by FORTRAN). LOC(A[i][j]) = Base + w × [m(j − LB₂) + (i − LB₁)]
Multi-dimensional arrays (3-D and above) extend the same idea with more indexes.
Topic 5
Sparse matrices
A sparse matrix has most of its elements equal to zero. Storing all zeros wastes memory, so only non-zero elements are stored as (row, column, value) triplets.
Example
A 4 × 4 matrix with only 3 non-zero values needs 16 cells normally, but only 3 triplets (plus a header row giving 4, 4, 3) in triplet form.
Special sparse matrices include lower triangular, upper triangular and tridiagonal matrices.
Key terms
- Data structure
- An organised way of storing data for efficient use
- Time complexity
- How running time grows with input size
- Big-O
- An upper bound on growth; describes the worst case
- Row-major order
- Storing a 2-D array row by row
- Sparse matrix
- A matrix with mostly zero elements
Quick revision
- Linear: array, linked list, stack, queue; non-linear: tree, graph.
- O = worst, Ω = best, Θ = tight bound.
- LOC(A[k]) = Base + w(k − LB).
- Insertion and deletion in arrays need shifting: O(n).
- Store sparse matrices as triplets.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Define a data structure and classify it.
- Q2.What is time-space trade-off?
- Q3.Differentiate between Big-O and Theta notation.
- Q4.Write the address formula for row-major order.
- Q5.What is a sparse matrix?
- Q6.List the operations on data structures.
Long-answer questions
- Q1.Explain the classification of data structures with examples and the operations performed on them.
- Q2.Explain asymptotic notations with examples of common growth rates.
- Q3.Write algorithms to insert and delete an element in a linear array and find their complexity.
- Q4.Explain row-major and column-major representation of 2-D arrays with an address calculation example.
Stuck on this unit?
Message SBS on WhatsApp for help with Data Structures-I, or to ask about studying BCA at Synetic.