NEW


NOTES


TO DO


Abstraction


Algorithms


Pattern Recognition


Decomposition

Layers |

Foreword

Basic Course Concepts

The goal of this course is to equip the student with certain styles and habits of thought as a set of skills AND to provide a sense of how much one knows and how much one would need to know of what in order to proceed further in various areas related to computational work.

  1. Reprise abstraction | decomposition | pattern recognition | algorithm multiple times throughout the course at different scales (sometimes concentrating an entire class on one of these, sometimes all four illustrated or practiced in a single example or activity). Perhaps only formally present them at the end of the course.
  2. I hear and I forget; I see and I remember; I do and I understand.
  3. Ever class session follows same ritual of review, motivate, introduce, practice, project
  4. There will be an explicit inventory of skills and concepts
  5. At every stage examples and applications from many fields
  6. Course BEGINS with FINAL EXAM and BACKGROUND INVENTORY

Relation to programming. Relation to computer science. Relation to computer literacy.

Course begins with final exam and intake questionnaire.

And a poster of diagrams.

Finish with exam and one page posters.

NOT computer literacy and not computer science.

Denning’s Great Principles of Computing break down into seven categories: computation, communication, coordination, recollection, automation, evaluation, and design. (Report of a Workshop on The Scope and Nature of Computational Thinking
http://www.nap.edu/catalog/12840.html pg. 29)

Quotes, Miscellaneous

"…the ability to construct rules to specify the behavior of an agent is important to computational thinking."

Automation

What do we mean by "automation"? What is the simplest example we can find? A wind up toy? Wikipedia defines it thus: "Automation is the technology by which a process or procedure is performed without human assistance." Let's see how much automation we can find within a small radius of where we are at the moment.
Thermostat
Lights that turn off if no one is moving.
Alarm clocks
Door that locks by default

Now, in each case, let's examine what automation means. One way to get at this is to ask how the task would be performed by "hand."

Thermostat: if it gets too warm, go turn the heater off; if it gets too cold, turn the heater on.
Lights: turn off the switch when you leave, turn it on when you arrive
Alarm clocks: keep an eye on the the clock and remember what time you want to do something

Food for thought: we don't mean the same thing by "automation" and "machine" - how would you distinguish them?

One way to think about automation is to describe the states that the device can be in, the events it can perceive or the commands it can receive and the state to which it moves and the actions it might take when it does on a given "input."

Consider the device shown to the right.

coffee-maker.png

Here's what the product description says: "Cuisinart introduces a fully programmable coffeemaker with a burr grinder for superior coffee. …. the strength selector and the grind control functions fine-tune the intensity and volume of your coffee. It's never been easier to make a great pot of coffee!

  • Burr grinder automatically grinds beans before brewing
  • Strength selector - choose coffee strength: strong, medium or mild
  • Grind control - program the amount of coffee you want to grind: choose from 2 to 12 cups
  • 24-hour fully programmable 12-cup (5-oz. each) capacity
  • Brew Pause feature lets you enjoy a cup before brewing is finished
  • Adjustable auto-shutoff (0-4 hours)
  • Grind-off feature
  • 2 to 4 cup feature integrated into unit

Scripting Clerical Tasks

SKILL SIDEBAR

  1. Advanced find/replace in word
  2. Wildcards and find what text
  3. paragraph mark, tab mark

I've given you a document that needs to be edited. In the first line you will notice that the word "center" appears - change it to "centre." A little while later we see fiber, liter, theater (for more examples look here). If you scan down the document you will see there are more. So, let's be lazy.

Then we learn how to customize autocorrect.

And we learn how to be a power user of advanced search and replace.

This demonstration will then move on to editing data.

And eventually we will point ourselves toward regular expressions.

Write a macro for Word.

Data cleaning with find/replace.
Example 1. File is full of space tab space junk. You want a nice simple single tabs between words.
Example 2. Let's take a scene from Shakespeare and produce a letter frequency chart.
Produce storyboard of results
TEXT > COMMAND > TEXT > etc.

Bring me no more reports; let them fly all:
Till Birnam wood remove to Dunsinane,
I cannot taint with fear. What's the boy Malcolm?
Was he not born of woman? The spirits that know
All mortal consequences have pronounced me thus:
'Fear not, Macbeth; no man that's born of woman
Shall e'er have power upon thee.' Then fly,
false thanes,
And mingle with the English epicures:
The mind I sway by and the heart I bear
Shall never sag with doubt nor shake with fear.

…MAGIC…

e xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
t xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
a xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
n xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
o xxxxxxxxxxxxxxxxxxxxxxxxxxxx
h xxxxxxxxxxxxxxxxxxxxxxxxxx
r xxxxxxxxxxxxxxxxxxxxx
l xxxxxxxxxxxxxxxxxxx
s xxxxxxxxxxxxxxxxxxx
i xxxxxxxxxxxxxxxxxx
m xxxxxxxxxxxxxxx
w xxxxxxxxxxxx
b xxxxxxxxx
f xxxxxxxx
c xxxxxxx
d xxxxxxx
u xxxxxxx
p xxxxxx
y xxxxx
g xxxx
v xxxx
k xx
j
q
x
z

Hand Algorithms

Exercise: each team gets a deck of 13 playing cards, all from one suit; your task is to sort them from low to high. First we have to constrain ourselves to a few simple operations. We can count the cards. We can look at a card and recognize its value. We can remember one card at a time - both its value and its location. We can compare the value of a remembered card and another card. We can swap the position of two cards.
Thus, we can do things like look at a card, compare it to it's neighbor to the right, swap them if the first is larger than the second.
We will, in version one of the exercise, count comparisons and swaps.
First, spread your cards out and come up with a strategy for sorting them.

Questions

  1. What ordering system did you use?

Reading Have a look at the Wikipedia article on Sorting.

Learning How to Count

Consider a 4x4 grid of squares (cells) that can be either black or white (filled or empty, 1 or 0).

  1. How many different patterns are possible?
    1. Do the exercise by counting up and then by counting "down" (recursively).

AI in the Classroom

Draw a grid on the board. Let's start with 4x4 and let each square of the grid be black or white.

Topics from UofT Planning Syllabus
  1. Classic breakdown
    1. Abstraction (visualize a zooming level of explanations - how does this work? clicking with mouse all the way down to electrons)
    2. Decomposition
    3. Pattern Recognition
    4. Algorithmic Thinking
    5. See "Computational Thinking by JULES" (4:31)
    6. See "Computational Thinking" (2012) Jeanette Wing at Microsoft Research (40:08)
    7. See "Solving Problems at Google Using Computational Thinking" (3:43)
  2. Abstraction.
    1. Robotics Academy. "- Computational Thinking"
      1. Think about maps that leave information off when not relevant
      2. Think about Platonic forms. Or Eviatar's TFG around "what did you do?"
      3. Compare to black boxing
    2. CSER - The Computer Science Education Research Group. 2016. "Abstraction - Introduction"
      1. Process / Data / Specification
    3. Curriki. "Computational Thinking: Abstraction and Pattern Generalization"
    4. DJR: examples from a whole bunch of different fields. Generic. Generalization. In science, models. Periodic table. Taxonomy. Math or GIS as points, lines, areas. Grammar. Mad libs. Graphic design. Men/Women. Olympics. MIT press logo. Look at material in my intro lectures on modeling. Tangrams.
    5. OOP Channel. 2017. "What is abstraction" Describing same object in different ways. Relevant to the task at hand. UML diagrams (see also SmartDraw, UML-diagrams.org, Wikipedia).
    6. I Am Dev. 2016. "[What is abstraction in programming?]" Pretty good straightforward presentation (3:23). Emphasis: when you don't care about internals. Connect with what I've been calling modularity.
    7. Points to phenomenological generalization. And to the thing we do when we name clusters in brainstorming.
    8. Story of my disk access routines for FXNET. Also relates to APIs.
    9. Cf encapsulation where we hide details for protection
  3. Decomposition. Polya-if a problem is too hard, it contains smaller problems that are not. Analysis and Synthesis.
    1. Curriki. 2016. "Computational Thinking: Decomposition." How does X work? Break it down. Main functions, then their components. Example: crime scene investigation; song composition; app design; essay writing; my exercise on describing getting up in the morning or getting ready for bed;
    2. DJR: is there an exercise in creating fonts with different levels of pixels?
    3. See Google Divide and Conquer? Cf. Soo Bong's searching for lion in the Sahara. How the game Battleship works? Can we put together a quiz that asks us to identify "same" scenarios.
  4. Pattern Recognition
  5. Basic Algorithmic Design, e.g. ”sorting”.
  6. Logical operators (conjunction/disjunction).
  7. Graph Theory.
  8. Problem Solving Strategies, e.g. ”Divide and Conquer”.
  9. Data encoding and organization, e.g. ”Indexing”.
  10. Sequential vs. Parallel Execution.
  11. Control structures, e.g. ”if-statements”, ”loops”, etc.
  12. Recursion.
  13. Introduction to Programming, e.g. ”variables”

Wing Notes from MR India Talk 2016.

Classes of CT Thinking Concepts

  1. Algorithms
    • e.g. mergesort, binary search, string matching, clustering
  2. Data structures
    • e.g., sequences, tables, trees, graphs
  3. State machines
    • finite automata, Turing machines
  4. Languages
    • regular expressions,…
  5. Logics and Semantics
  6. Heuristics
  7. Control structures
    • parallel/sequential, iteration, recursion
  8. Communication
    • synchronous/asynchronous, broadcast/P2P
  9. Architectures

Sample Lecture With Problem Set Includes

Suspendisse dapibus consequat mi sit amet mollis. Nullam sed egestas risus, sit amet facilisis metus. Maecenas molestie sapien elit, eget iaculis quam blandit a. Vestibulum in quam euismod, malesuada tellus id, finibus velit. Duis quis elit odio. Suspendisse feugiat condimentum tempus. Aliquam purus purus, egestas eu porttitor non, ornare id nisl.

Problems

1. We arrange the classroom in rows and build a network that will recognize a character in a 4x4 grid. (EDIT)

2. Make a list of all the tasks involved in going on a three day canoe trip. Arrange these hierarchically (which ones are sub parts of which other ones). Draw simple three step high level flow chart. And so on. (EDIT)

Lesson: Truth Tables and Logic

Playing With Digital Design

[https://logic.ly/demo/]
[http://www.neuroproductions.be/logic-lab/]
[https://sciencedemos.org.uk/logic_gates.php]
Simple Tool up to six inputs and outputs. Use to simulate simple adder?
Logic Circuit (windows only?)

Other Disciplines

Biology (14:01)
CS Method with effects all over: machine learning
And more: chemistry, physics, economics (automated mechanism design, voting schemes, Nash equilibria), law (Stanford CL approaches include AI, temporal logic, state machines, process algebras, Petri nets; POIROT project on fraud creating detailed ontology of European law; project on crime scene investigation)

Extending the Notion of "Interface"

Forms as UI for organizations. Door knobs and switches as UI for a house? Notion of pushing someone's buttons as UI for person?

Move at the end in the direction of the API. Primitive version of API in the commands you can send to a listserve.

Diagram Tools

https://creately.com/app/?tempID=gc7qvpsj1&login_type=demo#

Exercise on CT Concepts/Skills Outside the Realm of Computers/Technology

e.g. debugging, search algorithms, and test cases

Random Bits


Subpages