Week 2: Analysis of Algorithms, Dynamic Data Structures
Week 2
Quiz Rules
Nerds You Should Know
Analysis of Algorithms
Running Time
Empirical Analysis
Theoretical Analysis
Pseudocode
The Abstract RAM Model
Primitive Operations
Counting Primitive Operations
Estimating Running Times
Big-Oh
Big-Oh Notation
Big-Oh and Rate of Growth
Big-Oh Rules
Asymptotic Analysis of Algorithms
Example: Computing Prefix Averages
Example: Binary Search
Math Needed for Complexity Analysis
Relatives of Big-Oh
Complexity Analysis: Arrays vs. Linked Lists
Static/Dynamic Sequences
Self-referential Structures
Iteration over Linked Lists
Modifying a Linked List
Comparison Array vs. Linked List
Complexity Classes
Complexity Classes
Generate and Test
Example: Subset Sum
Dynamic Data Structures
The Tao of Programming
Pointers
Pointers
Memory
Application: Input Using
scanf()
Pointers
Examples of Pointers
Pointers and Arrays
Pointer Arithmetic
Arrays of Strings
Pointers and Structures
C execution: Memory
Dynamic Data Structures
Dynamic Memory Allocation
Dynamic Data Example
The
malloc()
function
Memory Management
Memory Leaks
Sidetrack: Standard I/O Streams, Redirects
Linked Lists as Dynamic Data Structure
Sidetrack: Defining Structures
Self-referential Structures
Memory Storage for Linked Lists
Iteration over Linked Lists
Modifying a Linked List
Abstract Data Structures: ADTs
Abstract Data Types
Stack as ADT
Stack ADT Implementation
Common Mistakes
Summary
Produced: 13 Jan 2025
![[index]](icon/up.gif){kind=icon}