COMP5112 Data Structures and Database Systems
The Complete Exam Bible · Semester 1 2026/27COMP5112 Overview
- The Hong Kong Polytechnic University
- Semester 1 2026/27
- Postgraduate programme core
- Computer Science
- Three credit subject
What this subject is designed to do
COMP5112 is a programme core subject designed for students who do not already have a Computing or Computer Science background. It has two connected halves. The first develops algorithmic problem solving through data structures, searching and sorting.
- Assessment One quiz, two assignments and an examination, with the current course outline giving the detailed split.
- Exam evidence Algorithm questions may use pseudocode, while C and C++ language detail is not the focus.
- Core method Trace intermediate state, state the invariant or dependency, and then justify the complexity or design.
- Source limit Exact examination duration, sections and permitted materials must be confirmed on Canvas when published.
How COMP5112 is assessed
| Component | Weight | Format |
|---|---|---|
| Quiz (1) | 10% | Week 8, short questions, 45 minutes, covering data structures |
| Assignments (2) | 20% | Due around Weeks 6 and 13, covering data structures and the first part of databases |
| Examination | 70% | Examination period published as 3 to 18 December, subject to scheduling |
The September 2026 course outline splits continuous assessment into Quiz 10% and Assignments 20%, while the July 2025 Subject Description Form groups them together as Quizzes and Assignments 30%. Both sources give the examination 70% and total 100%. The more specific current-offering split is shown here. The captured sources do not publish the examination duration, sections or permitted materials.
Current COMP5112 dates
| Date | Item | Control |
|---|---|---|
| 13 October 2026 | Assignment 1 | The assignment PDF and Canvas syllabus page show this due date. |
Dates are as published in the course outline, Canvas syllabus page and Assignment 1 brief for this offering. Confirm exact deadlines and submission settings in the live LMS.
What COMP5112 covers
Eleven chapters move from algorithm analysis and data structures through sorting into database systems, relational design and query access.
Algorithm Design and Growth Rates
correctness, operation counts, asymptotic upper bounds and the growth classes used to compare algorithmsFrom a problem to a defensible algorithm
This chapter separates computational problems, algorithms and programs, then shows why test cases cannot prove correctness.
- Computational problems and algorithms
- Correctness beyond test cases
- Worst-case running-time functions
- Asymptotic upper bounds
- Dominant-term simplification
- Common growth classes
Searching Arrays Efficiently
linear search, binary search, inclusive boundaries and workload choices for sorted arraysInformation creates the speed-up
Linear search works on an unsorted array and may inspect every item. Binary search gains logarithmic time only because sorted order lets one comparison discard half the remaining interval.
- Linear search on unsorted arrays
- Binary-search preconditions
- Inclusive boundary traces
- Successful and failed lookup
- Logarithmic interval shrinkage
- Search and update workload trade-offs
Stacks, Queues and Expression Processing
LIFO and FIFO operations, circular arrays, postfix evaluation and infix conversionAccess order is the abstraction
A stack removes the most recent item, while a queue removes the earliest.
- Stack LIFO operations
- Queue FIFO operations
- Array stack state
- Circular-array queue indices
- Postfix evaluation
- Infix-to-postfix conversion
Linked Lists and Pointer Updates
doubly linked structure, search, insertion, removal, sentinels and pointer-safe update orderLocal changes require global reachability
Linked lists store nodes through references instead of contiguous positions.
- Doubly linked structure
- Forward and backward reachability
- Search by key
- Insertion update order
- Removal update order
- Head, tail and sentinel cases
Tree Structure and Traversal
rooted-tree vocabulary, recursive structure, preorder, inorder, postorder and reconstructionRecursive structure controls the visit order
A rooted tree is built from nodes and subtrees, with depth measured from the root and height measured down to a leaf.
- Root, parent, child and leaf
- Depth and height
- Recursive subtrees
- Preorder traversal
- Inorder traversal
- Postorder and reconstruction
Binary Search Trees and AVL Balance
search-tree ordering, search paths, insertion, deletion, height balance and rotationsOrdering converts comparisons into paths
A binary search tree requires every left-subtree key and every right-subtree key to respect bounds inherited from all ancestors.
- Global search-tree ordering
- Search and insertion paths
- Minimum and maximum
- Leaf and one-child deletion
- Two-child successor deletion
- AVL balance and rotations
Heaps and Priority Queues
array-tree correspondence, heapify, construction, heapsort and priority queue operationsComplete shape enables index arithmetic
A max-heap combines a complete binary-tree shape with the rule that each parent is at least as large as its children. Level-order array storage turns child and parent links into arithmetic.
- Complete binary-tree shape
- Heap parent-child property
- Array index mapping
- Max-Heapify precondition
- Bottom-up heap construction
- Heapsort and priority queues
Elementary Sorting and Stability
selection, bubble and insertion sort traces, best and worst cases, movement and stabilityQuadratic algorithms still make different promises
Selection, bubble and insertion sort share familiar quadratic worst cases but build order differently.
- Selection-sort minimum placement
- Bubble-sort adjacent inversions
- Insertion-sort sorted prefixes
- Comparison and movement counts
- Best and worst arrangements
- Stable equal-key ordering
Merge Sort, Quick Sort and Recurrences
divide and conquer, merging, partition invariants, recursion trees and pivot-sensitive boundsRecursion shape explains the bound
Merge sort and quick sort both divide arrays and recurse, but merge sort spends linear work combining sorted halves while quick sort spends linear work partitioning before the calls.
- Divide and conquer phases
- Two-index merging
- Merge-sort recurrence
- Partition invariants
- Quick-sort pivot balance
- Best, expected and worst cases
Database Systems and Data Independence
DBMS roles, file-processing failures, database models, layered schemas and independenceShared data needs a management layer
A DBMS gives applications a controlled way to store and query organisational data while centralising integrity, concurrency, recovery and access.
- Database, query and DBMS
- File-processing redundancy
- Integrity and transactions
- Concurrency and recovery
- Database model comparison
- Physical and logical independence
Relational Models and Database Design
relations, keys, SQL, entity relationships, dependencies, normalisation, indexing and query processingDesign moves from meaning to access
The official syllabus links relational structure, algebra, SQL and constraints to entity-relationship modelling, functional dependencies, normalisation, file organisation, indexing, hashing and query processing.
- Relations, tuples and attributes
- Primary and foreign keys
- Entity-relationship design
- Functional dependencies
- Normalisation and anomalies
- Indexes, hashing and query processing
The second introduces database systems and the design choices that let several applications share data safely.
The published learning outcomes ask for comprehensive understanding of data structures, sorting and searching algorithms, the application of database systems and their tools, and good database design and analysis in real problems.
Why the methods matter more than syntax
The course introduction says quiz and examination questions may ask about algorithms expressed as pseudocode but not about the programming language details of C or C++.
That places the emphasis on what the algorithm does: which state changes, why the next step is legal, what remains true, and how the running time grows. The guide therefore shows arrays after each pass, stack and queue boundaries, pointer rewiring, tree paths, active heap size and recurrence structure.
How the data structures fit together
Arrays support direct positions but make some updates expensive.
Stacks and queues restrict which item can leave next, enabling expression processing and arrival-order service. Linked lists trade direct indexing for local pointer updates. Search trees convert key comparisons into paths, AVL rotations protect height, and heaps expose an extreme item efficiently.
Sorting then compares how algorithms build ordered regions and how divide-and-conquer changes the growth rate.
How the database half changes the question
The database material moves from individual structures to shared information systems. A DBMS separates applications from physical storage, provides query access and centralises integrity, concurrency, recovery and authorisation.
Relational design identifies entities, keys and relationships, uses dependencies and normalisation to control repeated facts, and then selects storage and indexes for the query workload.
Correct logical design comes before physical tuning.
Evidence boundaries
The captured course contains current lecture decks through the introduction to database systems, tutorial exercises with answers, an assignment brief and the full official outline. Later database topics are named in the outline but their detailed lecture decks are not in the capture.
This guide teaches the standard relationships those named topics require while directing students to align terminology and depth with the later Canvas slides for their class. No past examination or sample final appears in the captured folder.
Worked example · free
Trace a heap repair before counting its cost
- 2Compare the root with both children and choose the larger child.
- 3Continue only along the branch that received the smaller key.
- 3Connect the number of downward moves to heap height.
Key terms
- Algorithm
- A finite, well-defined sequence of steps for solving a computational problem.
- Big-O Bound
- An asymptotic upper bound describing how an operation count grows as input size increases.
- Invariant
- A property that remains true across repeated algorithm steps and supports a correctness argument.
- Binary Search
- A search method that repeatedly discards half of a sorted interval after comparing its middle item.
- Stack
- A last-in, first-out abstract data type whose insertion and removal use the same active end.
- Queue
- A first-in, first-out abstract data type that inserts at the rear and removes from the front.
- Linked List
- A sequence represented by nodes connected through references rather than contiguous positions.
- Tree Traversal
- A systematic visit of every tree node in an order determined by when the current node is processed.
- AVL Tree
- A binary search tree that uses rotations to keep every node's subtree heights within one.
- Heap
- A complete binary tree with a parent-child priority property, commonly stored in level-order array positions.
- Stability
- The sorting property that equal-key records retain their original relative order.
- DBMS
- Software that manages shared database storage, querying, integrity, concurrency, recovery and access control.
- Foreign Key
- An attribute whose values reference a key in another relation to represent a relationship.
- Data Independence
- The ability to change one database representation layer while preserving interfaces at higher layers.
COMP5112 FAQ
How is the subject assessed?
The September 2026 outline lists one quiz worth ten per cent, two assignments worth twenty per cent together and an examination worth seventy per cent, totalling one hundred. The Subject Description Form groups the first two categories as thirty per cent. Use the detailed current outline for planning and confirm current task settings on Canvas.
What is known about the examination format?
The lecture introduction says algorithm questions may be based on pseudocode and will not test C or C++ language details. The captured material does not publish the examination duration, section structure, exact question count or permitted materials, so those details must come from the current Canvas announcement and official timetable.
How should I justify a Big-O answer?
Name the input size and basic operation, count how many times that operation executes, write the resulting function or sum and then simplify to the dominant growth term. A complexity class without the count can be plausible but unsupported, especially when loop ranges shrink or recursion creates unequal subproblems.
Do I need to memorise C++ implementations?
No language-specific examination focus is stated. The course introduction says pseudocode algorithms may be examined but not C or C++ language details. You should still understand what an implementation must preserve, such as bounds, saved pointers and base cases, because those facts explain whether the pseudocode is correct.
How do I choose the right data structure?
Start with the operation mix and the required removal or search order. Arrays support direct positions, stacks reverse access order, queues preserve arrival order, linked lists support local rewiring once a position is known, search trees organise comparisons and heaps support repeated access to an extreme priority.
Which sorting properties should I compare?
Compare worst, average or expected running time as appropriate, extra storage, stability, adaptiveness to existing order, cache locality and the input pattern that triggers a bad case. Algorithms sharing the same Big-O row can behave differently because these properties answer different workload needs.
What does good database design require?
Identify entities and stable keys, represent relationships with foreign keys, state functional dependencies from the real domain, decompose repeated facts without losing information and enforce integrity at the shared database layer. Only after the logical design is correct should indexes and file organisation be selected for the query workload.
Are past papers included in the captured materials?
No past examination, sample final, practice final or examination solution appears in the captured folder. Tutorial exercises and answer sheets show the course's tracing and reasoning methods, but they are not past papers and this guide does not imply that they reveal the final paper structure.
Questions students ask in each COMP5112 chapter
- Why do successful tests not prove correctness?
- A finite test set covers only selected instances, so an unseen input may still violate the required output. A correctness argument must explain why the algorithm works for every allowed input, often by stating a preserved invariant and showing termination. Chapter 01 · Algorithm Design and Growth Rates
- Why must binary-search data be sorted?
- The comparison with the middle value rules out a whole side only when position order agrees with key order. Without that property, a smaller target could appear on either side and discarding half would be unjustified. Chapter 02 · Searching Arrays Efficiently
- Why does postfix notation not need parentheses?
- The operator appears only after the operands it consumes, so a stack trace determines evaluation order without precedence punctuation. A valid expression also leaves exactly one final value after all tokens. Chapter 03 · Stacks, Queues and Expression Processing
- Is linked-list insertion always constant time?
- Only when the insertion position and necessary neighbour references are already known. Searching from head for a key or position adds linear time before the fixed local rewiring begins. Chapter 04 · Linked Lists and Pointer Updates
- What do preorder and postorder names refer to?
- They refer to whether the current node is processed before or after its recursive subtree visits. They do not describe a left-to-right sweep of a finished drawing. Chapter 05 · Tree Structure and Traversal
- Why is checking each parent and child not enough?
- A deep descendant can be correctly ordered relative to its parent and still violate a bound inherited from an ancestor. Carry lower and upper bounds down the tree throughout validation. Chapter 06 · Binary Search Trees and AVL Balance
- Why is a heap not a sorted array?
- The heap property constrains only parent-child relationships. Siblings and different subtrees need not be ordered, so arbitrary-key search may still inspect many items across the structure. Chapter 07 · Heaps and Priority Queues
- Why does selection sort not improve much on sorted input?
- Its inner search still compares the remaining items to locate the minimum. It may avoid an unnecessary self-swap, but the comparison count remains quadratic under the standard implementation. Chapter 08 · Elementary Sorting and Stability
- Why is merge sort O(n log n)?
- Balanced halving creates logarithmically many levels, and merging across all calls on each level processes O(n) items, giving O(n log n) total work after the base cases are included. Chapter 09 · Merge Sort, Quick Sort and Recurrences
- What is the main problem with duplicated files?
- One real fact gains several stored versions that can disagree after an update. The result is an update anomaly, not merely wasted storage, and applications can no longer know which copy is authoritative. Chapter 10 · Database Systems and Data Independence
- Why is a sample with no duplicates not enough to prove a key?
- A key follows the domain rules across all valid future states, not the accidental uniqueness of current rows. Ask whether two legitimate entities could share the value or whether it can change. Chapter 11 · Relational Models and Database Design
How to study for the exam
Use a three-column notebook: state, rule and cost. In the state column draw the array, stack, queue, pointers, tree, heap or relations after each meaningful action. In the rule column write the invariant, precondition, ordering property or functional dependency that justifies the action. In the cost column count the operation and state the bound only after the count is visible.
Alternate one data-structure trace with one database design prompt once the database half begins. Rework the tutorial question types with new numbers rather than memorising a published answer. In the final week, practise explaining a method aloud without C or C++ syntax, because the course itself places the algorithmic focus on pseudocode.
Check Canvas for the exact examination date, duration, sections and permitted materials before relying on any revision timetable.
Your AI Computer Science tutor for COMP5112
Stuck on a hard COMP5112 question? Sia is AskSia’s AI Computer Science tutor — ask any COMP5112 Data Structures and Database Systems question and get a clear, step-by-step explanation grounded in how the course is actually taught and assessed. Read this whole study guide free, then take your hardest questions to Sia.
