A Level Miscellany

From de51be530fd87391e8dab7c2f39d33152dba2515 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Thu, 5 Mar 2015 23:58:19 +0000 Subject: [PATCH] First bit of the A-level miscellany --- Hash_table_5_0_1_1_1_1_1_LL.svg | 254 ++++++++++++++++++++++++++++++++ Karnaugh_map2.png | Bin 0 -> 2643 bytes SIGNED.md | 31 ++-- Untitled1.ipynb | 75 ++++++++++ a-level-miscellany.html | 231 +++++++++++++++++++++++++++++ index.html | 3 + 6 files changed, 580 insertions(+), 14 deletions(-) create mode 100644 Hash_table_5_0_1_1_1_1_1_LL.svg create mode 100644 Karnaugh_map2.png create mode 100644 Untitled1.ipynb create mode 100644 a-level-miscellany.html diff --git a/Hash_table_5_0_1_1_1_1_1_LL.svg b/Hash_table_5_0_1_1_1_1_1_LL.svg new file mode 100644 index 0000000..73a2b83 --- /dev/null +++ b/Hash_table_5_0_1_1_1_1_1_LL.svg @@ -0,0 +1,254 @@ + + + + + diff --git a/Karnaugh_map2.png b/Karnaugh_map2.png new file mode 100644 index 0000000000000000000000000000000000000000..a4eed109af1ab245aa9cec6e5b0b993747413b76 GIT binary patch literal 2643 zcmX|D3p~^78((!?5^K(JLj9ysj$BW(*r*m;Zjnnwr-Wt*X`9P9N+CvN?#|@kjN_J& z>&a$`$z0}|TbSfl$V5A~V)kF>eE#QsKJVv!-uLtUJfG+JzR&wSZ<6B$D+RfOav%^$ z!NwZn3qV$!`OeSW-W&v~?lh5luq4^5hMsc|y?Dzvl;lmsfy{kw zUB?}2mrkcc zAdnmo2!p}!csw$h%;9h_n0gYalfzl2j#6D+86*;k#}m3rG*{R1@^bDv7g7LO=5T~O z-YAtyr_asN>767}2^3l{F(Tw)>M;^1l{#7gfj~>3Fjys-+z*A8l$TF&mO1n}dL<0D z&gJ%#$*@XTtFJGqlf>n&ll#e2<>kJuz7R-(uWxJlRQWfj#bT+Z{w@$`uc{5k+$Cb- zBi9d`YpNveg*BtL5BFWOuX_x)&n=0X3hNV#-G1|C2OT|oq_tu{B@U;NFAMFmifFe^ zgYVvjc)1IVm(RuqT4MT^3=qxrD+4+)agiqk0Ub?(`P;vON-|9^TvnG^D2*MH?sVc`_e7RGmoEFHqFO;~N8hE$1AW|4 z5=H)x4gEXwWx|vyx6_u=uHbb+3|1D92jlPU0cJqtH+z8@|HL>uJ2~Xn{L7EgQ@K9f z8ce@;`}37TWW_NvvI{$8;y?%C89;Vf{eY6msO2mYI#(}8jFlJ{&+035g}x%tq-6eK zKw?p}FdlghKAG0J9Z<>!uDpZyT>6}|@bTci;ComLc!3>In1o+!a`(*|=teZgX+*@o z2{x_E%meC8DVH60SHq2RI2TF>Mc`EWSrYd5W`HTQVj zrRg>3y81EX@V0S zJBxOK{j~Z9Eg%8WcE9QZO9VTng&RjtDeUU{*?xWKPU@_lBW5W)RxI(U?2EiZIPv^DlLK^5wRK z94M!C2J%#r2>%i_OdpVL>2py2kZ_KzTt_3~mn&)`e!Ao--O<{$w)eC8B5NTrMu?&$ z^;HltLkJVC=%-PM(c4in*w4q&)oRyF^W>?TZ^A#CVi>Go+akAYAvqu2JV1P;X}o@# zAFN_Xk?Bi&;T(*W{p$-CSrvl2T&blvdt@+P=V+a6y!))~KBW}@8$TW~Y%_1GIN;y# zHmuh6`!sQ?=oiMG?U6XIRmh`~(s7-vc_?m-(yYdQ%axX?LC8ET(5sL+|Iw!l^>c*> z__{YZea3yE!95e*jy^48125K_GOhaji#@zJ+p&dpzsvmm6O}vfpFQ78=?#9om}m#c z=WCuxN$*XQx2;w#R9~=;XDIWK*^@ddZLZ)14Moa)L7B2VE=xK8fm{Ve^JGspD^2zv z=$v%|LpcN!V$z?MAH=z7b|2Y|)vR=Z9-RRH4OqAx@TP2(MR_2trK}>aHcSIky5QYb zXc71ru;3(+Lk3iaJGTvXWfi9t$Jipei+HXfN`kgSGuAuBB~itNo=+5e^4P7e$opGr z&Oot~KnK}v6`h52;ijKmN<0AEBxuv~k{W>)IS3|n+pb_k(-d=@1_+Q!n1*D|lTIU3iv zM82{(Ro7tPwF0EC$iY~=L+&+@{wXMVn7+FY5STo>4$W^e16Lj9xle~%uc`w2ArQn% zry28^L;{AFW#mJdEskN$Xe8U2|yr7gORS3A*Y;? z@5ry7ATS2?3gAz<3^W>rXb<*tt{Q}q3zyUnFy17WS?)(*g5zE8dlQs_fJNIevdigL z`^FBF({uOrrpbBYTg%Zz$If2t6S}M=D<|+;}9K`#^uc7d(e>-=~20 z@1|KDyy0xr3`gbN(;V#?mtxboRN>nU28ey$=<99j^XngxEPVkJ@C>SA}ghU_+0VBS8p_Lyu;k-)^2iKPJj%5$+QD1&t!p zGPMHKxVSig-CDX7au@M}VNOrZ)5}fFN0}EtyBpuz5xAwXQ+s!yrBv*br>CAgAHiRi zYFQ8LxQXvR8o-WsGZfZ2DBiL?K9YI(*yAC;ACOfRvDG^bo25}vUAK6J>?k2*TlnrI zEx%o4xMlTV&IeT{E50Cb5PIDTqj6367F#DznODUIuJ-1PDQxNf+Kg%o9;1;e6&T(E zRr{rBn*jy0jr`NqCLUN>vZDUC%&L4X-YpMm#5~|7k=(q#ee!J1UBFaXc*Xt?PfiLf literal 0 HcmV?d00001 diff --git a/SIGNED.md b/SIGNED.md index 91947e6..7964d97 100644 --- a/SIGNED.md +++ b/SIGNED.md @@ -3,19 +3,19 @@ -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 -iQIcBAABAgAGBQJU53KIAAoJEJPB2e07PgbqI38P/j/eQEa78/O/0rw7Gvnnglut -pHkghfKnyX0NSTif8OpK7MtxikwC8h8BMu7+KOX+BZu31RAZxeXVdxHkyKXT7/jD -YLXPeK/803362bsJiL9yebVf5C1it8opIzCGe/nx6O+bLHqO8eEuaB9xmE5CnS+T -etEijh889LP3dwKPjYia+kJci55mHLoVgWQzXbQQnvc8Pi3TNRbHOehdSRgGOa5k -g5HAJdggPGgnTrzItsA86yZzAdjgSBbJvs/aGn4Qjx5w+wiiN0BANI3/H3cgP7Hc -Yeby1VfFo3Kqpp48EggTw54+Tgvco17QB3PQj4Nux/FbdKeSS+eT/2m/4uOVblXT -w8tcmZS9DHctD/g3e+9C0eAcVZgSygzdFhK7zJ1o3x0z0Ic9/qcHxaWvijcExjeB -E0gr2matR9zZshRJKLlKs975xoQL9OlcpZHcvVijAkp9aCr8/zgGWlrFmNHnMqKx -bg2LxV3SgKpoTvpqAWEugUD4OgSZ2iuqCVhqMnCt5hesqmHJSJ7wH5t1XyEml8mx -z1VDeMWtVAf/xjU9tN/++JWVFH9YxvL/2FFuREWYch35dc9LuUUrwkUk+dR+sdW9 -D8y51adNR1cfzVefzyInBku3tu+lE3JRGKizT9rdWl8V+kq9Ma9BiGrn1W8LYHI3 -+M56lSm5HEJK+lQ0W7TP -=ywOf +iQIcBAABAgAGBQJU+O2fAAoJEJPB2e07PgbqUS8P/RXy5zccLlaXhVVSjC2bwBk9 +87Ibf1DoiJVIfZ3iPKLiqv66L3KyDjBTlpNvH8XvvRkQ1i4M5tdWEWeqWkKJXAAd +yo+k5dAX7if4jvzpt9d88CituRBhn9AtXnlhwx0vVfYU2f7amhlWN5TEhPUbzrKG +V5JWXQv1So4ZIU5bHSj2Qd3exQAVxWpm/OY239E7WlahgkbUzqzzd9KdLvyeSjE9 +JSQ+8yotXBu12wMNhrwmd/spa1UTFhD602h6Vcur7QmFAftm/eFID+IY+wFfsjou +WXSM7SgL3PXkKCzSCHYhO41y3XFalBMfFqeri0iV7J1y8rLPfchmm10NZZOZTz3Q +M+lPFa9BTRLZ5HlwC9w0hmnFaqBHQetEnscu3V+7qst0QPUvGM9QWvfn87HRwB1i +8fahdrVBrwrJceEOfcnLov4zMeoR5x61J1VNPBuWtVZ9BVczjlkJBs+NflbM0uFu +lE2jwcqgrMBpPATNs7L4GfNbWJdRhd3d3meZhSxnxe0O7fubX8mm3gXGB96+r/58 +ppfb5axeeU/DC+B0og/xUmqSAjwP9YYUqjSv7zu6YMVj3UDLJZVdb/RoRkA4AlCI +BJUEtMKvCe7wRoMbS91oA8UvOFqxkC05qBpPnwBmOJs5hbGbeg8fu7j8WK1K3DBs +cPHT6YsBiIb8dR1F7RFS +=yzXB -----END PGP SIGNATURE----- ``` @@ -30,9 +30,12 @@ D8y51adNR1cfzVefzyInBku3tu+lE3JRGKizT9rdWl8V+kq9Ma9BiGrn1W8LYHI3 size exec file contents ./ 384 .gitignore a93de2ae5c2a47a38599751d1f914566569dfa09dd1778e207117db6c71421dd +11547 Hash_table_5_0_1_1_1_1_1_LL.svg e95ff61c4b3a5e202fdea793673e5288321aade8eaac1e9bc61229ee0a27c7ba +2643 Karnaugh_map2.png fffe1982ec61fea8cc6488c7bf7206572297962419f3ee71d95867e27f7c9d87|30ce6e3887da5efb4068383508a86bc6e38153c53c307a23c29632795b166bd3 339 README.md b6a32e10a4a36e2de32385dedef3e88bad767c41a92caeb93086d5065ac0a188 78868 Untitled0.ipynb 8ac2a76fb3b6f29f2b3a35c4db46c35ec81d053c9a86bec8a1dee48905d5953a 1363 Untitled1.ipynb ef878c0d63f138a496713f862ef177f4346942944b690ad48589e7adb929b62d +7656 a-level-miscellany.html d0df27fdaeeebfb886193b8b2f68204e625093d363021e8dee5adfd8b1cfbd1d 81789 alan-turing.jpg 52fc427b7eee09b10682cf36594ff9038f497c856c284d912f44c7603561969b|300c9f022062d629ec4f4bcb7192d732ca850d0ab92f9f39b2b90981979abdf7 13180 algorithms.html 5d983371c7ba55108c68d19a8dfe419dfa387587b764415bce09c59e55d1c5da 20722 big-o-chart-2-smaller.png e57e10b28aa20f09b308fee493a996cea11a374160edd36a82170730130b7446|d0f348376c076c50c429756da7ee020e545aa5ff781fe4b983662cf23f503d0b @@ -63,7 +66,7 @@ size exec file contents 5366 hangman.html 64a75e50559c236118e2cc91651f5ac7091d14f3d27b7038a3d4770beb3dee08 4167 hangman2.html 84014a67033d320605b3ae2eacc6a2f622560a2694487624c39d9fd66a9278f4 41276 human-computer-worksheet.png 354fa591f28e7b979f8efa9ed6423ce76e019601628945ac61b173bf6107ce60|11073eea5462dd9fbd056cc6694dbab62408e251c64001dc7090060d7fbf96ff -2191 index.html 4b8e1de469018e557ce42955c3ede679f08d8a5421a9b1c5cb91ae03ed681a75 +2265 index.html a104a11703f9ca8b58711265a6d60c6f105c9061e7d8aeab898d1f344f0368be 650 make-change.dot cc56b42a08ee78b0ec2afa8c96ce4574ae546f959e535e68605beb66394247c1 54549 make-change.dot.png 7c46cdaac91b084a95903de65685906d2c61cd1c55d740936ec6f1bb9050ee22|bd52720ce8c4b7350caed16cc72954757550f4e62e8a030f151922ac9a11dffe 2216 oulogo_hor.png 93dae19a7dde063927ca9a3ec7d468cc20f0bc4da9091fdf4819273ab4cf524a|f73072930ecf211ce23d4559b9fbdd11c1be4a0451fa6a8f74ad803d4f5f71ee diff --git a/Untitled1.ipynb b/Untitled1.ipynb new file mode 100644 index 0000000..bf17f6f --- /dev/null +++ b/Untitled1.ipynb @@ -0,0 +1,75 @@ +{ + "metadata": { + "name": "", + "signature": "sha256:383dbd07426142dba085750cea664fb5a2eb5d274834904c9266a800ddf86c5c" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "code", + "collapsed": false, + "input": [ + "def anagram1(word1, word2):\n", + " return sorted(word1) == sorted(word2)" + ], + "language": "python", + "metadata": {}, + "outputs": [], + "prompt_number": 2 + }, + { + "cell_type": "code", + "collapsed": false, + "input": [ + "anagram1('happy', 'sad')" + ], + "language": "python", + "metadata": {}, + "outputs": [ + { + "metadata": {}, + "output_type": "pyout", + "prompt_number": 3, + "text": [ + "False" + ] + } + ], + "prompt_number": 3 + }, + { + "cell_type": "code", + "collapsed": false, + "input": [ + "anagram1('happy', 'hpayp')" + ], + "language": "python", + "metadata": {}, + "outputs": [ + { + "metadata": {}, + "output_type": "pyout", + "prompt_number": 4, + "text": [ + "True" + ] + } + ], + "prompt_number": 4 + }, + { + "cell_type": "code", + "collapsed": false, + "input": [], + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +} \ No newline at end of file diff --git a/a-level-miscellany.html b/a-level-miscellany.html new file mode 100644 index 0000000..832a4f0 --- /dev/null +++ b/a-level-miscellany.html @@ -0,0 +1,231 @@ + + + + A Level Miscellany + + + + +

+
+# A-level Miscellany ![Open University logo](oulogo_hor.png)
+
+* Hashing
+* Boolean algebra
+* Karnaugh maps
+* Python file handling
+
+---
+
+layout: true
+
+.indexlink[![Open University logo](oulogo_hor.png) [Index](index.html)]
+
+---
+
+# Hashing
+
+Convert any of a large range of value to a small range of values
+
+Two purposes:
+
+1. Putting many things in few buckets
+2. Cryptographic signing
+
+---
+
+# Hashing many things into a few buckets
+Useful for dividing items into files, or balancing items across any data structure. 
+
+Some examples (from [Geoff Kuenning's old course notes](http://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200101/homework10/hashfuncs.html))
+.float-right[![Chaining hash table collisions: from https://commons.wikimedia.org/wiki/File:Hash_table_5_0_1_1_1_1_1_LL.svg#mediaviewer/File:Hash_table_5_0_1_1_1_1_1_LL.svg](Hash_table_5_0_1_1_1_1_1_LL.svg)]
+
+* **Division method** (Cormen) Choose a prime that isn't close to a power of 2. h(k) = k mod m. Works badly for many types of patterns in the input data.
+
+* **Knuth Variant on Division** h(k) = k(k+3) mod m. Supposedly works much better than the raw division method.
+
+* **Multiplication Method** (Cormen). Choose m to be a power of 2. Let A be some random-looking real number. Knuth suggests M = 0.5*(sqrt(5) - 1). Then do the following:
+    1. s = k Ã A
+    2. x = fractional part of s
+    3. h(k) = floor(m Ã x)
+
+Problem of hash collisions, where multiple items provide the same hash value. In a data structure, do something like chain multiple values together.
+
+---
+
+# Cryptographic hash functions
+
+Maps a large file into a smaller space of values, e.g. SHA-256 maps any file to a 256-bit digest
+
+Cryptographic hashes have additional features:
+
+* Easy to compute
+* One way: can't derive a source from a hash
+* Sensitive: modifying a source changes the hash
+* Few collisions: different souces have different hashes
+
+MD5, SHA-1 in common use, but broken. SHA-2 developed by NSA, but seems secure...
+
+Useful for validating messages, downloaded files, etc.
+
+* Alice posts message and hash
+* Bob downloads message and hash
+* Bob computes hash for message and compares to what Alice posted
+* If they're equal, Bob's happy that the download was successful
+* If Eve changed the message in transit, the hashes won't be the same
+
+---
+
+# Signing messages: authentication
+
+Assume a public key encryption scheme.
+
+* Alice finds a message's hash, encrypts it with her private key
+* Alice sends the message plus encrypted hash to Bob
+* Bob decrypts the hash with Alice's public key
+* Bob hashes message and compares it what Alice sent
+* If they're the same, Bob knows
+    1. The message wasn't changed in transit
+    2. Alice must have sent the message, as only she had the private key
+
+See also TU100 Block 5 Part 3 on cryptography and security.
+
+---
+
+# Bitcoin
+Hashes used as proof of work for 'mining' bitcoins.
+
+* Block is transaction history + nonce word
+* Challenge is to find a nonce word that gives a hash in the correct range
+* No shortcut: must try many, many nonces and see what works
+
+---
+
+ # Boolean algegra identities
+
+|Rule | Left | Right | 
+|------|----:|:----|
+|`$\text{Associativity of } \vee                             $`|`$ x \vee (y \vee z)     $`|`$ = (x \vee y) \vee z $`|
+|`$\text{Associativity of } \wedge                           $`|`$ x \wedge (y \wedge z) $`|`$ = (x \wedge y) \wedge z $`|
+|`$\text{Commutativity of } \vee                             $`|`$ x \vee y              $`|`$ = y \vee x $`|
+|`$\text{Commutativity of } \wedge                           $`|`$ x \wedge y            $`|`$ = y \wedge x $`|
+|`$\text{Distributivity of } \wedge \text{ over } \vee \quad $`|`$ x \wedge (y \vee z)   $`|`$ = (x \wedge y) \vee (x \wedge z) $`|
+|`$\text{Identity for } \vee                                 $`|`$ x \vee 0              $`|`$ = x $`|
+|`$\text{Identity for } \wedge                               $`|`$ x \wedge 1            $`|`$ = x $`|
+|`$\text{Annihilator for } \wedge                            $`|`$ x \wedge 0            $`|`$ = 0 $`|
+|`$\text{Double negation }                                   $`|`$ \neg \neg x           $`|`$ = x $`|
+|`$\text{De Morgan's Law }                                   $`|`$ \neg ( x \wedge y )   $`|`$ = \neg x \vee \neg y $`|
+|`$\text{De Morgan's Law }                                   $`|`$ \neg ( x \vee y )     $`|`$ = \neg x \wedge \neg y $`|
+
+You can prove all these by truth tables.
+
+---
+
+# Boolean Notation
+
+`$ \wedge = \& = Ã = \cdot  = \text{and}$` ; `$ \vee = | = + = \text{or}$` ; `$ \neg x = \: \sim x = x' = \overline x = \text{not}$`
+
+## implies
+
+`implies` is a connective: `$a \text{ implies } b = a \rightarrow b = a \supset b = \neg a \vee b $`
+
+`$ A $` | `$ B $` | `$ \neg A $` | `$ \neg A \vee B $` | `$ A \rightarrow B $`
+:--------:|:---------:|:--------------:|:---------------------:|:-----------------------:
+    F     |     F     |       T        |           T           |          T
+    F     |     T     |       T        |           T           |          T
+    T     |     F     |       F        |           F           |          F
+    T     |     T     |       T        |           T           |          T
+
+If A is true, B must be true. If A is false, B can be anything.
+
+Use other notation for derivations and proofs: see your friendly mathematicians.
+
+---
+
+#Karnaugh maps
+
+.float-right[![Karnaugh maps](Karnaugh_map2.png)]
+
+A way of visually simplifying Boolean expressions. 
+
+Draw the biggest loops you can, don't worry if the overlap.
+
+---
+
+# File handling in Python
+
+* Reading, writing appending
+* `read()` and `readlines()`
+* Text and binary
+* Text encodings
+
+
+
+
+

+ + + + + + + diff --git a/index.html b/index.html index 14184be..5abad17 100644 --- a/index.html +++ b/index.html @@ -60,6 +60,9 @@ * [Hangman part 2](hangman2.html) * [Algorithms](algorithms.html) +# CAS A-level miscellany + +* [A level miscellany](a-level-miscellany.html)