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

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

  • 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
  • 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)
    • simple adjacency: 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

More About Sequences

  • 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

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

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

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)

Exercise: Input A Sequence Of Strings