Programming and Data Structures

PDF version of this text.

This document was built on Sep 08, 2024.

List of Lectures

1. Introduction and C++

2. Types, Control Structures, and Procedural Abstraction

3. Machine Model I

4. Machine Model II

5. Const, Structs, and ADTs in C

6. Streams and I/O

7. Program Design

8. Abstract Data Types in C++

9. Derived Classes and Inheritance

10. Polymorphism

11. Containers and Iterators

12. Time Complexity, Arrays, and Pointer Arithmetic

13. Array-based Containers I

14. Array-based Containers II

15. Memory Models and Dynamic Memory

16. Managing Dynamic Memory

17. The Big Three

18. Linked Lists

19. Implementing Iterators

20. Function Objects and Impostor Syndrome

21. Recursion

22. Structural Recursion

23. Binary Search Trees and Maps

24. Error Handling and Exceptions

Foundations

• Introduction
• C++ Fundamentals
• Types
  • Arithmetic and Comparisons
  • Library Types
• Control Structures
• Procedural Abstraction
  • Code Organization in C++
  • The Compilation Process
  • Specification Comments (RMEs)
    • REQUIRES Clause
    • MODIFIES Clause
    • EFFECTS Clause
  • Properties of Procedural Abstraction
• Testing
• Machine Model I
  • Pointers
    • Pointers and References
• Machine Model II
  • Pointer Errors
  • Function Calls and the Call Stack
    • Function-Call Process

Data Abstraction

• The const Keyword
  • References and const
  • Pointers and const
  • const Conversions
• Structs
  • Compound Objects and const
• Abstract Data Types in C
  • Representation Invariants
  • Plain Old Data
  • Abstraction Layers
  • Testing an ADT
• Command-Line Arguments
• Input and Output (I/O)
  • I/O Redirection
  • Example: Adding Integers
  • File I/O
• More on Streams
  • String Streams
• Program Design
• Abstract Data Types in C++
  • Implicit this->
  • Member Accessibility
  • Constructors
  • Default Initialization and Default Constructors
    • Implicit Default Constructor
  • Get and Set Functions
  • Information Hiding
  • Testing a C++ ADT
  • Member-Initialization Order
  • Delegating Constructors
• Derived Classes and Inheritance
  • Ordering of Constructors and Destructors
  • Name Lookup and Hiding
• Polymorphism
  • Function Overloading
  • Subtype Polymorphism
  • Static and Dynamic Binding
  • dynamic_cast
  • Member Lookup Revisited
  • The override Keyword
  • Abstract Classes and Interfaces

Containers and Dynamic Memory

• Containers and Iterators
  • Range-Based For Loops
    • Iterating over a Map
• Time Complexity
• Arrays
  • Arrays and Pointers
  • Pointer Arithmetic
  • Array Indexing
  • More on Array Decay
  • The End of an Array
  • Array Traversal
  • Arrays and const
• Array-based Containers
  • Set Operations
  • Code Example
  • Public Interface
  • static Data Members
  • Data Representation
  • size_t
  • Implementation
  • Sorted Representation
• Container ADTs and Polymorphism
  • Operator Overloading
  • Parametric Polymorphism
    • Function Templates
    • Compiling Templates
    • Include Guards
    • Member-Function Templates
    • Insertion-Operator Template
    • Another Example
  • Static vs. Dynamic Polymorphism
    • Type Aliases
    • The Factory Pattern
    • Liskov Substitution Principle
• Memory Models and Dynamic Memory
  • Static Local Variables
  • Automatic Storage Duration
  • Address Space
  • The new and delete Operators
  • Dynamic Arrays
  • Lifetime of Class-Type Objects
  • Dynamic-Memory Errors
  • Uses for Dynamic Memory
• Managing Dynamic Memory
  • RAII
  • Growable Set
• The Big Three
  • Copy Constructor
  • Assignment Operator
  • Shallow and Deep Copies
  • The Law of the Big Three
  • Example: Calls to the Big Three
  • Destructors and Polymorphism
• Linked Lists
  • Traversing a Linked List
  • Linked List Big Three
  • Insertion and Removal at the End
  • List Template
• Implementing Iterators
  • Iterator Definition
    • Dereference and Increment Operators
    • The typename Keyword
    • Equality Comparisons
    • Creating Iterators
  • Friend Declarations
  • Generic Iterator Functions
  • Iterator Invalidation
  • Type Deduction

Functional Programming

• Function Objects
  • Function-Pointer Types
  • Function-Pointer Parameters
  • Functors
  • Comparators
  • Iterating over a Sequence
• Impostor Syndrome
• Recursion
  • Tail Recursion
  • Kinds of Recursion
  • Iteration vs. Recursion
• Structural Recursion
  • Recursive Lists
  • Trees
    • Tree Traversals
• Binary Search Trees (BSTs)
  • The BinarySearchTree Interface
  • BST-Based Set
• Maps and Pairs

Odds and Ends

• Error Handling and Exceptions
  • Global Error Codes
  • Object Error States
  • Return Error Codes
  • Exceptions
    • Exception Objects
    • Try/Catch Blocks
    • Exception Propagation
    • Exception Examples
  • Error Handling vs. Undefined Behavior

Supplemental Material

• Introduction to C++
  • A Simple Program
  • Static Typing
  • Compound Data
  • Value Semantics
  • Example: Stickman
    • Program Constants
    • The Game Struct
    • Task Decomposition
    • Implementation
    • Testing and File Organization
• Solving Problems with Recursion
  • Pancake Sort
  • Tower of Hanoi
  • Counting Change
• Containers of Pointers
  • Sorting Containers of Pointers
  • Containers of Polymorphic Objects
• C and C++ Strings
  • C-Style Strings
    • String Traversal and Functions
    • Printing C-Style Arrays
  • C++ Strings

About

These notes were written by Amir Kamil in Winter 2019 for EECS 280. They are based on the lecture slides by James Juett and Amir Kamil, which were themselves based on slides by Andrew DeOrio and many others.

This text is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license.