Syllabus

This syllabus is the alignment note between this course and the 408 exam outline: it first lays out the three levels of mastery the course expects, and then lists the exam scope chapter by chapter, from linear lists all the way to sorting and searching. Read it once before you start, and you can use it to judge how much weight each chapter carries; if you are preparing for the exam, treat it as the checklist of “what must be mastered” versus “what only needs to be recognised”.

Assessment Objectives

  1. Master the basic concepts, principles, and methods of data structures.
  2. Master the logical and storage structures of data and the implementation of their basic operations, and be able to perform basic time- and space-complexity analysis on algorithms.
  3. Be able to analyse and solve problems using the principles and methods of data structures, and be able to design and implement algorithms in C or C++.

1. Linear Lists

  • (a) Basic concepts of linear lists
  • (b) Implementation of linear lists
    1. Sequential storage
    2. Linked storage
  • (c) Applications of linear lists

2. Stacks, Queues, and Arrays

  • (a) Basic concepts of stacks and queues
  • (b) Sequential storage structures for stacks and queues
  • (c) Linked storage structures for stacks and queues
  • (d) Storage of multidimensional arrays
  • (e) Compressed storage of special matrices
  • (f) Applications of stacks, queues, and arrays

3. Trees and Binary Trees

  • (a) Basic concepts of trees
  • (b) Binary trees
    1. Definition of a binary tree and its main properties
    2. Sequential and linked storage structures for binary trees
    3. Traversal of binary trees
    4. Basic concepts and construction of threaded binary trees
  • (c) Trees and forests
    1. Storage structures for trees
    2. Conversion between forests and binary trees
    3. Traversal of trees and forests
  • (d) Applications of trees and binary trees
    1. Binary search trees
    2. Balanced binary trees
    3. Huffman trees and Huffman coding

4. Graphs

  • (a) Basic concepts of graphs
  • (b) Storage of graphs and their basic operations
    1. Adjacency matrix method
    2. Adjacency list method
    3. Adjacency multilist and orthogonal list
  • (c) Traversal of graphs
    1. Depth-first search
    2. Breadth-first search
  • (d) Basic applications of graphs
    1. Minimum (cost) spanning tree
    2. Shortest path
    3. Topological sorting
    4. Critical path

5. Searching

  • (a) Basic concepts of searching
  • (b) Sequential search
  • (c) Block search
  • (d) Binary search
  • (e) B-trees and their basic operations; the basic concept of B+ trees
  • (f) Hash tables
  • (g) String pattern matching
  • (h) Analysis and application of searching algorithms

6. Sorting

  • (a) Basic concepts of sorting
  • (b) Insertion sort
    1. Direct insertion sort
    2. Binary insertion sort
  • (c) Bubble sort
  • (d) Simple selection sort
  • (e) Shell sort
  • (f) Quick sort
  • (g) Heap sort
  • (h) Two-way merge sort
  • (i) Radix sort
  • (j) External sorting
  • (k) Comparison of the various sorting algorithms
  • (l) Applications of sorting algorithms

More courses

Recommended courses

Found an issue with this content?

Tell us what could be improved.