COMP9123 — Data Structures & Algorithms
Week 1: Introduction & Analysis
This page starts where the real teaching starts: the lecture content from slide 44 onward. The goal is to leave Week 1 understanding what an algorithm is, how the course thinks about problems, and why efficiency language like Big-O matters.
Focus for this week: understand the course language before later weeks start layering on linked lists, trees, hashing, graphs, and greedy algorithms.
Why Algorithms Matter
Week 1 is not trying to impress you with advanced tricks. It is trying to build the right mental posture: solve problems systematically, explain your method clearly, and reason about whether it scales.
The lecture's big message: this course is your formal introduction to algorithms and data structures, and the point is not just to use existing ones. The point is to become confident enough to design your own and justify why they are correct and efficient.
Algorithms are everywhere
The lecture uses everyday examples on purpose: cooking, navigation, sorting, and simple decision procedures are all algorithms once the steps are explicit.
Good algorithms are precise
An algorithm is not just a vague idea. It must be finite, unambiguous, and effective enough that another person or machine could follow it.
Why the name matters
The slide on Al-Khwarizmi is there to remind you that algorithmic thinking is about systematic procedure, not just coding syntax.
Professor mindset: whenever you hear “algorithm”, ask three things immediately. What problem is being solved? What information do we keep while solving it? What would convince someone this method is both correct and efficient?
| Lecture example | What it teaches |
|---|---|
| Making a sandwich | Even a simple real-world task becomes clearer when broken into explicit ordered steps. |
| Finding the largest number | Comparison-based reasoning is the simplest way to introduce algorithm structure. |
| Sorting / searching | The same problem can have multiple algorithms, and the difference between them is often efficiency. |
The Three Abstractions You Must Keep Separate
This is the most important conceptual slide cluster in Week 1. If you keep these three layers separate, later weeks become much easier to reason about.
| Abstraction | What it means | Typical question you should ask |
|---|---|---|
| Computational problem | Defines the task itself: valid input and required output. | What counts as a correct answer? |
| Algorithm | A step-by-step method that transforms input into output. | How does the method actually proceed? |
| Correctness & complexity analysis | The argument that the algorithm works, plus how much time / space it uses. | Why should I trust it, and how expensive is it? |
If you confuse the problem with one specific algorithm, you stop looking for better solutions too early.
If you confuse the algorithm with the code, you end up arguing about syntax instead of logic.
If you skip analysis, you may have a correct method that is still a terrible choice at scale.
Common beginner mistake: “I wrote Python that works on my example” is not the same as “I solved the computational problem well.” The course will keep asking for all three levels: specification, method, and justification.
Pseudocode: Turning an Idea into a Procedure
The lecture's “largest of three numbers” example is doing more than teaching a tiny algorithm. It is teaching how to move from informal thinking to a reusable procedure.
Pseudocode is not code. It is structured enough to show the control flow clearly, but abstract enough that you focus on the logic rather than the language details.
Core example: largest of three
The teaching point is that a correct algorithm keeps a useful partial answer while scanning the input.
largest ← a
if b > largest then
largest ← b
if c > largest then
largest ← c
return largest
What this example is teaching
- Initialize a candidate answer.
- Compare new information against the current candidate.
- Update only when necessary.
- Return the maintained best-so-far value.
How it generalises to \(n\) numbers
Start with the first element as the current best, then scan the rest one by one. This is the same algorithmic idea, just with a loop instead of two fixed comparisons.
largest ← numbers[1]
for i ← 2 to n do
if numbers[i] > largest then
largest ← numbers[i]
return largest
Study tip: whenever the lecture gives a tiny example, ask yourself what pattern it is secretly teaching. In Week 1, the pattern is “maintain a useful invariant while scanning input.”
Data Structures: Organising Information to Support Algorithms
The lecture introduces data structures as the storage side of problem solving. Algorithms tell you what steps to perform; data structures determine what information is easy or expensive to access while performing them.
Definition: a data structure is a way of organising and storing data so that it can be accessed and modified efficiently for the problem at hand.
Arrays
Fixed-size indexed storage in contiguous memory. Great when direct access by position matters.
Lists
Good for ordered collections, especially when the size changes dynamically.
Trees
Useful when data has hierarchy: categories, file systems, search structure, expression structure.
Graphs
Useful when the interesting part is the relationship network between items rather than a strict order or hierarchy.
| Real-world analogy from the lecture | Data-structure idea |
|---|---|
| Organising books in a library | The same information can be stored in different ways depending on whether fast search, grouping, or update matters most. |
| Relationship network | Graphs model connections between entities better than linear collections do. |
| Indexed collection of values | Arrays make direct position-based access easy. |
The right question is never “which data structure is best?” It is “best for which operations, on which kind of problem?”
Python Essentials for This Course
The Python part of Week 1 is not trying to make you a Python expert in one lecture. It is giving you enough shared vocabulary so later code examples in the hub feel natural instead of distracting.
Core containers
You should recognise lists, tuples, dictionaries, and sets immediately and know the kind of information each one stores well.
Control flow
if, for, and while are the building blocks for expressing the algorithmic steps discussed earlier in the lecture.
Functions and classes
Functions package behaviour; classes package behaviour together with data. Later data-structure code will use both constantly.
Common structures
my_list = [1, 2, 3, 4]
my_tuple = (1, 2, 3)
person = {"name": "Alice", "age": 25}
Core flow patterns
if x > 0:
print("Positive")
for i in range(5):
print(i)
Important bridge: Python list is not the same thing as the abstract List ADT from later lectures, but it is often used as the concrete implementation students meet first.
Big-O, Growth, and the Search Examples
This is the part of Week 1 that changes how the whole course talks. From here on, “good” does not only mean correct. It also means appropriate growth in time and space as the input gets larger.
Big-O describes how performance grows as input size grows. It deliberately suppresses machine-specific details so two algorithms can be compared on the same conceptual scale.
| Notation | Meaning | How to think about it |
|---|---|---|
| \(O(\cdot)\) | Asymptotic upper bound | “No worse than this growth rate for large enough input.” |
| \(\Omega(\cdot)\) | Asymptotic lower bound | “At least this much growth.” |
| \(\Theta(\cdot)\) | Tight asymptotic bound | “Upper and lower bound agree up to constants.” |
Linear search
Check elements one by one until the target is found. In the worst case you inspect the whole collection, so the time cost is \(O(n)\).
Binary search
If the data is ordered, each comparison cuts the remaining search space roughly in half, which gives \(O(\log n)\) comparisons.
After one comparison, roughly half of the candidates are eliminated.
After two comparisons, about a quarter remain; after three, about an eighth remain.
You stop when the remaining search space is down to size 1, which happens after about \(\log_2 n\) halvings.
The lecture's homework-style Big-O slides are important. They are training you to look at assignment, conditionals, loops, and nested loops and translate code shape into growth shape.
Arrays: the First Concrete Structure
The lecture ends with arrays because they are the cleanest example of how storage design creates both strengths and limitations.
Array idea: a collection of elements stored in fixed order, where each position has an index and can therefore be accessed directly.
| Array feature | Why it is useful | What it costs you |
|---|---|---|
| Indexed positions | Fast access and update by location. | You must think carefully about valid index ranges. |
| Contiguous layout | Simple and efficient memory access. | Size is fixed in the classical array model. |
| Set / get operations | Natural for many algorithms. | Middle insertions are awkward because later elements must shift. |
Classical array mindset
An array is declared with a type and size before use. That makes the memory model clean and predictable, which is why it is so common in algorithm discussion.
Python reality
Python does not expose low-level arrays as its default everyday container. In practice, Python list plays the role students usually rely on first.
Bridge to later weeks: Week 1 introduces arrays as a clean starting point. Later weeks will keep asking when their strengths are exactly what you need and when more flexible structures are worth the extra complexity.
Chapter Quizzes
Use the embedded checks above as you move through the page, then switch to the Quiz Hub and flashcards for broader repetition.
Best use: answer each local quick check right after its section. If you miss one, go back immediately, restate the idea aloud, and only then continue.