# Introduction to CS; Sets; Python Programming

New Beginnings: Week 1
Lecture Notes by Bart Massey

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

### What is Computer Science?

• 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

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

• 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
• Desk height so that elbows are level with wrists
• Low keyboard
• Monitor centered on eyes, 1-1.5' away
• Adequate monitor / font size

### Linux

• Command-line interface
• Neal Stephenson, In The Beginning Was The Command Line
• Programmer's text editor: `vi` or `emacs`
• I will teach `vi` for this course, but
• I use `emacs` normally
• IDE, e.g. Python IDLE
• Programming tools
• Scripting

### Mental Ergonomics

• 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:

• 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
• 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
• Function application is sometimes noted with

• parens: f(3)
• 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

• Can think of a sequence as a function from N position to value

• Sequence 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
• 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

### 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

### 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
• 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`
• Soon we'll learn to build our own functions

• 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

### 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

### While Loops

``````    while <condition>:
<statements>
``````
• Note that the statements may be executed zero times

• Also may be executed forever (usually bad)