Programming and Data Structures

PDF version of this text.

This document was built on Feb 02, 2024.

List of Lectures

1. Introduction and Machine Model

2. Procedural Abstraction and Testing

3. Pointers

4. Arrays

5. Strings, Streams, and I/O

6. Compound Objects

7. Abstract Data Types in C

8. Abstract Data Types in C++

9. Inheritance

10. Polymorphism

11. Container ADTs I

12. Container ADTs II

13. Memory Models and Dynamic Memory

14. Managing Dynamic Memory

15. The Big Three

16. Linked Lists

17. Iterators

18. Recursion

19. Structural Recursion

20. Function Pointers, Functors, and Impostor Syndrome

21. Maps, Auto, and Range-Based For Loops

22. Error Handling and Exceptions

23. Containers of Pointers

Foundations

• Introduction
• Machine Model
• Function Calls and the Call Stack
  • Function-Call Process
• Procedural Abstraction
  • Code Organization in C++
  • The Compilation Process
  • Specification Comments (RMEs)
    • REQUIRES Clause
    • MODIFIES Clause
    • EFFECTS Clause
  • Properties of Procedural Abstraction
• Testing
• Pointers
  • Pointer Errors
  • Pointers and References
• Arrays
  • Arrays and Pointers
  • Pointer Arithmetic
  • Array Indexing
  • More on Array Decay
  • The End of an Array
  • Array Traversal
• Strings
  • C-Style Strings
    • String Traversal and Functions
    • Printing C-Style Arrays
  • C++ Strings
• Command-Line Arguments
• Input and Output (I/O)
  • I/O Redirection
  • Example: Adding Integers
  • File I/O

Data Abstraction

• The const Keyword
  • References and const
  • Arrays and const
  • Pointers and const
  • const Conversions
• Compound Objects
  • Compound Objects and const
• Abstract Data Types in C
  • Representation Invariants
  • Plain Old Data
  • Abstraction Layers
  • Testing an ADT
• Streams in C++
  • String Streams
• 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

• Container ADTs
  • 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
• Iterators
  • Iterator Definition
    • Dereference and Increment Operators
    • The typename Keyword
    • Equality Comparisons
    • Creating Iterators
  • Friend Declarations
  • Generic Iterator Functions
  • Iterator Invalidation

Functional Programming

• 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
• Function Pointers and Functors
  • Function-Pointer Types
  • Function-Pointer Parameters
  • Functors
  • Comparators
  • Iterating over a Sequence
• Impostor Syndrome
• Maps and Pairs
• Type Deduction and Range-Based For Loops
  • Range-Based For Loops
    • Iterating over a Map

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
• Containers of Pointers
  • Sorting Containers of Pointers
  • Containers of Polymorphic Objects

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

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.