• IDSA
  • Course Outline
    • Description
    • Details
    • Lecturers and Teaching Assistant
    • Timetable
    • Learning Management System
    • Communication and Consultations
    • Lab Attendance and QuickLabs
    • Textbook
    • Other Resources
    • Grading
    • Tentative Schedule
    • Satisfactory Performance
    • Additional Support
    • Academic Integrity
  • 1 Data Structures & Algorithms
    • 1.1 Analysis of Algorithms
    • 1.2 Best, Worst or Average?
    • 1.3 When do we actually care?
    • 1.4 Beyond Asymptotics: When Constants Still Matter
    • 1.5 Abstract Data Types
    • 1.6 Conclusion
    • 1.7 TODO
  • 2 C++ Revision
    • 2.1 Introduction
    • 2.2 Compilation
      • 2.2.1 Command Line
      • 2.2.2 Make
      • 2.2.3 Integrated Development Environments (IDEs)
    • 2.3 Hello World!
    • 2.4 Data Types
    • 2.5 Strings
    • 2.6 Reading input from stdin
    • 2.7 Vectors
    • 2.8 Branching (If Statements)
    • 2.9 Loops
      • 2.9.1 While Loops
      • 2.9.2 Do Loops
      • 2.9.3 For Loops
    • 2.10 Pointers
      • 2.10.1 Basics
      • 2.10.2 Initialisation & Null Pointers
    • 2.11 References
    • 2.12 Classes
      • 2.12.1 Interactive Example
    • 2.13 Arrays
    • 2.14 Static & Dynamic Allocation
    • 2.15 Recursion
    • 2.16 Debugging
    • 2.17 Setting up your environment
      • 2.17.1 Install a C++ compiler
      • 2.17.2 Install VS Code
      • 2.17.3 Install the C/C++ extension
      • 2.17.4 Compiling and running your code from the terminal
      • 2.17.5 (Optional) Debugging in VS Code
  • 3 Searching and Sorting
    • 3.1 Introduction
    • 3.2 Searching Algorithms
      • 3.2.1 Linear Search
      • 3.2.2 Binary Search
      • 3.2.3 Linear vs Binary Search
    • 3.3 Sorting Algorithms
      • 3.3.1 Insertion Sort
      • 3.3.2 Selection Sort
      • 3.3.3 Bubble Sort
      • 3.3.4 Summary
      • 3.3.5 Overall Comparison
  • 4 Arrays & Vectors
    • 4.1 Abstract Data Type: Lists
    • 4.2 Memory Management
    • 4.3 Contiguous Memory & Pointer Arithmetic
    • 4.4 Increasing the size of an array
    • 4.5 std::array and std::vector
    • 4.6 Reallocation & Complexity
    • 4.7 Questions
    • 4.8 Additional Reading
  • 5 Linked Lists
    • 5.1 Introduction
      • 5.1.1 Arrays
      • 5.1.2 Questions
    • 5.2 When arrays aren’t good enough
      • 5.2.1 Questions
      • 5.2.2 Linked Structures
    • 5.3 Linked Lists – forward_list
    • 5.4 Operations
      • 5.4.1 push_front
      • 5.4.2 pop_front
      • 5.4.3 get_link
      • 5.4.4 at
      • 5.4.5 push_back
      • 5.4.6 pop_back
      • 5.4.7 insert
      • 5.4.8 erase
      • 5.4.9 Size
    • 5.5 Iterators
      • 5.5.1 What?
      • 5.5.2 Why?
    • 5.6 Doubly Linked Lists
    • 5.7 Other Linked List Structures
    • 5.8 Drawbacks of Linked Structures
      • 5.8.1 Linear Searches
      • 5.8.2 Locality of Reference – Caching
      • 5.8.3 Be Careful
    • 5.9 Lab
    • 5.10 Additional Reading
  • Published with bookdown

Introduction to Data Structures & Algorithms

Introduction to Data Structures & Algorithms

COMS1017A

Prof. Richard Klein

Semester 2, 2026
[Updated: 2026-08-20]