VCTAL has developed a set of instructional modules, for use in high school classrooms. The modules are intended to cultivate a facility with computational thinking in students across different grade levels and subject areas. The project was administered by DIMACS at Rutgers University in collaboration with the Consortium for Mathematics and its Applications (COMAP).
Computational thinking is a high level thought process that considers the world in computational terms. It begins with learning to see opportunities to compute something, and it develops to include such considerations as computational efficiency, selecting appropriate ways to represent data, and making approximations. A person skilled in computational thinking is able to harness the power of computing to gain insights. Computational thinking is not programming. It is a thought process that can be brought to bear not only in programming but also in a wide array of other contexts. It relates to mathematical thinking in its use of abstraction, decomposition, measurement and modeling, but is more directly cognizant of the need to compute and the potential benefits of doing so.
It’s an Electrifying Idea!
This module explores whether it’s time to buy an electric car by examining its cost to own and convenience to operate. The module has two stand-alone parts that can be used together or separately. The first component examines the cost of owning anelectric car relative to a traditional hybrid or a gasoline-powered car. Students learn the basics of building a cost model, making assumptions, and confronting uncertainty through scenario analysis with a spreadsheet. The second component looks at convenience by asking the question, “Can I get there from here?”. In so doing, it introduces the correspondence between maps and graphs, relates graph connectivity to vehicle range, and explores locating charging stations to ensure that feasible routes exist. This module is appropriate for mathematics classes or other types of classes that address technology in society, business, or life skills.
Heart Transplants and the NFL Draft
When a group of people must decide on whom to select out of a group of eligible candidates, how do they decide? Who should have input into the decision? Given all the people eligible for a heart transplant how do you decide who gets one? Given all the people eligible to be CEO for a company, how do you decide? How does a professional sports team choose a player in the draft and how does a player maximize his position? How does the NFL promote fairness among teams? The students develop ranking procedures for both heart transplantation and the NFL draft. They examine the similarities and the differences, and they look at difficulties unique to each context. They consider how to the measure “success” of their rankings, and compare various alternatives based on spreadsheets and solutions from other members of their class. This module is appropriate for mathematics, computer science, and social studies classes in grades 9-12.
This module uses networks that are familiar to students (such as phone and Internet) to motivate modelng capacity and demand in other settings, such as school hallways, using simple networks. It concentrates more on allowing students to experiment with and think about networks and network capacity, rather than describing the algorithms used to determine optimal network settings or behavior. Students simulate the likelihood of congestion delay using rolls of dice (and later Excel spreadsheets) to consider issues of capacity when constructing networks and/or routes. Students come to understand the difference between average and peak demand and the costs associated with adding new capacity. As students run simulations many times, and as they look at more complex simulations, they see the essential role that computers play in this approach. This module is appropriate for mathematics and computer science classes grades 11-12.
Tomography: A Geometric and Computational Approach
Tomography is the science of examining internal structure with external measurements. Most people think of tomography in the context of medical testing, such as CT scans, but tomography can be used any time it is impossible to directly look inside something. Students tackle activities in which they are challenged to determine what is inside some object. They study how CT scan images of an object are created using 3-D reconstruction of 2-D slices of the object using shadows, pin prints, graphs, and more. The main questions of the module are: How can 3-D images be created from 2-D images (i.e. slices) of it?; How much computational power and skill are required to do these reconstructions; and what do they depend on? This module is appropriate for high school classes in computer science, mathematics, biology, environmental science, and physics.
Cryptography: Lqwurgxfwlrq wr Fubswrjudskb (Cryptography: Introduction to Cryptography)
The purpose of this module is to introduce students and teachers to the theory and practice of cryptography. As this is a vast subject with numerous applications, any introduction necessarily has to be brief and must concentrate on a few jewels of the subject; we have chosen to emphasize RSA because of the richness of the mathematics and the importance of its applications. More material and exercises are included than can be covered in one week in order to allow teachers flexibility in terms of topics and depths. In particular, the homework problems range from straightforward calculations to some very challenging exercises (included for advanced students).
Fair and Stable Matching
In 1998, the National Resident Match Program changed how they match medical students with hospitals for their residencies. Motivating this change was a concern about fairness. This module looks at a variety of different types of matching problems and discusses the properties that are desirable in each case. Students learn about the classic Gale Shapley algorithm as a means of understanding the notion of stability and fairness as two such desiderata. They discuss how to measure fairness in problem instances that admit multiple stable matchings. Through several prompts, students are motivated to define and compute several different measures of fairness and to compare and contrast their various definitions of fairness. The module concludes by presenting recent results from the research literature that show a surprising convergence of a local measure of fairness, that considers each individual’s median level of satisfaction, with a global measure of fairness based on the median distance measured within a partially ordered set defined on the set of stable matchings.
Polynomiography: Visual Displays of Solutions to Polynomial Equations
This mathematically inspired computer medium is based on algorithmic visualizations of one of the most basic and fundamental tasks in sciences and mathematics: solving a polynomial equation. Polynomiography has numerous applications in education, computer science, mathematics, fine arts, and design. It helps student to think about why (since antiquity) solving for the unknown in a polynomial equation has remained such a difficult task, why we need algorithmic methods to do it, and whether they can be approximate or must be exact. With the increasing role of visual tools and technologies, the search for these solutions introduces a striking appreciation of the connections between creativity in art and the intrinsic beauty of science and mathematics. Students are able to visually discover the Fundamental Theorem of Algebra, symmetry in shapes, the concept of iteration in science and nature, the notion of convergence, sensitivity of solutions as data parameters change. Students are encouraged to structure their own investigations with the module and to share their images and discoveries through social networking.
The Analysis of Games
Connect Four is a popular sequential game played on a 6x7 grid. Players take turns dropping red or black checkers into the tops of columns, where they fall to the lowest unoccupied space in the column. The first player to get four of their colored checkers to line up vertically, horizontally, or diagonally wins. A draw occurs when all 42 spaces are filled without a winner. It is a game with simple rules and can be demonstrated easily in a classroom. With multiple sets of Connect Four and groups of four, students can experiment with winning strategies. For instance, is possible to find an algorithm to produce perfect play from any configuration (even if mistakes have already been made)? This is always possible with a powerful enough computer, by checking all the positions. However, students are encouraged to find efficient algorithms that will work on computers readily available. Students consider what an algorithm is, what it means to be efficient, and they develop strategies to solve connect four from different vantage points.
Competition or Collusion? Game Theory in Sports, Business, and Life
Rock, paper, or scissors? Fastball or curveball? Bluff or fold? Work together or backstab the competition? Game theory offers a computational approach to decision-making in competitive situations between “players” who are each choosing from a variety of possible strategies. While recreational games and sports are natural examples, game theory is also effective in modeling business decisions, political campaigns, biological evolution, and decisions in many other real-life contexts. This module introduces students to game theory concepts and methods, starting with zero-sum games and then moving on to non-zero-sum games. Students learn techniques for classifying games, for computing optimal solutions where known, and for analyzing various strategies for games in which no optimal solution exists. Finally, students have the opportunity to transfer what they’ve learned to new game-theoretic situations. This module is appropriate for high schools classes in mathematics, computer science, and economics.
Gently Down the Stream: The Mathematics of Streaming Information
This module introduces students to the issues, methods, and challenges in successfully transmitting information. Topics include error detection, error correction, data authentication, data compression, and efficient transmission. This module could be used in a number of different classes in grades 9-12, many of which may have the flexibility in curriculum to incorporate nonstandard materials. Potential target classrooms are those that discuss technology in society, especially those in computer science, business, or mathematics.
Recursion can be used in many areas, from modeling population growth or the spread of disease to determining how much money you will have in an account at retirement. The purpose of this module is to provide a general background on the process of recursion, a method for solving problems where the solution to a problem depends on solutions to smaller instances of the same problem. A recursive process is one in which objects (a whole system) are defined in terms of other objects (stages of the system) of the same type. The whole system can be built knowing only a few initial values or stages of the system and applying a small set of rules. Computers routinely use recursion in performing many standard operations or processes. Recursion is a fundamental topic in computing. While this module could be used in a number of different classes with the flexibility in curriculum to incorporate nonstandard materials, it is probably best suited to those in computer science or mathematics.