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  Activity examples of Discrete Math topics, background information Assignment  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
 SEP 02 LABOR  DAY  HOLIDAY  Activity Tracing a Graph 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  Notes/Video Movement in Graphs: Paths & Circuits path, circuit, necessary & sufficient conditions  Notes Nearest Neighbor, Cheapest Link, strategies, establishing simple repeatable steps/clear process Activity find Hamiltonian circuits using the Nearest Neighbor algorithm first then the Cheapest Link algorithm
 SEP 09  Review TSP in Florida   Discuss TSP Applications routing, construction 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  Discuss how to measure, bridges, cut vertices, pieces, applications Crossword 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?  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  Test Graph Theory Fundamentals Collect Homework & Classwork Assignment 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  Discussion 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  Notes subgraphs, trees, spanning trees Activity flow, directed edges & digraphs, modeling Assignment 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?  Review critical paths, flow analysis Notes source, sink, quantifying capacity, max flow Assignment 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  Notes Navigating Flow in Graphs [Numb3rs] quantifiable differences, starting backwards, exclusionary approach Assignment 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  Video Applications of Graphs & Algorithms work flow & queues Assignment 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  Activity Sample Test Questions [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  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  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  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  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  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  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  Notes Sequences: Gauss & Fibonacci recursive definitions, partial sums Activity Generating Sequences in Excel Crossword 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  Notes Number Symbols & Zero counting methods, number systems, alternative bases Activity Generating Sequences in Excel Sample Test Questions 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.  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  Activity Using Modular Arithmetic: Friday the 13th modeling repeating cycles, finding congruences Assignment 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