Why learn DSA

A problem is a precise question: “given an array of integers, return its largest value”. An algorithm is a finite, step-by-step procedure that solves it. One problem has many algorithms, and an algorithm is only meaningful relative to the problem it claims to solve.

Searching a sorted array is one problem with at least three algorithms: linear search, binary search and interpolation search. They return the same answers and differ in cost.

Data is raw, uninterpreted values: 72, "Ana", true. Information is data in context: “Ana's heart rate is 72 beats per minute”. Programs store data and derive information from it.

How data is organised decides which questions are cheap. The same 72 stored in a sorted array answers “is anyone at 72?” quickly; stored in an unsorted list it needs a scan.

An abstract data type (ADT) describes behaviour: what operations exist and what they promise, such as a Stack with push, pop and peek. A data structure is a concrete way to store the data so those operations work: a stack can be an array with a size counter or a linked list with a head.

Java mirrors this split: List is an ADT (an interface), while ArrayList and LinkedList are data structures that implement it. Code that depends on the interface can switch structures without changing.

1List<Integer> items = new ArrayList<>();   // ADT on the left, structure on the right
2items.add(7);
3items.get(0);
4// swap the structure, keep every line that uses `items`
5items = new LinkedList<>();

A contract states what the caller must supply (preconditions) and what the code guarantees in return (postconditions). “Given a sorted array and a target, return its index or -1” is a contract. Binary search is correct for this contract and wrong for unsorted input, so the sortedness belongs in the contract, not in a hope.

Write the contract before the code: input types and ranges, what counts as valid, what to return for “not found” or empty input, and whether the input may be modified.

1/**
2 * Returns the index of target in arr, or -1 if absent.
3 * Precondition: arr is sorted ascending. Not modified.
4 * Postcondition: result == -1 or arr[result] == target.
5 */
6static int indexOf(int[] arr, int target) { ... }

Correctness asks “does it give the right answer for every valid input?”. Efficiency asks “how much time and memory does it use as the input grows?”. They are independent: a brute-force solution can be perfectly correct and far too slow.

Compare the two solutions to the same two-sum problem. Both are correct. The first checks every pair; the second remembers what it has seen. Run both on the same input and compare the number of operations.

1public static int[] twoSum(int[] nums, int target) {
2    for (int i = 0; i < nums.length; i++) {
3        for (int j = i + 1; j < nums.length; j++) {
4            if (nums[i] + nums[j] == target) {
5                return new int[] { i, j };
6            }
7        }
8    }
9    return new int[] { -1, -1 };
10}

1public static int[] twoSum(int[] nums, int target) {
2    Map<Integer, Integer> seen = new HashMap<>();      // value -> index
3    for (int i = 0; i < nums.length; i++) {
4        int need = target - nums[i];
5        if (seen.containsKey(need)) {
6            return new int[] { seen.get(need), i };
7        }
8        seen.put(nums[i], i);
9    }
10    return new int[] { -1, -1 };
11}

Scalability is how cost grows as input grows. An algorithm that takes 1 ms for 1,000 items might take 1 ms × 1,000 = 1 s for a million items if it is linear, 11 days if it is quadratic, and longer than the age of the universe if it is exponential.

Move the slider below to see how the growth classes diverge. Small inputs hide the problem; large ones expose it.

The structures in this course run underneath everyday systems. Choosing the right one is usually worth more than tuning code.