Software Engineering Principles

New Beginnings: Week 5
Lecture Notes by Bart Massey
Copyright © 2014 Bart Massey

2014-07-28: Parts of a Computer; GUI Building

Parts of a Computer

  • Let's take apart a computer, and discuss how it works from that perspective

  • Identify:

    • Power Supply
    • Motherboard
      • CPU
      • Northbridge chipset
      • GPU
      • RAM
      • PCI bus
      • USB controller
      • Networking chipset
    • Drives
      • HDD
      • Optical Drive

Protocols and Standards

  • HDD formatting
  • Keyboard serial
  • Video prootocols
  • Network protocols

Installing Linux

  • Demo

The Standard WIMP GUI

  • Windows / Icons / Menus / Pointer

  • Normally implemented:

    • As an event stream system
    • With widget objects
    • By a toolkit used by app developers

Python and Tk

  • Toolkit borrowed from an ancient system called TCL / Tk; TCL is a string-based programming language

  • Pretty standard interaction:

    • Subclass a class that provides the application environment
    • Override methods to get your behavior for the app
    • In particular:
      • Create widget objects to represent the interface
      • Set up callbacks to connect the interface to your application
      • Install your widgets where the toolkit can find them

Layout

  • The graphical environments you will be running on vary:

    • Screen size, color resolution, keyboard layout, etc
  • One of the jobs of the toolkit is to insulate you from this as far as possible

  • But there is a tension between auto-layout of widgets on the screen, and having a most-usable layout

  • For Tk, the layout manager is the "packer"

Events and Callbacks

  • Drawing is easy; processing user commands is harder

  • For each user action, the toolkit creates an event object

  • Events are used to select callbacks into application code

  • Callbacks have access to the event object

Exercise: Build a die roller

Code Reading: Socrate

2014-07-29: Basic Counting; Turtle Graphics

How To Count Things

  • 1, 2, ...

  • Seriously, the count ("cardinality") is just the number of elements in a set or collection

  • With two collections, add the cardinalities

  • But subtract off the overlap if the collections overlap

Combinatorics: How To Count Made Things

  • The cardinality |E x F| = |E||F|

  • In general, synthetic objects like tuples are more...interesting to count

  • Example, count the number of possible complete sequences that can be made from a set S

Permutations and Factorial

  • Base Cases:

    • The number of complete sequences that can be made from the empty set is pretty clearly 1 (the empty sequence)

    • The number of complete sequences that can be made from a set containing 1 item is pretty clearly 1

  • Inductive Case:

    • To count the number P(n) of complete sequences that can be made from a set of n items:

      • First pick an element out to put on the front

      • Then append it to each of the P(n-1) sequences that can be made from the remaining n-1 items

      • Since there are n ways this can be done, P(n) = n P(n-1)

      • Expanding the recursion, we get P(n) = product(i=1..n, i)

      • We write this number as P(n) = n!

Exercise: Generate All Permutations

  • Write a function that returns the set of complete sequences that can be made from its set argument

  • HINT: Use the recursive formulation above

Permutations Of Sequences

  • Note that a sequence of n items may have repetition. Thus P(n) = n! overcounts the number of possible ways it can be rearranged

  • For starters, imagine that just one element e occurs r times, with all other elements unique

  • Now the overcount is calculable by the product rule: the permutations contain e in "every possible order", so we have overcounted by a factor of P(r)

  • Thus

          P(n; r) * P(r) = P(n)
          P(n; r) = n! / r!
    
  • The obvious generalization to more repeated elements holds

Ordered Sampling

  • Number N(n, k) of distinct sequences of length k that can be taken from a set S with n = |S|

  • With replacement: Select a first element one of n ways, then put it back. Repeat k times. By the product rule,

          Nr(n, k) = n^k
    
  • Without replacement: Select a first element one of n ways, then the second one of n-1 ways, etc. By the product rule,

          N(n, k) = product(i=n..n-k+1, i) = n! / (n-k)!
    

Combinations and Choice

  • Suppose we want to count the number C(n, k) of ways we can choose a set of k items from a set S where n = |S|

    • Note that everything's a set: order is irrelevant here
  • One way to think about it: imagine that we take all possible ordered samples with replacement from S; there are N(n, k) such. If we treat each such ordered sample as a set, it must appear in all possible orders: thus P(k) times

  • Thus, by the product rule:

          C(n, k) P(k) = N(n, k)
          C(n, k) = n! / (k! (n - k)!)
    

Pigeonhole Principle

  • If you have n pigeons and less than n "holes" (cages), and every pigeon is in a hole, then some hole must contain more than one pigeon

  • Book correctly calls this "almost obvious": Inductive proof on number of holes

    • Base Case: If I have two or more pigeons and one hole, they must all be in the same hole

    • Inductive Case: If I have n pigeons and k holes, with 1 < k < n, then place one pigeon in one hole. Now I have n - 1 pigeons in k - 1 holes and still have k < n. Thus, if the statement holds for (n - 1, k - 1), it holds for (n, k)

  • Note important book typo: "can occur" should be "must occur"

  • Example:

    • Probability of two people having the same birthday in a room of two people (neglecting leap years): 1/365
    • Probability of two people having the same birthday in a room of 365 people (neglecting leap years): 1

Stirling's Approximation

  • Way of accurately approximating n! as n gets large

          n! ~ sqrt(2πn) n^n e^-n
    
  • Note terrible book typo with n^π instead of nn

Examples: Poker Hands

  • Note that there are C(52, 5) = 2598960 possible poker hands

    • This is not a scary number because computers
  • Let's count the number of these hands that are

    • Four of a kind
    • Flush
    • Straight Flush

Turtle Graphics

  • Ancient graphics system designed for teaching computing, from LOGO programming language

  • Idea: Virtual "turtle" on the drawing plane leaves a line behind it when it moves

  • Turtle state: facing, pen up/down, pen width/color, fill status/color

Demos and Comments

2014-07-30: Low-Level Computing 1

2014-07-31: Low-Level Computing 2