Skip to main content
Welcome to CS
Contents
Index
Search Book
close
Search Results:
No results.
Prev
Up
Next
Scratch ActiveCode
Profile
Course Home
Assignments
Practice
Peer Instruction (Instructor)
Peer Instruction (Student)
Change Course
Instructor's Page
Progress Page
Edit Profile
Change Password
Log Out
\( \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)
I
Computation and Computers
1
Computing Related Fields
1.1
Computer Engineering
1.1.1
Typical careers
1.1.2
Education
1.1.3
Knowledge Domains
1.2
Computer Science
1.2.1
Typical careers
1.2.2
Education
1.2.3
Knowledge Domains
1.3
Software Engineering
1.3.1
Typical careers
1.3.2
Education
1.3.3
Knowledge Domains
1.4
Information Systems
1.4.1
Typical careers
1.4.2
Education
1.4.3
Knowledge Domains
1.5
Information Technology
1.5.1
Typical careers
1.5.2
Education
1.5.3
Knowledge Domains
1.6
Cybersecurity
1.6.1
Typical careers
1.6.2
Education
1.6.3
Knowledge Domains
1.7
Data Science
1.7.1
Typical careers
1.7.2
Education
2
History of Computers
2.1
Prehistory
2.2
Dawn of Computers
2.3
The First Generation
2.3.1
The Stored Program Computer
2.4
The Second Generation
2.5
The Third Generation
2.6
The Fourth Generation
2.7
Modern Computers
3
Binary and Bits
3.1
Analog and Digital
3.2
Analog To Digital
3.3
Binary and Its Advantages
3.4
Bits
3.5
Bit Patterns
3.6
Bytes
3.6.1
Powers of 2 vs 10
4
Data Representation
4.1
Number Systems & Binary
4.2
Binary Conversions - Table Method
4.2.1
Binary to Decimal
4.2.2
Decimal to Binary
4.3
Binary Conversions - Multiplication/Division Method
4.3.1
Decimal to Binary
4.3.2
Binary to Decimal
4.4
Binary Addition
4.4.1
Overflow
4.5
Other Operations
4.6
Negative Values - Two’s Complement
4.6.1
Advantages of Two’s Complement
4.6.2
Overflow & Two’s Complement
4.7
Fractional Values
4.7.1
Limits of Fractional Representation
4.8
Floating Point Numbers
4.9
Representing Letters with ASCII
4.10
Representing Images
4.11
Hexadecimal
4.11.1
Hexadecimal Conversion To and From Binary
4.11.2
Why Hexadecimal?
4.12
Hex Data & Colors
5
Logic Gates & Circuits
5.1
The OR Gate
5.2
The AND Gate
5.3
Applying Logic Rules
5.4
XOR and NOT Gates
5.4.1
XOR Gates
5.4.2
NOT Gates
5.5
Circuits
5.6
Complex Circuits
5.7
Remembering Things
5.8
Adding Numbers with Logic
5.9
Circuit Playground
6
Computer Architecture & The Machine Cycle
6.1
Computer Components
6.2
The Processor
6.3
The Processor, cont.
6.3.1
The ALU
6.3.2
The Control Unit
6.3.2.1
The Decoder
6.3.2.2
The Clock (or Timer)
6.3.3
The Registers
6.3.3.1
Instruction Register (IR)
6.3.3.2
Program Counter (PC)
6.3.3.3
General Purpose Registers
6.4
Main Memory
6.5
Memory Hierarchy
6.5.1
Registers
6.5.2
Cache
6.5.3
RAM - Main Memory (Physical Memory)
6.5.4
Secondary Memory
6.6
The Machine Cycle
7
Programming Languages
7.1
Machine Languages
7.2
The Little Computer
7.3
The Little Computer - Branching
7.3.1
Decisions
7.3.2
Looping
7.4
Assembly Languages
7.5
The Little Computer - Assembly
7.6
High Level Programming Languages
7.7
Variety and Syntax
8
Algorithms
8.1
Algorithms Introduction
8.1.1
Algorithm Requirements
8.2
Linear Search
8.3
Binary Search
8.4
Sorting
8.5
Selection Sort
8.6
Selection Sort Code
8.7
Insertion Sort
8.8
Insertion Sort Code
8.9
Algorithm Efficiency
8.10
Big-O
8.11
Efficiency Testing
8.12
Search Efficiencies
8.12.1
Linear Search Efficency
8.12.2
Binary Search Efficency
8.12.3
Comparison
8.13
Sorting Efficiency
8.14
Estimating With Big-O
8.15
Merging
8.16
Merge Sort
8.17
Merge Sort Efficiency
8.18
Merge Sort Compared
9
Operating Systems
9.1
Operating System Varieties
9.2
Operating Systems Goals
9.2.1
Hardware Allocation
9.2.2
Hardware Abstraction
9.2.3
Common Interface
9.3
Process Management
9.4
Memory Management
10
Parallel Processing
10.1
Moore’s Law
10.2
Multi Processing
10.3
Parallel vs Serial Performance
10.4
Synchronization
10.4.1
Locks and Deadlock
11
Limits and Future of Computing
11.1
Computability
11.2
End of Moore’s Law?
11.3
Quantum Computing
12
Impacts of Computing
12.1
Blown To Bits
12.2
Analyzing Impacts
12.2.1
Choosing a Technology
12.2.2
Questions
12.3
Example: Smart Locks
12.4
Example: Street Maps
II
Programming
13
An introduction to programming
13.1
About This Section of the Book
13.1.1
Philosophy
13.1.2
License
13.2
Compute with Numbers
13.3
Compute with Words
13.4
Compute with Turtles
13.5
Compute with Images
13.6
Chapter Summary
14
Names for Numbers
14.1
Assigning a Name
14.2
Rules for Names
14.2.1
Naming Syntax
14.2.2
Naming Convention
14.3
Expressions
14.3.1
Operations
14.3.2
Division and Integer Division
14.3.3
Modulo
14.4
Summary of Expression Types
14.5
How Expressions are Evaluated
14.6
Driving from Chicago to Dallas
14.7
Following the Ketchup Ooze
14.8
Walking through Assignment more Generally
14.9
Figuring out an Invoice
14.10
Math Library Functions
14.11
Chapter Summary
14.12
Mixed Up Code Practice
14.13
Chapter Exercises
15
Names for Strings
15.1
Assign a Name to a String
15.1.1
Concatenating (Appending) Strings
15.1.2
Inputting Strings
15.1.3
Concatenating Strings and Numbers
15.2
Strings are Objects
15.2.1
Getting Part of a String
15.2.2
Some Other String Functions
15.3
Strings are Immutable
15.4
Making a MadLib story
15.5
Chapter Summary
15.5.1
Summary of String Functions
15.6
Mixed Up Code Practice
15.7
Chapter Exercises
16
Names for Turtles
16.1
Turtles as Objects
16.1.1
What does a left turn of 90 mean?
16.2
Procedures and Functions
16.3
Errors in Programs
16.3.1
Debugging Programs
16.4
Turtle Procedures
16.5
Single and Multiple Turtles
16.6
Turtle Coordinates
16.7
Turtle Art
16.8
Chapter Summary
16.9
Mixed Up Code Practice
16.10
Chapter Exercises
17
Names for Procedures
17.1
Stand Alone Procedures and Functions
17.2
Defining Procedures - Why
17.3
Defining Procedures - How
17.4
Order and Indentation
17.4.1
Indentation
17.4.2
Indentation Rules
17.5
Parameters
17.6
Multiple Parameters
17.7
Practice - Write a Procedure
17.8
Chapter Summary
17.9
Chapter Exercises
18
Designing with Procedures
18.1
Procedures that Call Procedures
18.2
Program Design
18.2.1
Top-Down Design Example
18.3
Program Implementation - 1
18.3.1
Implementation Discussion
18.4
Program Implementation - 2
18.5
Program Implementation - 3
18.6
Program Implementation - 4
18.7
Program Implementation - Final
18.8
Chapter Summary
18.9
Chapter Exercises
19
Names for Functions
19.1
Functions and Composition
19.1.1
Function Composition
19.2
Defining Functions - How
19.3
Defining Functions - Why
19.4
Common Function Issues
19.4.1
Returning Ends a Function
19.4.2
Trying to Change a Parameter
19.5
Functions Calling Functions - 1
19.6
Functions Calling Functions - 2
19.7
Functions Calling Functions - 3
19.8
Chapter Summary
19.9
Chapter Exercises
20
Repeating Steps with Turtles
20.1
Repeating Steps & Range
20.1.1
Range
20.2
Using Repetition with Turtles
20.3
A Regular Polygon Recipe
20.4
Nesting Loops
20.4.1
Execution Limit & Run Amok Programs
20.4.2
Indirect Nesting
20.5
Using the Loop Variable
20.5.1
Range Recipes
20.5.2
Range Recipes With Turtles
20.6
More Turtle Repetition Practice
20.7
Chapter Summary
20.8
Chapter Exercises
21
Repeating Steps with Images
21.1
Understanding Image Representation
21.2
A Library of Images
21.3
Using Repetition with Images
21.4
A Pattern for Image Processing
21.5
Increasing and decreasing brightness
21.6
Thinking About Pixel Locations
21.7
Chapter Summary
21.8
Chapter Exercises
22
Repeating Steps with Numbers
22.1
Repeating Calculations
22.2
Introducing the While Loop
22.3
Booleans and Logical Expressions
22.4
While Loops - While vs Until
22.5
Counting with a While Loop
22.5.1
Loop Control Variable
22.6
Infinite Loops
22.7
The Accumulator Pattern
22.8
Debugging Loops
22.9
Chapter Summary
22.9.1
Summary of Python Keywords and Functions
22.10
Chapter Exercises
23
Making Decisions
23.1
Making Decisions
23.2
The if Statement
23.3
Functions that make Decisions
23.4
Using Multiple if statements
23.5
Using if and else
23.6
Using elif for more options
23.7
Using elif correctly
23.8
Chapter Summary
23.8.1
Summary of Python Keywords and Functions
23.9
Chapter Exercises
24
Decisions, Randomness, and Simulations
24.1
Simulations
24.2
Random Numbers
24.3
Using Random Numbers
24.4
Building a Simulation
24.5
Building a Simulation - 2
24.6
Turtles And Randomness
24.7
Random Walks
24.8
Chapter Summary
24.8.1
Summary of Python Keywords and Functions
24.9
Chapter Exercises
25
Decisions with Strings and Complex Conditions
25.1
Using Decisions with Strings
25.2
Comparing Strings
25.3
Complex Conditionals
25.4
And, Or, and Not
25.4.1
And
25.4.2
Or
25.4.3
Not
25.5
When to use And and Or
25.6
Complex Conditional Dangers
25.7
Testing parts of strings and length
25.8
Making a Chatbot
25.9
Chapter Summary
25.9.1
Summary of Python Keywords and Functions
25.10
Chapter Exercises
26
Using Decisions with Images
26.1
Using Decisions with Images
26.2
A Pixel Selection Function
26.3
Combining Pictures
26.4
Posterizing
26.5
Location Based Conditions
26.6
Location Based Conditions Continued
26.7
Chapter Exercises
27
Working with Lists
27.1
The Need for Lists
27.2
What is a List?
27.3
In and Not In
27.4
Working with Indexes
27.5
Adding and Removing Items
27.6
List Accumulation
27.7
Finding the Largest or Smallest Value
27.8
Rainfall Problem
27.8.1
Rainfall Step 1
27.8.2
Rainfall Step 2
27.8.3
Rainfall Step 3
27.8.4
Rainfall Finished
27.9
Chapter Concept Summary
27.9.1
Summary of Python Keywords and Functions
27.10
Chapter Exercises
28
Changing and Chopping up Lists
28.1
Iterating with Indexes
28.2
Iterating Parts of a List
28.3
Making a MadLib Story
28.4
Slicing a List
28.5
Shuffle A List
28.5.1
Shuffle By Cuts
28.5.2
Shuffle By Move To Back
28.6
Chapter Concept Summary
28.7
Chapter Exercises
29
Introduction to SQL
29.1
Introduction
29.2
Tables of Records
29.3
Selecting
29.4
Filtering
29.5
Filtering with Like
29.6
Sorting
29.6.1
LIMIT
29.6.2
Multiple Sorts
29.7
Chapter Summary
29.8
Chapter Exercises
30
SQL Grouping and Joining
30.1
Aggregating Data
30.1.1
Counting Unique Values
30.2
Grouping
30.3
Filtering with Aggregated Results
30.4
Joining
30.5
Chapter Summary
30.6
Chapter Exercises
31
Working with Data in Python
31.1
Data and Python
31.2
Our first data set: Air pollution in the United States
31.3
Reading the data
31.4
What’s the largest pollution values?
31.5
What’s the average pollution?
31.6
Most Populated and Least Populated States
31.7
Finding the Pollution for a State
31.8
Comparing States
31.9
Chapter Concept Summary
31.9.1
Summary of Python Keywords and Functions
31.10
Chapter Exercises
32
What’s Next?
32.1
Extending Your Programming Skills
32.1.1
Full Python On The Web
32.1.2
Python On Your Computer
32.1.3
More Python
32.1.4
Applications
Back Matter
Index
Chapter
2
History of Computers
There is no one person who can claim to be the inventor of the computer - many people contributed to the development of the modern computer:
2.1
Prehistory
2.2
Dawn of Computers
2.3
The First Generation
2.4
The Second Generation
2.5
The Third Generation
2.6
The Fourth Generation
2.7
Modern Computers
