# 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
- 2014-07-29: Basic Counting; Turtle Graphics
- 2014-07-30: Low-Level Computer Operation 1 —Warren Harrison
- 2014-07-31: Low-Level Computer Operation 2 —Warren Harrison

## 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*itemsSince 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 rearrangedFor starters, imagine that just one element

*e*occurs*r*times, with all other elements uniqueNow 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)*timesThus, 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 pigeonBook 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*n*^{n}

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