Coloring Discrete Structures

0 Review(s)
521 Download(s)
Rate & Review

Lesson synopsis

coloring conceptIs it true or false that Discrete Structures and Discrete Mathematics are the same thing? This is the kind of question that is asked in this field – or both fields if they are indeed different. Most Middle School students see a mix of discrete and continuous math without ever noticing the difference. This lesson introduces them to areas of mathematics that computer scientists use to do computational problems. Search techniques through discrete structures are illustrated through graph traversal and graph coloring.

Age Levels

11 - 13 years

Objectives

Introduce students to:
the relationship between Discrete Structures and Discrete Mathematics.
the difference between discrete and continuous phenomenon.
how to answer a question with sets.
how a discrete problem is solved through search: specifically graph coloring.

Anticipated learner outcomes

Students will be able to:
explain the difference between continuous and discrete structures.
discuss the difference in perspective of discrete math and discrete structures.
form a problem statement as a logical proposition, a Venn diagram, and an adjacency graph.
color a map with the least number of colors.

Optional Writing Activity

Is it true or false that Discrete Structures and Discrete Mathematics are the same thing? Defend your answer.

Rate this lesson plan

Add new review

Bletchley Park
Dr. Sue Black
Dr. Sue Black

Dr. Sue Black has demonstrated the power of social networking. She used Web 2.0 technologies to help raise awareness of, and critical funding for, Bletchley Park, the UK World War II center for decrypting enemy messages. She has also been an active campaigner for equality and support for women in technology fields, founding a number of online networking platforms for women technology professionals. A keen researcher, Dr. Black completed a PhD in software measurement in 2001. Her research interests focus on software quality improvements. She has recently won the PepsiCo Women's Inspiration Network award, been named Tech Hero by ITPRO magazine and was awarded the first John Ivinson Award from the British Computer Society. In 2011 Dr. Black set up The goto Foundation, a nonprofit organization which aims to make computer science more meaningful to the public, generate public excitement in the creation of software, and build a tech savvy workforce. Read Sue's blog about The goto Foundation: http://gotofdn.org

RISC processor
John Hennessy
John Hennessy

Have you ever wondered how computers can execute complex commands in mere seconds? John Hennessy is a pioneer of reduced instruction set computing (RISC) architecture which employs small, highly-optimized sets of instructions to greatly enhance computer performance. He was instrumental in transferring the technology, specifically MIPS RISC architecture, to industry. He co-founded MIPS Technologies and co-authored the classic textbook with David A. Patterson, on Computer Architecture.

As Stanford faculty he rose to be the Chairman of the Computer Science Department, Dean of the School of Engineering, then Provost and finally the President of Stanford in 2000 (and till date). Hennessy holds a Master’s and Ph.D. in Computer Science from SUNY Stony Brook. He is an IEEE Fellow and was selected to receive the IEEE Medal of Honor in 2012. Hennessey also launched significant activities that helped to foster interdisciplinary research in the biosciences and bioengineering at Stanford.

Router
Sandra Lerner

It is difficult to imagine a time when computers were not capable of sharing information and resources with great ease. Sandra Lerner pushed the boundaries of network computing as one of the co-founders of Cisco Systems, which introduced one of the first commercially viable routers. The router was born while Sandra was working at Stanford University in the 1980’s after earning her Master’s degree there in Computer Science. To avoid the tedious task of transferring information between computers using floppy disks, she and co-founder of Cisco, Leonard Bosack, created a local area network, or LAN, between their campus offices using a multiprotocol router that Bosack developed. Shortly thereafter the pair started Cisco Systems, and began selling the router which was a success, because it could work with so many different types of computers. After Leaving Cisco in 1990, Lerner started the trendy cosmetics company Urban Decay and became a philanthropist and avid activist for animal rights.

CGA palette
Mark Dean

If you have ever used a PC with a color display you have been acquainted with the work of Mark Dean. After achieving a Bachelor’s degree in electrical engineering from the University of Tennessee, Dean began his career at IBM. Dean served as the chief engineer on the team that developed the first IBM PC, for which he currently holds one third of the patents. With colleague Dennis Moeller, he developed the Industry Standard Architecture (ISA) systems bus, which enabled peripheral devices such as printers, keyboards, and modems to be directly connected to computers, making them both affordable and practical. He also developed the Color Graphics Adapter which allowed for color display on the PC. Most recently, Dean spearheaded the team that developed the one-gigahertz processor chip. Dean went on to obtain a MSEE from Florida Atlantic University and a Ph.D. in electrical engineering from Stanford University. He is a member of the National Academy of Engineering, has been inducted into the National Inventors Hall of Fame, and is the first African-American IBM Fellow.

Turing machine
Alan Mathison Turing
Alan Mathison Turing

Did you know that computing has been used in military espionage and has even influenced the outcome of major wars? Alan Mathison Turing designed the code breaking machine that enabled the deciphering of German communications during WWII. As per the words of Winston Churchill, this would remain the single largest contribution to victory. In addition, he laid the groundwork for visionary fields such as automatic computing engines, artificial intelligence and morphogenesis. Despite his influential work in the field of computing, Turing experienced extreme prejudice during his lifetime regarding his sexual orientation. There is no doubt that computers are ubiquitously part of our lives due to the infusion of Turing’s contributions.

Image credits