Schedule for Discrete Math

Last Updated on Friday September 16, 2016 01:20 PM

Fall Semester / Mathurin

 

Fall
2013
Mtg
#
Agenda For Class Meeting
(What is Planned / What Happened)
Homework Assignment/Tasks
(To be completed before the next class meeting)
AUG
19
   
 
[1]

Activity Getting a Little Discrete

examples of Discrete Math topics, background information

Assignment Getting There ASAP

 
[2] Activity Game of Sprouts
how to play, rules
Notes Graph Theory Basics: Vocabulary & Counting
vertex, edge, degree, strategies for counting

Question How Many Moves?

Is it possible to predict the maximum number of moves that can be played in a Sprouts game based on how many vertices at the start of the game?

  • introduce game by having a student come up and play
  •  
AUG
26
[3]

Activity Analyzing The Game of Sprouts

quantifiable differences, collecting data, looking for patterns, describing patterns

Research Leonard Euler

write 3 sentences about Euler's life and why he is considered one of the greatest mathematicians

  • preview the week
  • ask if anyone got the answer to the question "How many Moves?"
  • frame the activity as to get a glimpse of how mathematicians work in analysis...emphasis on quantifiable differences...and sometimes we have to look for more than just the obvious
  • interesting number of available vertices as a quantifiable difference...does this lead anywhere?
  • find patterns in the columns -- pretty easy
  • find relationships among the columns...some are easy, some not so easy -- Algebra to the rescue
  • introduce the adjective "complete" -- what do you think it means? show some examples
  • look at the pattern for complete graphs in respect to the relationship between number of vertices & number of edges -- is there a simple way to move ahead in the pattern without knowing the previous??
    ** might be a nice connection point to Pascal's Triangle
[4]

Activity The Euler Characteristic

quantifiable differences, pieces, regions, looking for patterns

Notes Describing Structures in Graphs

adjacent, planar, complete

Crossword Talking Graph Theory

facts about Euler, graph theory vocabulary

  • begin working at the structure of graphs -- ask students to draw graphs that are planar
  • Review/Discuss Euler's life and achievements with the assistance of these videos
    An Evening with Leonard Euler: http://www.youtube.com/watch?v=h-DV26x6n_Q
    The Euler Identity (New Age-ish): http://www.youtube.com/watch?v=zApx1UlkpNs
    Euler Biography (CloudBiography): http://www.youtube.com/watch?v=Ty6ejK1rAkg
  • have students draw a graph that is planar with between 8 and 15 vertices and at least 20 edges but no more than 40 edges
  • practice counting -- have students count vertices & edges
  • introduce the idea of regions or trapped space -- quantify these
  • Euler "saw" a relationship here....what was it?
  • motivate the Euler Characteristic by having
[5]

Notes  The "Essence" of a Graph

equivalent representations, isomorphisms, planar

Activity Water Puzzle

draw a graph that represents the game

Research The Four-Color Problem

6 sentences (who, what, where, when, why, how)

  • start with a picture of K4 drawn with and without edges crossing then a picture of K4 with edges crossing -- now ask "Are the graphs different?" and remind students to look for/identify quantitative differences between the graphs
  • sane number of edges, same number of vertices, same adjacency relationships...hmmm, so the only difference is the position of the vertices and how the edges were drawn -- so essentially the structure of the graphs are identical -- the DNA or the fingerprint
  • introduce the term Isomorphic and relate to the term Equivalent -- give examples of each
  • move to the Isomorphic applet at http://webspace.ship.edu/deensley/discretemath/flash/ch7/sec7_3/isomorphism.html
  • while working through the applet, focus students on looking at structures -- i.e the number of vertices, the degree of the vertices, adjacencies, and triangles -- these features will help in determining if two graphs are isomorphic
  • return to the K4 example and discuss the concept of planar in light of isomorphic graphs -- make sure to define planar as a graph that cannot be drawn without edges crossing
  • determining whether a graph in non-planar is difficult, but there are two classic examples of non-planar graphs, namely K5 or greater or K3,3
  • make the connection with the idea of looking for these structures within graphs as a way to decide if the graph is planar or not by using the applet at http://webspace.ship.edu/deensley/discretemath/flash/ch7/sec7_3/planargraphs.html
  • time permitting, discuss how these graphs get used? what is the practical reason for studying graphs? by introducing the Water Puzzle and how a graph can "map" the game
  • *** might be a good way to transition to game theory
[6]

Audio Clip Solving or Proving? The 4-Color Problem

Activity Coloring Maps

Four Color Problem, algorithms

Activity Coloring Maps

Four Color Problem, algorithms

  • ask for the who, what, where, when, how, why for their 4-color problem homework and write on the board -- verify & correct where necessary
  • introduce the audio clip and Keith Devlin
  • as the clip plays, check off/correct  the w, w, w, w, h, & w written on the board
  • dntart with a picture of K4 drawn with and without edges crossing then a picture of K4 with edges crossing -- now ask "Are the graphs different?" and remind students to look for/identify quantitative differences between the graphs
  • sane number of edges, same number of vertices, same adjacency relationships...hmmm, so the only difference is the position of the vertices and how the edges were drawn -- so essentially the structure of the graphs are identical -- i.e. the DNA, the fingerprint
SEP
02
LABOR  DAY  HOLIDAY
[7]

Activity Tracing a Graph

Seven Bridges of Königsberg & Eulerian paths, necessary & sufficient conditions

Research The Traveling Salesman Problem

6 sentences (who, what, where, when, why, how)

  • spend a few minutes reviewing: count the number of vertices, count the number of edges (count degrees), adjacent vertices, non-adjacent vertices, planar
  • sane number of edges, same number of vertices, same adjacency relationships...hmmm, so the only difference is the position of the vertices and how the edges were drawn -- so essentially the structure of the graphs are identical -- i.e. the DNA, the fingerprint
[8]

Notes/Video Movement in Graphs: Paths & Circuits

path, circuit, necessary & sufficient conditions

 
[9]

Notes Traveling Salesman Problem & Algorithms

Nearest Neighbor, Cheapest Link, strategies, establishing simple repeatable steps/clear process

Activity TSP in Florida

find Hamiltonian circuits using the Nearest Neighbor algorithm first then the Cheapest Link algorithm

 
SEP
09
[10]

Review TSP in Florida

 

Discuss TSP Applications

routing, construction

Read Splitting Terrorist Cells

  • start with a "quiz" on Canvas that refers to the homework assignment from the weekend
  • project the distance matrix and demonstrate how to apply the Cheapest Link algorithm
[11]

Discuss Connectivity in Graphs

how to measure, bridges, cut vertices, pieces, applications

Crossword Graph Theory Vocabulary Review

  • review vocab
  • re-introduce new vocab & practice
  • use campus connection as example for discussion -- how to connect
  • find Hamiltonian or Euler path? -- find the hamiltonian
  • How well connected? no bridges and no cut verticies -- yay
  • how many edges to remove before causing problems? 2 -- how bad a problem?
  • after removing 1 edge, go from zero bridges to YIKES!
  • How long will the entire construction job take? the sum of all the times is 31, but does the structure of the graph indicate shorter?
[12]

Review Graph Theory Fundamentals

Cheapest Link & Nearest Neighbor algorithms, planar, paths, circuits, complete, adjacent, isomorphic

Sample Test Questions Graph Theory Fundamentals   [Solutions]

  • distribute copies of last year's test and provide about 10 minutes for students to work on answering the questions without any assistance
  • students allowed to use all materials (notes, hw, classwork, iPads, computers)
  • remind students about the hw assignemtn
[13]

Test Graph Theory Fundamentals

Collect Homework & Classwork

Assignment Sudokus - A Glimmer of Algorithms

  • allow the entire period for the test
  • students allowed to use all materials (notes, hw, classwork, iPads, computers)
  • remind students about the hw assignemtn
SEP
16
[14]

Discussion Navigating Sudoku Using Algorithms

practice the sudoku algorithm discussed in class

Video/Activity Getting There Efficiently

Dijkstra's Algorithm

Assignment Finding the Shortest Path in Graphs [Numb3rs]

complete questions #1-4

  • start by making sure that everyone understands the goal of a sudoku and the parameters that must be satisfied -- also note that sudokus are not mathematical...the numbers could be replaced with letters or pictures...so it's more of a logic puzzle
  • solicit one or two students to explain how they start a sudoku -- have them tell what to do first using a sudoku projected on the board
  • invite students to follow the 8 step algorithm to work through the sudoku -- which quadrant to start with?
  • spend time to work through at least 2 quadrants -- emphasize that repeating the same procedure over and over -- eventually it should lead to a solution or pretty darn close to a solution
  • show the start of NUMB3RS episode "Money for Nothing" until Charlie has talked about Dijkstra's Algorithm and the possible paths out of LA show up on the computer screen
  • project the hw assignment and work through #1 together
[15]

Notes Examining Dijkstra's Byproduct

subgraphs, trees, spanning trees

Activity Modeling: Getting Things Done

flow, directed edges & digraphs, modeling

Assignment Turner Construction

find the least amount of time it will take to complete the construction project

  • review homework -- complete #3 on the board
  • "what are the chances that you'll have to find a hijacked semi in your professional life?"...so let's talk about a related idea that might be more "realistic" - construction industry anyone? remember the construction of SLC and the aux gym? 
  • Like many things in life, there is usually a sequence to how things happen -- sometimes some things can happen in parallel, other times it must be sequential -- sometimes a combo of both
  • Turner Construction -- draw a graph that represents the construction process
  • introduce directed edges and digraphs
  • how to quantify the weeks -- start with week 0 or week 1? -- how to represent in the graph
  • How long will the entire construction job take? the sum of all the times is 31, but does the structure of the graph indicate shorter?
[16]

Review Turner Construction

critical paths, flow analysis

Notes Navigating Flow in Graphs

source, sink, quantifying capacity, max flow

Assignment Finding the Flow

map the max flow for a digraph

  • continue/finish discussion of Turner Constructions -- emphasize critical paths, the analysis the graph allows for evaluating slowdowns, etc.
  • introduce flows in networks by using the conveyor belt analogy with this video:
  • discuss what other real life phenomenon are examples of flow -- include electricity and discuss why it cannot be stored
  • show the start of NUMB3RS episode "Blackout" -- need to edit the beginning but focus on Charlie's examination of the network to identify the next substation to target if the goal is a cascading failure of the network
  • use the NUMB3RS handout to work through an example of determining maximum flow - be sure to define source & sink
  • introduce hw assignment
[17]

Notes Navigating Flow in Graphs [Numb3rs]

quantifiable differences, starting backwards, exclusionary approach

Assignment How Much Can You Flow?

develop an algorithm to determine the maximum flow in a digraph

  • work through the hw modeling an algorithmic approach to determining the max flow -- emphasize finding quantitative differences between the verices and use those to determine flow through individual vertices -- working backwards from the sink
  • introduce/explain hw assignment / start in class
SEP
23
FACULTY  IN-SERVICE  DAY
[18]

Video Applications of Graphs & Algorithms

work flow & queues

Assignment Connecting the Campus

  • preview the week
  • review hw from the weekend - remind of sink, source, establishing bounds, quantifying vertices with flow in & flow out, reverse analysis
  • watch For All Practical Purposes Episode #3 starting with the Bell Laboratories piece on connectivity -- stop video along the way to make connections
  • show/discuss NUMB3RS handout Critical Maths from "End of Watch" -- highlight space race need to identify critical paths, cooking a meal example, & share experience of Pizza Hut 5 minute guarantee with an 8 minute oven
  • explain hw assignment / start in class
[19]

Activity Increasing Electricity Flow

Sample Test Questions More Graph Theory & Algorithms [Solutions]

  • indicate that one of the two activities will be selected as a 5-point possible for the hw
  • introduce/explain  Increasing Electricity Flow activity -- students will have 25 minutes in class to work together to provide a solution
  • regroup as a class and discuss
  • distribute old quiz and answer the multiple-choice & true/false questions
  • remind students to prepare for tomorrow's test
[20]

Test More Graph Theory & Algorithms

Collect Homework & Classwork

Assignment  

Prove that the number xxx is a prime number.

  • allow the entire period for the test
  • students allowed to use all materials (notes, hw, classwork, ipads, computers)
  • remind students about the hw assignemtn
SEP
30
[21]

Notes Getting Into Algorithms

multiplication & division, efficiency, prerequisites, Rubik Cubes, divisibility

Research The Sieve of Eratosthenes

  • preview the week
  • start with soliciting ways to multiply 142 and 58 -- be sure to highlight at least 4 options (traditional, repeated addition, partitioning into smaller/easier multiplications and addition, lattice multiplication, and peasant's multiplication)
  • engage in discussion with questions about prerequisite knowledge (times tables), how these algorithms are similar (lattice & traditional), etc.
  • give special attention to Peasant's because of the simplicity and relative quickness of it's method -- tie into Rubiks Cube
  • transition into algorithms for determining if a number is prime by introducing divisibility rules
  • tease out the divisibility algorithm for multiples of 3 -- connect to the partitioning algorithm for multiplication
[22]

Notes Setting the Stage for Number Theory

partitioning & factoring, uniqueness of prime factorization, sifting for primes

Research Goldbach's Conjecture

Who? What? Where? When? Why? How?

  • have "infinity" playing as students settle into to class
  • start by formally defining prime and divisible -- provide examples & stress that we are only talking about positive integers
  • transition to discussing the Sieve of Eratosthenes -- an algorithmic way to find prime numbers
  • will we eventually run out of prime numbers? gut feeling no because there are infinite positive natural numbers, but how do we know for sure the primes don't fizzle out?
  • introduce the video Lecture 7: Numbers of Prime Importance (from Zero to Infinity: A History of Numbers)
  • stop video to emphasize why 1 is not considered a prime number
  • stop video to provide concrete numerical example of showing the existence of prime numbers beyond a finite list
  • end class by discussing the idea of finding patterns in primes -- look at the Sieve table to see that primes must end in a 1, 3, 7, or 9, what about spacing -- then define Twin Primes
  • https://www.youtube.com/watch?v=iFuR97YcSLM
[23]

Video Getting Primed for Number Theory

distribution of primes, π(n) function, establishing bounds, natural log, comparing quantities

Research Mersenne Primes

Who? What? Where? When? Why? How?

  • start by discussing Goldbach's Conjecture -- who, what, where, when, why, and how -- be sure to include discussion of $1,000,000 prize
  • work through several examples -- 30=13+7+5+3+2
  • emphasize the idea of partitioning -- breaking a quantity into smaller quantities -- a way to find out about the "nature" of the number, similar to in chemistry and distillation
  • introduce and show the video Lecture 9: The Prime Number Theorem and Riemann
  • stop to highlight/explain the function π(n) -- emphasize that it's a function like functions in algebra but the difference is there is no quick and easy plug and chug way of getting the values
  • mathematicians have been trying to figure out a formula for this function with the hopes that it will give us insight/the ability to predict where prime numbers are, i.e. how they are distributed
  • breakthrough was that n divided by the natural log of n served as an upper bound for π(n) -- but how close does this upper bound get to the actual value of π(n)
  • end class with discussion of taking into account size of numbers when discussing how close
[24]

Video Getting to "Know" Numbers

divisibility, visualizing patterns, proof,

Research Perfect Numbers & Pentagonal Numbers

  • finish discussion about comparing numbers via ratios
  • ask about Mersenne numbers -- write the pattern on the board and see how well it works
  • go to the GIMPS website online and highlight how the program works and how big these numbers are/how many digits
  • introduce video The Primes from Mathematics Illustrated -- stop after the introduction of figurative numbers
  • end class by discussing figurative numbers
OCT
07
[25]

Notes Figurative Numbers: Patterns Galore

triangular, square, pentagonal, Gauss & partitions, Collatz conjecture

Research Fibonacci

6 sentences (who, what, where, when, why, how)

  • start class by reviewing the prior week and giving some examples of questions types that could be asked on the test
  •  review vocabulary -- prime, composite, odd, even
  • re-introduce figurative numbers -- numbers that are generated by arranging objects into regular polygons
  • triangular numbers: 3, 6, 10, 15, 21,... -- draw shape on board and then increase the number of edges on each side -- look for pattern to how many new vertices get added at each juncture
  • square numbers: 4, 9, 16, 25, 36,... -- draw shape on board and then increase the number of edges on each side -- look for pattern to how many new vertices get added at each juncture
  • pentagonal numbers: 5, 12, 22, 35, 51,... -- draw shape on board and then increase the number of edges on each side -- look for pattern to how many new vertices get added at each juncture
  • show how the patterns can be reversed back to include 1 and 0 for each type of number
  • now look for patterns that exist among the sets of numbers -- i.e. square numbers and triangular numbers, pentagonal numbers and triangular numbers, etc.
  • Gauss -- Prince of Mathematics -- theorem that every positive integer can be written as  the sum of at most 3 triangular numbers -- some sense that triangular numbers are in a way like prime numbers except for the uniqueness
[26]

Notes Sequences: Gauss & Fibonacci

recursive definitions, partial sums

Activity Generating Sequences in Excel

Crossword Number Theory Review

  • historical notes on Gauss -- the famous adding up integers punishment story
  • introduce Fibonacci numbers -- highlight the idea of a recursive pattern/definition
  • look at partial sums of Fibonacci numbers -- any patterns?
  • transition to laptop cart etiquette -- how to remove and not remove / how to replace and not replace
  • login using BCP credentials -- if you want to save work, several options: on your BCP network drive, personal USB drive, email to yourself
  • Microsoft Excel -- explain that a spreadsheet is a bunch of individual calculators that can talk to each other, etc.
  • establish columns with headings Triangular, Square, Pentagonal, Fibonacci -- introduce Excel commands/language while generating these number sequences
[27]

Notes Number Symbols & Zero

counting methods, number systems, alternative bases

Activity Generating Sequences in Excel

Sample Test Questions Number Theory Basics & Algorithms   [Solutions]

  • start with slide showing triangular numbers and Fibonacci numbers using Roman Numerals -- discuss the nature of Roman Numerals / positional? how many symbols necessary? grouping? compare with Arabic numerals
  • discuss counting -- one-to-one correspondence / the idea of keeping track by grouping (use a shepard and sheet analogy with small pebbles) /
  • using a deck of cards, count the cards emphasizing grouping first in the traditional 10s / then recount the cards using base 6 grouping
  • go to the GIMPS website online and highlight how the program works and how big these numbers are/how many digits
  • emphasize the idea of partitioning -- breaking a quantity into smaller quantities -- a way to find out about the "nature" of the number
  • return to
  • label a column Collatz -- introduce the =if( function to check
  • end class by distributing number grid -- complete by identifying triangular, Fibonacci, etc.
[28]

Test Number Theory Basics & Spreadsheets

Collect Homework & Classwork

Assignment Avoiding Friday the 13th

  • Is it possible to have a year without a Friday the 13th? Show/explain/justify.

  • allow the entire period for the test
  • students allowed to use all materials (notes, hw, classwork, ipads, computers)
  • remind students about the hw assignment
OCT
14
[29]

Activity Using Modular Arithmetic: Friday the 13th

modeling repeating cycles, finding congruences

Assignment Predicting the Future

  • on a separate sheet, answer #1-9

  • you must show work/steps

  • direct students to the pdf for this activity
  • depending on time and level of student, use the chart to develop the idea of repeating cycles
  FROSH SERVICE DAY / PSAT / SENIOR WORKSHOPS
  OCTOBER BREAK - Classes Do Not Meet
 
OCT
21
[30]

Notes Into the Mod: Check Digit Applications

algorithms, congruence, ISBN-10 & ISBN-13 numbers

Research UPC Number Check Digits

  • similarities & differences from ISBN check digits

  • solicit  ISBN numbers and ask to read all but the last digit / do the magic on the board
  • solicit UPC numbers and ask to read all but the last digit -- UPC have 5 and 5 inside the barcode and 1 on each end / do the magic on the board
[31]

Notes/Activity Sneaky Scrambling Algorithms

counting methods, scrambling via modular arithmetic & geometry

Read Cryptography: Secret Writing pp 11-28

  • what are the "big ideas"

  • end with rectangular transposition challenge -- offer to answer questions about the method /  depending on amount of time available, offer extra credit points for the first correct solution
[32]

Notes Only Two Options: Transposition & Substitution

scrambling vs. replacing, algorithms, reversibility

Read Cryptography: Secret Writing  pp 29-56

  • be able to discuss/explain at least 2 specific examples

  • start with second rectangular transposition challenge -- very similar enciphering method as the previous example
  • explain expectations for the reading homework -- you are responsible and there will be questions on the test that are drawn from the reading, but it's your responsibility to read
  • highlight the idea of "stock phrases" on p14 -- give example of at BCP the phrase "Go Bells" is often used at the conclusion of talks/etc. so a message between BCP students might end with "Go Bells" -- this gives enemies something to look for/a way into the system / connect this to the Enigma Machine and the allies using "Hail Hitler" as the in for breaking German messages
  • highlight the only two actions that can be performed, namely scrambling or replacing / pp17-18
  • show the NSA recruitment advertisement and highlight that they are not looking for experts in Calculus :)
  • return to the scramble MHRNRRKBEOUTYSEOC and reveal that the message is NUMBERTHEORYROCKS -- the scramble is not random, but generated by using both addition and multiplication in mod 17
  • begin a process of trying to figure out what was added and multiplied to generate the scramble -- why focus on unique letters vs. non-unique?
[33]

Notes/Activity Going Backwards: Unscrambling

modular arithmetic & inverse operations

Assignment Solving Equations in Modular Arithmetic

  • assign every student two numbers -- they will be responsible for the letters in those positions in the plaintext message
  • display a message on the board with corresponding position values -- ask students as a group to encipher the message by scrambling the positions using an affine scramble / once students have determined where their letters will be moved, have them come up to the board and write their letter...no students should be fighting for the same box!
  • model one or two letters for them
  • verify the scramble using the Excel spreadsheet
  • repeat the process but this time give the students a message in its enciphered form & provide the enciphering keys (additive and multiplicative) -- ask students to decipher the message
  • emphasize that going backwards is more difficult that going forwards
OCT
28
OPEN  HOUSE  HOLIDAY
[34]

Activity Modular Arithmetic Messages

congruence, avoiding negatives, finding remainders

Crossword History of Secret Writing

  • begin by working through the homework assignment -- assume that only a handful of students even attempted the assignment
  •  use the assignment to instruct key points for working in modular arithmetic: avoid negatives, avoid division, values should not exceed remainder values, etc.
  • use remaining class time for students to work on deciphering the message while practicing solving modular equations -- offer extra points to the first person or team to correctly decipher the message
[35]

Activity Going Backwards: Inverses

multiplicative inverses

Sample Test Questions Modular Arithmetic & Introduction to Secret Writing   [Selected Solutions]
  • begin by discussing the previous day's challenge -- assign each group an equation to solve  and then brainsorm how to use those answers to reveal the message
  • focus on equation #9 and highlight the fact that it took a long time (many additions of the mod) before arriving at a value that was a multiple of the coefficient of x -- but IS there an easier and/or more efficient way of finding the solution?
  •  --working through the homework assignment -- assume that only a handful of students even attempted the assignment
  •  use the assignment to instruct key points for working in modular arithmetic: avoid negatives, avoid division, values should not exceed remainder values, etc.
  • use remaining class time for students to work on deciphering the message while practicing solving modular equations -- offer extra points to the first person or team to correctly decipher the message
[36]

Test Modular Arithmetic & Introduction to Secret Writing

Collect Homework & Classwork

Read Cryptography: Secret Writing pp 57-90

  • be able to discuss/explain at least 2 specific examples & key differences

  • allow the entire period for the test
  • students allowed to use all materials (notes, hw, classwork, ipads, computers)
  • remind students about the hw assignment
NOV
04
[37]

Notes Mathematics of Substitution: Forwards

methods for scrambling the alphabet, one-to-one correspondence, cipher charts vs. code systems

Read Cryptological Mathematics pp 27-34

  • Monoalphabetic Substitution Ciphers

  • start class by asking students to decipher the message "Did you do your reading this weekend" that was enciphered using a mono-alphabetic substitution where the keyword 'MEAT' was used to scramble the alphabet
  • after about 5 minutes of time present Ceasar ciphers (alphabet shifting) & give an example on the board / discuss how this is not very secure-complicated
  • compare/contrast Ceasar vs. Keyword vs. Modular methods for scrambling the alphabet -- then present the idea of a polyalphabetical substitution to reduce the "Wheel of Fortune" effect
  • end class with Cement Truck joke/punchline -- give time to find patterns
[38]

Activity Automating Substitution Ciphers

text & chart referencing functions, number to text conversions, uppercase vs. lowercase

Assignment Monoalphabetic Ciphers

  •  anually create a substitution chart by typing one letter per cell
  • encipher 'bellarmine' manually making the distinction between upper & lower case as presented in  the text reading
  • introduce the idea of having the spreadsheet "automatically" do the substitution -- present the vlookup and hlookup functions
    class by asking students to decipher the message "Did you do your reading this weekend" that was enciphered using a mono-alphabetic substitution where the keyword 'MEAT' was used to scramble the alphabet
  • after about 5 minutes of time present Ceasar ciphers (alphabet shifting) & give an example on the board / discuss how this is not very secure-complicated
  • compare/contrast Ceasar vs. Keyword vs. Modular methods for scrambling the alphabet -- then present the idea of a polyalphabetical substitution to reduce the "Wheel of Fortune" effect
  • end class with Cement Truck joke/punchline -- give time to find patterns
[39]

Activity Automating Substitution Ciphers: Generating Alphabets

number to text conversions, replicating patterns using mod

 
 
[40]

Activity Automating Substitution Ciphers: Backwards

text & chart referencing functions

Video Code-Breakers: Bletchley Park's Lost Heroes

 
NOV
11
[41]

Quiz Code-Breakers: Bletchley Park's Lost Heroes

Activity Affine Ciphers

additive vs. multiplicative, keys, modular inverses

Read Cryptological Mathematics pp 76-81

  • Polyalphabetic Substitution Ciphers

 
[42]

Activity Polyalphabetical Ciphers

keys, modular patterns, Enigma Machine

Assignment Polyalphabetic Ciphers

 
[43]

Notes How Secure Is Your Cipher System?

brute force & key options, strategies for breaking

Read Cryptological Mathematics pp 103-108

  • Polygraphic Substitution Ciphers

 
[44]

Notes Increasing Complexity & Subtle Twists

Hill Ciphers/matrix algebra, steganography

Research RSA Encryption

6 sentences (who, what, where, when, why, how)

 
NOV
18
[45]

Notes - Understanding Public Key Encryption: RSA

modular arithmetic, primes, finding inverses, public and private keys

Sample Test Questions Cipher Systems & Spreadsheets  [Selected Solutions]

  • preview the week -- remind students about being prepared for the test
  • begin by discussing the problem of key exchanges -- how do you make sure that both parties have access to the same keys?
  • move into the ides of a public key -- a way for people to send you a secure message where how to encipher is public but the how to decipher is private
  • use an example of Joe wants to send the letter J to you -- you instruct hum to use mod 527 and key 7 -- takes the letter J, converts to number, then uses multiplication in the form of  exponents where the number 10 will be multiplied 10 times in a row -- this generates a large number which is then reigned in by converting to its mod 527 equivalence, so that Joe send you the number 175 which represents his original letter J / invite students to join in the process
  • how do you go backwards? solicit from students their enciphered letter values -- let them know the plan is to raise the number they sent to the 343 power! -- yikes a ridiculously huge number...how can you compute that? luckily you just want to know what the remainder is after dividing by 527
  • using an Excel spreadsheet, show how the modulu congruence can be used to compute the remainder without having to get that big number -- stress the algorithmic approach of this
  • verify that the reverse process is working correctly by checking the values from the solicited student numbers/original letters
  • transitiion to the Youtube video
  •  
  • end class with Cement Truck joke/punchline -- give time to find patterns
[46]

Test Cipher Systems & Spreadsheets

Collect Classwork & Homework

Assignment Design Your Own Cipher System (example)

  • must have substitution and transposition

  • not more than 6 steps in complexity

  • originality/creativity (5pts max)

  • communication/presentation (5pts max)

 
[47]

Cipher System Project - Introduction & Information

scope, expectations, guidelines, specifications

Cipher System Project
[48]

Cipher System Project - Organizational Workday

organize homepage, synthesize ideas for substitution & transposition, establish timeline/key dates, assign responsibilities

Cipher System Project
NOV
25
[49]

Cipher System Project - Computer Workday

enciphering & deciphering spreadsheet designed, initial drafts of PowerPoint presentation & spec sheet

Cipher System Project
  THANKSGIVING  HOLIDAY
 
 
DEC
02
[50]

Cipher System Project - Computer Workday

enciphering spreadsheet functional

Cipher System Project
[51]

Cipher System Project - Computer Workday

final versions of PowerPoint presentation & spec sheet completed

Cipher System Project
[52]

Cipher System Project Computer Workday

deciphering spreadsheet functional,

Cipher System Project
[53]

Cipher System Project - Presentations

 
DEC
09
[54]

Notes Overview of Game Theory

quantifying strategies, zero-sum, minimax theorem, Nash Equilibrium

 
[55]

Activity Two-Player Games: Strategies

collecting data, looking for patterns

Activity Sprouts Strategy

Is there a winning strategy for the game of Sprouts?

[56]

Activity Two-Player Games: Winning Strategies

rules that drive strategies, combinatorial analysis, Grundy's Game

 
[57]

Activity The Prisoners' Dilemma

rules that drive strategies, combinatorial analysis

Sample Final Exam

DEC
16
[58]

Semester Reflection

Study/Prepare for Final Exam

  SEMESTER EXAMS - SOCIAL SCIENCE & MATHEMATICS
  SEMESTER EXAMS - ENGLISH & RELIGIOUS STUDIES
  SEMESTER EXAMS - LANGUAGE & SCIENCE