https://dcic-world.org/2021-08-21/index.html
V A Data-Centric Introduction to Computing
I Introduction
II Foundations
III Algorithms
IV Programming with State
V Advanced Topics
VI Appendices
On this page:
A Data-Centric Introduction to Computing
Sunday, August 22nd, 2021 2:04:44pm
- prev up next -
A Data-Centric Introduction to Computing
Kathi Fisler, Shriram Krishnamurthi, Benjamin S. Lerner, Joe Gibbs
Politz,
I Introduction
1 Overview
1.1 What This Book is About
1.2 The Values That Drive This Book
1.3 Our Perspective on Data
1.4 What Makes This Book Unique
1.5 Who This Book is For
1.6 The Structure of This Book
1.7 Organization of the Material
1.8 Our Programming Language Choice
2 Acknowledgments
II Foundations
3 Getting Started
3.1 Motivating Example: Flags
3.2 Numbers
3.3 Expressions
3.4 Terminology
3.5 Strings
3.6 Images
3.6.1 Combining Images
3.6.2 Making a Flag
3.7 Stepping Back: Types, Errors, and Documentation
3.7.1 Types and Contracts
3.7.2 Format and Notation Errors
3.7.3 Finding Other Functions: Documentation
4 Naming Values
4.1 The Definitions Window
4.2 Naming Values
4.2.1 Names Versus Strings
4.2.2 Expressions versus Statements
4.3 The Program Directory
4.3.1 Understanding the Run Button
4.4 Using Names to Streamline Building Images
5 From Repeated Expressions to Functions
5.1 Example: Similar Flags
5.2 Defining Functions
5.2.1 How Functions Evaluate
5.2.2 Type Annotations
5.2.3 Documentation
5.3 Functions Practice: Moon Weight
5.4 Documenting Functions with Examples
5.5 Functions Practice: Cost of pens
5.6 Recap: Defining Functions
6 Conditionals and Booleans
6.1 Motivating Example: Shipping Costs
6.2 Conditionals: Computations with Decisions
6.3 Booleans
6.3.1 Other Boolean Operations
6.3.2 Combining Booleans
6.4 Asking Multiple Questions
6.5 Evaluating by Reducing Expressions
6.6 Composing Functions
6.6.1 How Function Compositions Evaluate
6.6.2 Function Composition and the Directory
6.7 Nested Conditionals
6.8 Recap: Booleans and Conditionals
7 Introduction to Tabular Data
7.1 Creating Tabular Data
7.2 Extracting Rows and Cell Values
7.3 Functions over Rows
7.4 Processing Rows
7.4.1 Finding Rows
7.4.2 Ordering Rows
7.4.3 Adding New Columns
7.4.4 Calculating New Column Values
7.5 Examples for Table-Producing Functions
8 Processing Tables
8.1 Cleaning Data Tables
8.1.1 Loading Data Tables
8.1.2 Dealing with Missing Entries
8.1.3 Normalizing Data
8.1.4 Normalization, Systematically
8.1.4.1 Using Programs to Detect Data Errors
8.2 Task Plans
8.3 Preparing Data Tables
8.3.1 Creating bins
8.3.2 Splitting Columns
8.4 Managing and Naming Data Tables
8.5 Visualizations and Plots
8.6 Summary: Managing a Data Analysis
9 From Tables to Lists
9.1 Basic Statistical Questions
9.2 Extracting a Column from a Table
9.3 Understanding Lists
9.3.1 Lists as Anonymous Data
9.3.2 Creating Literal Lists
9.4 Operating on Lists
9.4.1 Built-In Operations on Lists of Numbers
9.4.2 Built-In Operations on Lists in General
9.4.3 An Aside on Naming Conventions
9.4.4 Getting Elements By Position
9.4.5 Transforming Lists
9.4.6 Recap: Summary of List Operations
9.5 Lambda: Anonymous Functions
9.6 Combining Lists and Tables
10 Processing Lists
10.1 Making Lists and Taking Them Apart
10.2 Some Example Exercises
10.3 Structural Problems with Scalar Answers
10.3.1 my-len: Examples
10.3.2 my-sum: Examples
10.3.3 From Examples to Code
10.4 Structural Problems that Transform Lists
10.4.1 my-doubles: Examples and Code
10.4.2 my-str-len: Examples and Code
10.5 Structural Problems that Select from Lists
10.5.1 my-pos-nums: Examples and Code
10.5.2 my-alternating: Examples and Code
10.6 Structural Problems with Sub-Domains
10.6.1 my-max: Examples
10.6.2 my-max: From Examples to Code
10.7 More Structural Problems with Scalar Answers
10.7.1 my-avg: Examples
10.8 Structural Problems with Accumulators
10.8.1 my-running-sum: First Attempt
10.8.2 my-running-sum: Examples and Code
10.8.3 my-alternating: Examples and Code
10.9 Dealing with Multiple Answers
10.9.1 uniq: Problem Setup
10.9.2 uniq: Examples
10.9.3 uniq: Code
10.9.4 uniq: Reducing Computation
10.9.5 uniq: Example and Code Variations
10.9.6 uniq: Why Produce a List?
10.10 Monomorphic Lists and Polymorphic Types
11 Introduction to Structured Data
11.1 Understanding the Kinds of Compound Data
11.1.1 A First Peek at Structured Data
11.1.2 A First Peek at Conditional Data
11.2 Defining and Creating Structured and Conditional Data
11.2.1 Defining and Creating Structured Data
11.2.2 Annotations for Structured Data
11.2.3 Defining and Creating Conditional Data
11.3 Programming with Structured and Conditional Data
11.3.1 Extracting Fields from Structured Data
11.3.2 Telling Apart Variants of Conditional Data
11.3.3 Processing Fields of Variants
12 Collections of Structured Data
12.1 Lists as Collective Data
12.2 Sets as Collective Data
12.2.1 Picking Elements from Sets
12.2.2 Computing with Sets
12.3 Combining Structured and Collective Data
12.4 Data Design Problem: Representing Quizzes
13 Recursive Data
13.1 Functions to Process Recursive Data
13.2 A Template for Processing Recursive Data
14 Trees
14.1 Data Design Problem - Ancestry Data
14.1.1 Computing Genetic Parents from an Ancestry Table
14.1.2 Computing Grandparents from an Ancestry Table
14.1.3 Creating a Datatype for Ancestor Trees
14.2 Programs to Process Ancestor Trees
14.3 Summarizing How to Approach Tree Problems
14.4 Study Questions
15 Interactive Games as Reactive Systems
15.1 About Reactive Animations
15.2 Preliminaries
15.3 Version: Airplane Moving Across the Screen
15.3.1 Updating the World State
15.3.2 Displaying the World State
15.3.3 Observing Time (and Combining the Pieces)
15.4 Version: Wrapping Around
15.5 Version: Descending
15.5.1 Moving the Airplane
15.5.2 Drawing the Scene
15.5.3 Finishing Touches
15.6 Version: Responding to Keystrokes
15.7 Version: Landing
15.8 Version: A Fixed Balloon
15.9 Version: Keep Your Eye on the Tank
15.10 Version: The Balloon Moves, Too
15.11 Version: One, Two, ..., Ninety-Nine Luftballons!
16 Examples, Testing, and Program Checking
16.1 From Examples to Tests
16.2 More Refined Comparisons
16.3 When Tests Fail
16.4 Oracles for Testing
III Algorithms
17 Functions as Data
17.1 A Little Calculus
17.2 A Helpful Shorthand for Anonymous Functions
17.3 Streams From Functions
17.4 Combining Forces: Streams of Derivatives
18 Predicting Growth
18.1 A Little (True) Story
18.2 The Analytical Idea
18.3 A Cost Model for Pyret Running Time
18.4 The Size of the Input
18.5 The Tabular Method for Singly-Structurally-Recursive
Functions
18.6 Creating Recurrences
18.7 A Notation for Functions
18.8 Comparing Functions
18.9 Combining Big-Oh Without Woe
18.10 Solving Recurrences
19 Sets Appeal
19.1 Representing Sets by Lists
19.1.1 Representation Choices
19.1.2 Time Complexity
19.1.3 Choosing Between Representations
19.1.4 Other Operations
19.2 Making Sets Grow on Trees
19.2.1 Converting Values to Ordered Values
19.2.2 Using Binary Trees
19.2.3 A Fine Balance: Tree Surgery
19.2.3.1 Left-Left Case
19.2.3.2 Left-Right Case
19.2.3.3 Any Other Cases?
20 Halloween Analysis
20.1 A First Example
20.2 The New Form of Analysis
20.3 An Example: Queues from Lists
20.3.1 List Representations
20.3.2 A First Analysis
20.3.3 More Liberal Sequences of Operations
20.3.4 A Second Analysis
20.3.5 Amortization Versus Individual Operations
20.4 Reading More
21 Sharing and Equality
21.1 Re-Examining Equality
21.2 The Cost of Evaluating References
21.3 On the Internet, Nobody Knows You're a DAG
21.4 From Acyclicity to Cycles
22 Graphs
22.1 Understanding Graphs
22.2 Representations
22.2.1 Links by Name
22.2.2 Links by Indices
22.2.3 A List of Edges
22.2.4 Abstracting Representations
22.3 Measuring Complexity for Graphs
22.4 Reachability
22.4.1 Simple Recursion
22.4.2 Cleaning up the Loop
22.4.3 Traversal with Memory
22.4.4 A Better Interface
22.5 Depth- and Breadth-First Traversals
22.6 Graphs With Weighted Edges
22.7 Shortest (or Lightest) Paths
22.8 Moravian Spanning Trees
22.8.1 The Problem
22.8.2 A Greedy Solution
22.8.3 Another Greedy Solution
22.8.4 A Third Solution
22.8.5 Checking Component Connectedness
IV Programming with State
23 From Pyret to Python
23.1 Expessions, Functions, and Types
23.2 Returning Values from Functions
23.3 Examples and Test Cases
23.4 An Aside on Numbers
23.5 Conditionals
23.6 Creating and Processing Lists
23.6.1 Filters, Maps, and Friends
23.7 Data with Components
23.7.1 Accessing Fields within Dataclasses
23.8 Traversing Lists
23.8.1 Introducing For Loops
23.8.1.1 An Aside on Order of Processing List Elements
23.8.2 Using For Loops in Functions that Produce Lists
23.8.3 Summary: The List-Processing Template for Python
24 Modifying Variables
24.1 Modifying Variables in Memory
24.2 Modifying Variables Associated with Lists
24.3 Writing Functions that Modify Variables
24.3.1 The global annotation
24.4 Testing Functions that Modify global Variables
24.4.1 The Internal Structure of a Test Function
24.4.2 Takeaways on Testing Modifications
25 Modifying Structured Data
25.1 Modifying Fields of Structured Data
25.2 Modifications to Shared Data
25.3 Understanding Memory
25.4 Modifications to Structured Data, Revisited
25.5 Basic Data in Memory
25.6 Variables and Equality
25.7 Takeaways on Modifying Variables
26 Revisiting Lists and Variables
26.1 Sharing List Updates
26.1.1 Operations that Mutate Lists
26.2 Lists in Memory
26.3 Practice: Data for Shared Bank Accounts
26.4 Circular References
26.4.1 Testing Circular Data
26.4.2 Revisiting Variables: A Function to Create Accounts
for New Customers
26.5 The Many Roles of Variables
26.6 Managing All Accounts
27 Hashtables and Dictionaries
27.1 Searching by Criteria Other than Keys
27.2 Dictionaries with More Complex Values
27.3 Using Structured Data as Keys
V Advanced Topics
28 Algorithms That Exploit State
28.1 Disjoint Sets Redux
28.1.1 Optimizations
28.1.2 Analysis
28.2 Set Membership by Hashing Redux
28.2.1 Improving Access Time
28.2.2 Better Hashing
28.2.3 Bloom Filters
28.3 Avoiding Recomputation by Remembering Answers
28.3.1 An Interesting Numeric Sequence
28.3.1.1 Using State to Remember Past Answers
28.3.1.2 From a Tree of Computation to a DAG
28.3.1.3 The Complexity of Numbers
28.3.1.4 Abstracting Memoization
28.3.2 Edit-Distance for Spelling Correction
28.3.3 Nature as a Fat-Fingered Typist
28.3.4 Dynamic Programming
28.3.4.1 Catalan Numbers with Dynamic Programming
28.3.4.2 Levenshtein Distance and Dynamic Programming
28.3.5 Contrasting Memoization and Dynamic Programming
VI Appendices
29 Pyret for Racketeers and Schemers
29.1 Numbers, Strings, and Booleans
29.2 Infix Expressions
29.3 Function Definition and Application
29.4 Tests
29.5 Variable Names
29.6 Data Definitions
29.7 Conditionals
29.8 Lists
29.9 First-Class Functions
29.10 Annotations
29.11 What Else?
30 Pyret vs. Python
31 Glossary
- prev up next -