Week 02
Efficiency
Program Properties
Program/Algorithm Efficiency
Algorithmic Complexity
Ex1: Assigning Complexity Class
Abstract Data Types
Abstract Data Types
DTs, ADOs, ADTs, GADTs
Interface/Implementation
Collections
Example ADT: Sets of Integers
Set ADT
Ex2: pre- and post-conditions
Set Applications
Ex3: Set Lab
Ex4: Set ADT Pre/Post-conditions
Sets as Unsorted Arrays
Sets as Sorted Arrays
Sets as Linked Lists
Sets as Hash Tables
Hash Table Costs
Sets as Bit-strings
Ex5: Implement Bit operations
Ex6: Implement Union via Bit Strings
Setting and unsetting bits
Performance of Set Implementations
Produced: 24 Jul 2017