• Course Outline
    • Description
    • Details
    • Lecturer
    • Timetable
    • Learning Management System
    • Communication
    • Consultations
    • Textbook
    • Other Resources
    • Grading
    • Tentative Schedule
    • Satisfactory Performance
    • 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 What are we ignoring?
    • 1.5 Abstract Data Types
    • 1.6 Conclusion
    • 1.7 TODO
  • 2 C++
    • 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 Structs & Classes
    • 2.13 Arrays
    • 2.14 Static & Dynamic Allocation
    • 2.15 Recursion
    • 2.16 Classes
    • 2.17 Pointers
    • 2.18 Debugging
    • 2.19 Setting up your environment
      • 2.19.1 Linux
      • 2.19.2 Windows/MacOS
      • 2.19.3 Installing Qt
  • 3 Arrays & Vectors
    • 3.1 Abstract Data Type: Lists
    • 3.2 Memory Management
    • 3.3 Contiguous Memory & Pointer Arithmetic
    • 3.4 Increasing the size of an array
    • 3.5 std::array and std::vector
    • 3.6 Reallocation & Complexity
    • 3.7 Questions
    • 3.8 Additional Reading
  • 4 Linked Lists
    • 4.1 Introduction
      • 4.1.1 Arrays
      • 4.1.2 Questions
    • 4.2 When arrays aren’t good enough
      • 4.2.1 Questions
      • 4.2.2 Linked Structures
    • 4.3 Linked Lists – forward_list
    • 4.4 Operations
      • 4.4.1 push_front
      • 4.4.2 pop_front
      • 4.4.3 get_link
      • 4.4.4 at
      • 4.4.5 push_back
      • 4.4.6 pop_back
      • 4.4.7 insert
      • 4.4.8 erase
      • 4.4.9 Size
    • 4.5 Iterators
      • 4.5.1 What?
      • 4.5.2 Why?
    • 4.6 Doubly Linked Lists
    • 4.7 Other Linked List Structures
    • 4.8 Drawbacks of Linked Structures
      • 4.8.1 Linear Searches
      • 4.8.2 Locality of Reference – Caching
      • 4.8.3 Be Careful
    • 4.9 Lab
    • 4.10 Additional Reading
  • 5 Stacks
    • 5.1 Introduction
    • 5.2 Operations
    • 5.3 Implementations
      • 5.3.1 Vector Implementation
      • 5.3.2 Linked List Implementation
    • 5.4 std::stack<T, C>
    • 5.5 Applications
      • 5.5.1 Postfix Notation
      • 5.5.2 Depth First Search
    • 5.6 Lab
    • 5.7 Project: Solving Sudokus
    • 5.8 Additional Reading
  • 6 Queues
    • 6.1 Introduction
    • 6.2 Operations
    • 6.3 Implementations
      • 6.3.1 Contiguous Implementation
      • 6.3.2 Linked List Implementation
    • 6.4 std::queue<T, C>
    • 6.5 Project – The Shortest Path in a Maze (BFS)
      • 6.5.1 Breadth First Search (BFS)
      • 6.5.2 Algorithm
      • 6.5.3 Examples
      • 6.5.4 Pseudocode
      • 6.5.5 Sample Input/Output
      • 6.5.6 Submission & Grading
    • 6.6 Additional Reading
  • 7 Computational Complexity
  • 8 Binary Search Trees
    • 8.1 Trees
    • 8.2 Binary Trees
    • 8.3 Binary Search Tree
      • 8.3.1 Insertion
      • 8.3.2 Searching
      • 8.3.3 Min & Max
      • 8.3.4 Delete
    • 8.4 Tree Traversals
      • 8.4.1 Depth First Traversals
      • 8.4.2 Breadth-First or Level Traversals
    • 8.5 Lab: Binary Search Trees
      • 8.5.1 Submission 1
      • 8.5.2 Submission 2
      • 8.5.3 Submission 3
      • 8.5.4 Submission 4
      • 8.5.5 Recommend Structure
    • 8.6 Additional Reading
  • 9 Balanced Trees
    • 9.1 AVL Trees
  • 10 Binary Heaps
  • 11 Searching and Sorting
    • 11.1 Introduction
    • 11.2 Searching Algorithms
      • 11.2.1 Linear Search
      • 11.2.2 Binary Search
      • 11.2.3 Linear vs Binary Search
    • 11.3 Sorting Algorithms
      • 11.3.1 Insertion Sort
      • 11.3.2 Selection Sort
      • 11.3.3 Bubble Sort
      • 11.3.4 Summary
    • 11.4 Lab
  • 12 Final Words
  • References

Introduction to Data Structures & Algorithms

Introduction to Data Structures & Algorithms

COMS1017A & COMS1021A

Prof. Richard Klein

Semester 2, 2024
[Updated: 2024-09-17]