# Introduction to CS; Sets; Python Programming

*New Beginnings:* Week 1

*Lecture Notes by Bart Massey*

Copyright © 2014 Bart Massey

- 2014-07-01: Introduction to CS; Some Basics
- 2014-07-02: More Set Stuff
- 2014-07-03: Python Programming

## 2014-07-01: Introduction to CS; Some Basics

### What is Computer Science?

Great question! There's a lot of argument about this one.

Plenty of debate about whether it's even a "science", with many folks weighing in against.

Plenty of debate about boundaries of the field.

For the purposes of this course, I will break the areas of study into three categories: Computing, Engineering and Mathematics.

### Computing

How computers work and do things. This is the "unique" content of CS. A particularly important subtopic is "Programming": how to make a computer do what is desired.

### Engineering

Computing is *not* just a kind of
engineering. There are aspects of art and literature,
and a peculiar relationship with mathematics.

- Engineering is the study of making things: gathering requirements, designing a solution, implementing the solution, and validating / verifying the result.

### Mathematics

It is a common misconception that mathematics is "just advanced arithmetic". The essence of mathematics is abstract reasoning: thinking about formal relationships between imaginary entities.

- We will work a lot at a boundary of Mathematics known as Mathematical Modeling. A mathematical model describes some situation in symbolic form. Mathematical models can be formally manipulated to draw conclusions about the situation they describe.

### What Are We Going To Learn?

In brief: what we need to learn for the PSU CS MS program. Material not contingent will be ruthlessly eliminated.

However, this still includes a bunch of "non-CS" stuff, e.g.

- Basic physical and mental skills
- Linux programming environment
- How to write a CS paper

### What Is A Computer?

- It's a machine (EE, bio, whatever)
- It "processes information" (turning power into heat)
- Parts of a computer
- It has "storage" (teeny tiny switches)
- It has a "CPU" (teeny tiny "logic" circuits)
- It has "I/O" (more electricity and stuff)
- It is the most complex thing humans can build

- Modular architecture
- Layered architecture
- It is mostly deterministic (= repeatable)

### How Do I Program A Computer?

Is programming a science, engineering, an art, a craft, math, other?

What's the programming "process"? (same as any making)

- Figure out what you want
- Figure out how to make it
- Make it
- Figure out whether its the right thing made right

The more tools / techniques / practices you have access to, the easier it is

### Who Do I Program With?

- Alone
- With folks online
- With folks in a room

### What's Hard About Programming?

- Lots of thinking per unit typing
- Easy to make mistakes
- Hard to estimate how fast programming will go

### What's Fun About Programming?

- Build really useful stuff
- Learn a ton as you work (about more than just computers)
- Makes for great career options
- Comes with a community (work in cross-disciplinary teams)
- Fairly "idiot-proof"

### Environmental Ergonomics

- Adequate lighting, but not too bright
- Reasonably quiet space
- Music
*only if it doesn't distract you* - Space to spread stuff around (there is always stuff)
- Temperature in narrow comfort range (70-74F)

### Physical Ergonomics

- Chair height so that knees are level with hips
- Back adequately supported, vertical
- Desk height so that elbows are level with wrists
- Low keyboard
- Monitor centered on eyes, 1-1.5' away
- Adequate monitor / font size

### Linux

- Default environment around academia
- Command-line interface
- Neal Stephenson,
*In The Beginning Was The Command Line*

- Neal Stephenson,
- Programmer's text editor:
`vi`

or`emacs`

- I will teach
`vi`

for this course, but - I use
`emacs`

normally

- I will teach
- IDE, e.g. Python IDLE
- Programming tools
- Scripting

### Mental Ergonomics

- Adequate sleep!!
- Adequate food!
- At peace
- Flow state vs exploration state
- Try setting a 15-minute timer

### Puzzle-solving Mode

Be OK with being

- Confused
- Frustrated

Don't get stuck!

- Take breaks!
- Change strategies
- Ask another human to help
- Doesn't have to be an expert

- Consult references (notably the Internet)

### Exercise: MIU System

From Douglas Hofstadter: *Godel, Escher, Bach: An Eternal
Golden Braid*:

- Start with MI
- Rules (Wikipedia):
- Add a U to the end of any string ending in I. For example: MI to MIU.
- Double the string after the M (that is, change Mx, to Mxx). For example: MIU to MIUIU.
- Replace any III with a U. For example: MUIIIU to MUUU.
- Remove any UU. For example: MUUU to MU.

- Goal: Make MU

### Mathematical Modeling

- Something that you want to understand?
- Translate it into symbols in a formal system
- Manipulate the formal system using its rules
- Translate back into the system you want to understand

### Formal System: Sets

- A set is a collection of items
- Items can be anything

- A set is an unordered collection
- A set has no duplicate elements
- Platonic ideals of things
- Convenient in a surprising number of places
- Can use "property functions" to deal with duplication

- May be "typed": All elements of the set are the same "kind"

### The Sets We Will Care Most About

- Booleans
- Numbers
- Integers
- "Natural Numbers"
- Small Integers

- Rational Numbers
- Real Numbers
- Floating Point Numbers

- Integers
- Characters
- Sequences: e.g. Strings

### Finite and Infinite Sets

- Sets can be divided into three kinds
- Finite: Can list all of the elements
- Infinite: There are more elements than can be listed
- Countably vs uncountably infinite: more later

### Sequences and Tuples

- Sometimes convenient to work with ordered collections
- Potentially with duplicates

- Can define tuples and sequence using sets
- Tuple "arity": Number of elements in the tuple
- "Cartesian Product": Set of all tuples with elements drawn from underlying sets

### Relations

- Can think of any tuple as "relating" its elements
- A relation is a set of tuples (of the same arity)
- Something is "in the relation" if its tuple is in the set

### Programming

A "programming language" is just a set of tools for manipulating the kind of entities we've been talking about automatically.

- Representations:
- Of mathematical symbols
- Of rules for manipulating symbols

A "program" is just rules for manipulating symbols. Given a starting point (like MI in the MIU system) as "input", it performs manipulations until it produces an output.

- The MIU system is not a program, because

### Python and the Standard Symbols

Python is a programming language.

- Values
- Expressions
- "Storing" a value
- Expressing simple rules

## 2014-07-02: More Set Stuff

### Review: Set Basics

Set is an unordered collection of non-repeated elements

Some sets are typed

Fundamental types: Booleans, Numbers, Integers, Rationals, Real Numbers, Floating Point Numbers, Characters

Fun Fact: The

*cardinality*of a set is its number of elements- We write |S| for the cardinality of a set S

### Review: Relations

Relation is a set of typed tuples indicating which things are "in" the relation

- e.g. "less than"

Especially important:

- Unary relations
- Binary relations

### Functions As Relations

A function is a binary relation with each of its left-hand-sides unique

- The set of LHS is the
*domain*of the function - The set of RHS is the
*range*of the function

- The set of LHS is the
Function

*application*is sometimes noted with- parens:
*f(3)* - simple adjacency:
*f 3*

- parens:
There will be other definitions of function

### Why Functions Are Important

Functions turn out to be sufficient by themselves to express almost anything

Functions provide a convenient notation for describing properties of things

### Special Kinds Of Functions

Injective: Every element of the domain maps to a unique element of the range ("1:1")

Surjective: Every element of the range is mapped from a unique element of the domain ("onto")

Bijective: Both injective and surjective

### Operators As Functions

- Operators are a special kind of function notation.
Think of a binary operator as:
- A function from two-tuples of operands to value
- A function from an operand to (functions from an operand to a value): "currying"

### Function Types

We use

*→*to denote function types: A function with domain*D*and range*R*is written*D→R*So the function arrow is kind of like the Cartesian Product operator, but more restrictive

### More About Sequences

Can think of a sequence as a function from

*N*position to valueSequence has a length:

- Length is the cardinality of its relation

### Modeling Complex Structure

Enough machinery to start modeling things

e.g. cards

- Cards: underlying set
*C*of 52 things- Can give symbolic names to the things, e.g.
*tc*

- Can give symbolic names to the things, e.g.
- Suits: set
*S*of four suits, e.g. "c" - Rank: Function from
*C*to a set*R*of 13 ranks- Ranks are integers? Or just symbolic?

- Rank ordering:
*<*relation*R x R*- "High-Low" aces?

- Stack of cards: injective sequence with range
*C*- Deck is largest such sequence

- Cards: underlying set

### Exercise: Model Oregon License Plates

### Power Set

- The Power Set
*P(S)*is the set of all sets with elements drawn from*S*- The empty set is always an element of
*P(S)* - When
*S*is finite, the cardinality*|P(S)|*is*2^|S|* - There's an easy way to see this

- The empty set is always an element of

### Set Complement and the Universe

Imagine that a set

*S*is drawn from some*universe**U*Then can define a unary relation

*-S*as a function returning the set of elements of*U*that are not in*S*

### Set Membership

We write

*e ∊ S*to indicate that element*e*is within set*S*This is a binary relation

*U x P(U) → B*

### Set Union and Intersection

Interesting relations:

- Intersection
*A ∩ B*is the set of all elements that are in both*A*and*B* - Union
*A ∪ B*is the set of all elements that are either in*A*or in*B*or both

- Intersection
Union and intersection are binary operators:

*P(A) x P(B) → P(A ∪ B)*- Yes, irony

### Properties of Set Union and Intersection

Set union and intersection are

*Commutative: A ∩ B = B ∩ A**Associative: (A ∩ B) ∩ C = A ∩ (B ∩ C)**Distributive: A ∩ (B ∩ C) = (A ∩ B) ∩ (A ∩ C)*

Mix and match union and intersection?

### Set Difference

Set difference

*A \ B*is the set of all elements that are in*A*but not*B*Think of it as

*A ∩ -B*

### Subset and Proper Subset

Can

*partial order*sets by the subset relation*A ⊆ B*if every element of*A*is contained in*B**Iff**A ∩ B = A*

*A ⊂ B*if*A ⊆ B*and*A ≠ B*More Boolean binary operators

### Boolean Algebra

Study of the set

*B = {t, f}*and expressions using it- Named after George Boole from the mid-1800s

Pretty strong dual of set theory

### Primitive Boolean Operators

¬x : Boolean negation

`x | ¬x ------ f | t t | f`

x⋀y : Boolean and (conjunction)

`x y | x⋀y ------ f f | f f t | f t f | f t t | t`

x⋁y : Boolean or (disjunction)

`x y | x⋁y ------ f f | f f t | t t f | t t t | t`

### Exclusive Or

x⊕y : Boolean exclusive or (xor)

`x y | x⊕y ------ f f | f f t | t t f | t t t | f`

### Properties of Boolean Operators

Commutative, associative

Also commute and associate with each other

Rule for multiple ⊕ : an odd number of

*t*is true, otherwise*f*

### Misc

Can construct ⊕ From Primitives

- x⊕y = (x⋁y)⋀¬(x⋀y)

Boolean Circuits: Fundamental building blocks of computers

- Essentially another way to write Boolean expressions

Boolean expressions pervade programming: e.g. conditional and looping tests

## 2014-07-03: Python Programming

### Review: Python Values and Expressions

Values are our old friends the elements of the standard sets

Expressions use binary operators from sets to sets

### "Calling Builtin Functions"

Lots of functions provided in Python

- Mathematical functions like
`floor`

- Functions for concepts like
`len`

- Conversion functions like
`str`

- Mathematical functions like
Soon we'll learn to build our own functions

### More About Variables

A variable is a name for a storage location ("an address")

A storage location holds a value

When the variable is

*evaluated*, it evaluates to whatever value is*currently*in its storage location

### A Bestiary Of Operators

Arithmetic operators + - * / // ** ^ -

Relational operators < > >= <= == !=

Boolean operators and or not

- e.g. 3 < 4 and not (5 < 4) == True

Can kind of think of list brackets, tupling symbols etc as operators

### Statements

A single line of Python is called a

*statement*So far, we have seen expressions used as statements, and variable assignment statements

There's lots of other kinds, to come soon

### Beyond Calculator Mode

The whole point of a "stored program" computer is to be able to reuse computations with different inputs

- This is the difference between a computer and a calculator

We will save a sequence of statements in a file: we call this a "program*

Python can load up and

*run*the program by just evaluating each expression in turn

### Input

Pointless to reproduce the same computation over and over

Need

*input*from "the external world"Easiest way in Python:

`input`

"function"`input`

always returns a string, so be careful

### Output

Evaluating expressions to output them doesn't work out so well

Python way:

`print`

"function"`print`

can take all kinds of arguments, but usually you want to just pass it a string

### Structure Of Simple Programs

Generally, a simple program:

- Starts with an input section
- Continues with a section that performs the computation
- Ends with an output section

This organization makes the program easier to read and modify

### Programs As State Transitions

A useful concept from CS: think of taking a snapshot of memory after executing every statement in the program

- This is the "trace" of the program

Our job as programmers is to create a trace that goes from some interesting initial state---the problem---to some interesting final state---the solution

Of course, IO complicates the picture

### Exercise: Celsius To Fahrenheit

### Altering "Flow Of Control"

So far the "flow of control" through our program has been simple: each statement is executed in turn, top to bottom

- Think of the program as a sequence of statements

This is less than totally useful (without a lot of magic we don't know yet)

We now learn some ways to

- Skip executing statements based on state ("conditionals")
- Repeatedly execute statements based on state ("looping")

### Conditional Statements

```
if <condition>:
<statements>
if <condition>:
<statements>
else:
<statements>
if <condition>:
<statements>
elif <condition>:
<statements>
else:
<statements>
```

The condition is a boolean-valued expression that almost always contains one or more variables

Note that indentation plays a crucial role here

### Exercise: C To F or F To C

### While Loops

```
while <condition>:
<statements>
```

Note that the statements may be executed zero times

Also may be executed forever (usually bad)