Activity Getting a Little Discrete

overview of Discrete Math topics, background information

Read Green Sheet

Resources:

http://www.shodor.org/interactivate/activities/

Research Leonard Euler

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

Activity Analyzing The Game of Sprouts

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

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?

Activity The Euler Characteristic

quantifiable differences, looking for patterns

Notes Describing Structures in Graphs

adjacent, planar, complete

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)

Resources:

Crossword Talking Graph Theory

facts about Euler, graph theory vocabulary

Activity Coloring Maps

Four Color Problem, algorithms

Activity Coloring Maps

Four Color Problem, algorithms

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)

Notes/Video Movement in Graphs: Paths & Circuits

path, circuit, necessary & sufficient conditions

Notes Traveling Salesman Problem & Algorithms

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

Resources:

The Euler Archive (MAA)

Paths in Graph Theory (Wikipedia)
Finding Euler Circuits (Oklahoma State University)

Activity Algorithms Everywhere

scrambling up messages

Activity TSP in Florida

find a Hamiltonian circuit using both the Nearest Neighbor and Cheapest Link algorithms

Discuss Connectivity in Graphs

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

Sample Quiz Questions Graph Theory Fundamentals   [Solutions]

Quiz Graph Theory Fundamentals

Collect Homework & Classwork

Assignment Sudokus - A Glimmer of Algorithms

Resources:

Powerpoint on Algorithms (University of Maryland Baltimore County)

Toward a Mathematical Theory of Counterterrorism (Proteus Management Group) 

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

Notes Examining Dijkstra's Byproduct

subgraphs, trees, digraphs, minimal spanning trees,

Assignment Getting There The Fastest

apply Dijkstra's algorithm to find the shortest time to each intermediate point from Portland

Discuss Navigating Flow in Graphs [Numb3rs]

directed edges, source, sink, quantifying capacity, finding flow paths, determining max flow

Notes Searching for Prime Numbers [Numb3rs]

definitions, exclusionary approach, Sieve of Eratosthenes

Resources:

Notes Unpacking Familiar Algorithms

addition, multiplication, division, relevance of grouping in number systems

Research Zero

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

Discuss How & Why Zero Became a Number

Video More Applications of Graphs & Algorithms

work flow, minimum spanning trees

Assignment Turner Construction

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

Discuss Turner Construction

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

Assignment Connecting the Campus

Assignment Increasing Electricity Flow

Sample Quiz Questions More Graph Theory & Algorithms [Solutions]

Resources:

Quiz More Graph Theory & Algorithms

Collect Homework & Classwork

Research Perfect Numbers & Pentagonal Numbers

Activity Creating an Dynamic Invoice Form

laptop cart etiquette, introduce & enroll to Moodle, basic features & operations of a spreadsheet

Video The Magical & Spiritual Allure of Numbers

meanings for Pythagoreans, figurative, perfect, & amicable numbers, magic squares

Research Patterns in Pentagonal Numbers

Resources:

Activity Getting Grundy With It

number patterns, data collection, strategies

Research A Big Prime Number

What was the largest known prime number on the day you were born?

Notes Setting the Stage for Number Theory

sequences, partitions, p(n) function, connection to triangular numbers

Video Getting Primed for Number Theory

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

Research Goldbach's Conjecture

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

Notes Partitioning: Primes, Clever, & Useful

divisibility, Goldbach's Conjecture, algorithm for substitution

Research Euclid's Algorithm

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

Notes Euclid's Take on Partitions & Into the Mod

greatest common divisor, congruence, applications (ISBN numbers, check digits)

Resources:

Collatz Conjecture (Wikipedia)
Partitions (Wikipedia)

Euclidean Algorithm (Wikipedia)

Spreadsheet Automating Algorithms

finding GCF/GCD via Euclidean, generating triangular numbers & sequences

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

Notes Going Backwards in Modular: Inverses

replacing subtraction with addition, replacing division with multiplication, conditions for multiplicative inverses

Assignment Modular Arithmetic: Inverse Operations

• on a separate sheet, solve #1-12

• you must show steps for all of your work

Notes Finding Inverses via Fermat

replacing subtraction with addition

Sample Quiz Questions Number Theory, Modular Arithmetic, & Spreadsheets

Discussion Saving Madeline from Markov

identifying strategies, counting, data collection & representation

Activity Developing a Saving Strategy from Data

Sample Quiz Questions Number Theory, Modular Arithmetic, & Spreadsheets

Quiz Number Theory Basics & Spreadsheets

Collect Homework & Classwork

Assignment Decoding a Secret Message

• you must fully document all your attempts/work (even dead-ends) on a separate sheet

Activity The Decoding Experience #1

identifying strategies

Read Cryptography: Secret Writing pp 11-15

• what are the "big ideas"

Activity Making & Referencing Tables

laptop cart etiquette, lookup functions

Read Cryptography: Secret Writing pp 16-28

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

Crossword History of Secret Writing

big ideas, transposition vs. substitution, examples

Read Cryptography: Secret Writing pp 29-56

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

Video Code-Breakers: Bletchley Park's Lost Heros

Lorenz Machine (Tunny), number of settings & prime numbers, depth for breaking

Read Cryptography: Secret Writing pp 57-85

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

Reading Quiz Cryptography: Secret Writing

Read Cryptography: Secret Writing pp 86-90

• be able to discuss/explain the difference

Resources:

http://www.archive.org/details/ird059

http://www.bbc.co.uk/programmes/b016ltm0
http://www.bletchleypark.org.uk/edu/teachers/ccresources.rhtm

Notes Quantifying the Potential Substitutions

monoalphabetic vs. polyaphabetic, affine, developing algorithms for automation

Read Cryptological Mathematics pp 27-34

• Monoalphabetic Substitution Ciphers

Notes Mathematics of Substitution & Going Backwards

additive vs. multiplicative vs. affine, Fermat's Little Theorem, Euler's generalization, big number calculators

Read Cryptological Mathematics pp 76-81

• Polyalphabetic Substitution Ciphers

Spreadsheet Automating Substitution Ciphers

text referencing functions

Read Cryptological Mathematics pp 103-108

• Polygraphic Substitution Ciphers

Notes Mixing It Up Along the Way: Polygraphic Ciphers

changing key example, matrix algebra, Hill Ciphers

Sample Quiz Questions Cipher & Code Systems

Cipher System Project - Introduction & Information

scope, expectations, guidelines, specifications

Quiz Cryptography: Secret Writing

Collect Classwork/Homework

Cipher System Project - Computer Lab Workday

editing & adding pages/content to wikis, organize team homepage, generate ideas for substitution & transposition

Cipher System Project - Computer Lab Workday

create a calendar/timeline, identify & establish target dates, assign responsibilities

Cipher System Project - Computer Lab Workday

spreadsheet layout & enciphering model

Cipher System Project - Computer Lab Workday

enciphering spreadsheet functionality, drafts of PowerPoint presentation & spec sheet

Notes - Understanding Public Key Encryption: RSA

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

Cipher System Project Computer Lab Workday

deciphering spreadsheet functionality,

Sample Quiz Questions Cryptography: Codes & Ciphers

Quiz Cryptography: Codes & Ciphers

Collect Classwork/Homework

Cipher System Project Computer Lab Workday

Activity A Different Type of Secret: Steganography

video explanation, examples, generating patterns with random numbers via algorithms

Presentations Cipher System Project

Notes Overview of Game Theory

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

Presentations Cipher System Project

Video - Pi [00:00 - 19:25]

analysis of main characters, plotline basics, Fibonacci Numbers

Movie Pi [19:25 - 42:54]

numerology vs. mathematics

Movie Pi [42:54 - 71:00]

Golden Spiral & Rectangles from Fibonacci Numbers

Sample Final Exam

Movie Pi [71:00 - 85:00]

connections between Sol, Marcy, Max, and Lenny

Semester Reflection