SECTION 111.46. Discrete Mathematics for Problem Solving, Adopted 2013 (One-Half to One Credit)

(a) General requirements. Students shall be awarded one-half to one credit for successful completion of this course. Prerequisite: Algebra II.

(b) Introduction.

(1) The desire to achieve educational excellence is the driving force behind the Texas essential knowledge and skills for mathematics, guided by the college and career readiness standards. By embedding statistics, probability, and finance, while focusing on fluency and solid understanding, Texas will lead the way in mathematics education and prepare all Texas students for the challenges they will face in the 21st century.

(2) The process standards describe ways in which students are expected to engage in the content. The placement of the process standards at the beginning of the knowledge and skills listed for each grade and course is intentional. The process standards weave the other knowledge and skills together so that students may be successful problem solvers and use mathematics efficiently and effectively in daily life. The process standards are integrated at every grade level and course. When possible, students will apply mathematics to problems arising in everyday life, society, and the workplace. Students will use a problem-solving model that incorporates analyzing given information, formulating a plan or strategy, determining a solution, justifying the solution, and evaluating the problem-solving process and the reasonableness of the solution. Students will select appropriate tools such as real objects, manipulatives, paper and pencil, and technology and techniques such as mental math, estimation, and number sense to solve problems. Students will effectively communicate mathematical ideas, reasoning, and their implications using multiple representations such as symbols, diagrams, graphs, and language. Students will use mathematical relationships to generate solutions and make connections and predictions. Students will analyze mathematical relationships to connect and communicate mathematical ideas. Students will display, explain, or justify mathematical ideas and arguments using precise mathematical language in written or oral communication.

(3) In Discrete Mathematics for Problem Solving, students are introduced to the improved efficiency of mathematical analysis and quantitative techniques over trial-and-error approaches to management problems involving organization, scheduling, project planning, strategy, and decision making. Students will learn how mathematical topics such as graph theory, planning and scheduling, group decision making, fair division, game theory, and theory of moves can be applied to management and decision making. Students will research mathematicians of the past whose work is relevant to these topics today and read articles about current mathematicians who either teach and conduct research at major universities or work in business and industry solving real-world logistical problems. Through the study of the applications of mathematics to society's problems today, students will become better prepared for and gain an appreciation for the value of a career in mathematics.

(4) Statements that contain the word "including" reference content that must be mastered, while those containing the phrase "such as" are intended as possible illustrative examples.

(c) Knowledge and skills.

(1) Mathematical process standards. The student uses mathematical processes to acquire and demonstrate mathematical understanding. The student is expected to:

(A) apply mathematics to problems arising in everyday life, society, and the workplace;

(B) use a problem-solving model that incorporates analyzing given information, formulating a plan or strategy, determining a solution, justifying the solution, and evaluating the problem-solving process and the reasonableness of the solution;

(C) select tools, including real objects, manipulatives, paper and pencil, and technology as appropriate, and techniques, including mental math, estimation, and number sense as appropriate, to solve problems;

(D) communicate mathematical ideas, reasoning, and their implications using multiple representations, including symbols, diagrams, graphs, and language as appropriate;

(E) create and use representations to organize, record, and communicate mathematical ideas;

(F) analyze mathematical relationships to connect and communicate mathematical ideas; and

(G) display, explain, and justify mathematical ideas and arguments using precise mathematical language in written or oral communication.

(2) Graph theory. The student applies the concept of graphs to determine possible solutions to real-world problems. The student is expected to:

(A) explain the concept of graphs;

(B) use graph models for simple problems in management science;

(C) determine the valences of the vertices of a graph;

(D) identify Euler circuits in a graph;

(E) solve route inspection problems by Eulerizing a graph;

(F) determine solutions modeled by edge traversal in a graph;

(G) compare the results of solving the traveling salesman problem (TSP) using the nearest neighbor algorithm and using a greedy algorithm;

(H) distinguish between real-world problems modeled by Euler circuits and those modeled by Hamiltonian circuits;

(I) distinguish between algorithms that yield optimal solutions and those that give nearly optimal solutions;

(J) find minimum-cost spanning trees using Kruskal's algorithm;

(K) use the critical path method to determine the earliest possible completion time for a collection of tasks; and

(L) explain the difference between a graph and a directed graph.

(3) Planning and scheduling. The student uses heuristic algorithms to solve real-world problems. The student is expected to:

(A) use the list processing algorithm to schedule tasks on identical processors;

(B) recognize situations appropriate for modeling or scheduling problems;

(C) determine whether a schedule is optimal using the critical path method together with the list processing algorithm;

(D) identify situations appropriate for modeling by bin packing;

(E) use any of six heuristic algorithms to solve bin packing problems;

(F) solve independent task scheduling problems using the list processing algorithm; and

(G) explain the relationship between scheduling problems and bin packing problems.

(4) Group decision making. The student uses mathematical processes to apply decision-making schemes. The student analyzes the effects of multiple types of weighted voting and applies multiple voting concepts to real-world situations. The student is expected to:

(A) describe the concept of a preference schedule and how to use it;

(B) explain how particular decision-making schemes work;

(C) determine the outcome for various voting methods, given the voters' preferences;

(D) explain how different voting schemes or the order of voting can lead to different results;

(E) describe the impact of various strategies on the results of the decision-making process;

(F) explain the impact of Arrow's Impossibility Theorem;

(G) relate the meaning of approval voting;

(H) explain the need for weighted voting and how it works;

(I) identify voting concepts such as Borda count, Condorcet winner, dummy voter, and coalition; and

(J) compute the Banzhaf power index and explain its significance.

(5) Fair division. The student applies the adjusted winner procedure and Knaster inheritance procedure to real-world situations. The student is expected to:

(A) use the adjusted winner procedure to determine a fair allocation of property;

(B) use the adjusted winner procedure to resolve a dispute;

(C) explain how to reach a fair division using the Knaster inheritance procedure;

(D) solve fair division problems with three or more players using the Knaster inheritance procedure;

(E) explain the conditions under which the trimming procedure can be applied to indivisible goods;

(F) identify situations appropriate for the techniques of fair division;

(G) compare the advantages of the divider and the chooser in the divider-chooser method;

(H) discuss the rules and strategies of the divider-chooser method;

(I) resolve cake-division problems for three players using the last-diminisher method;

(J) analyze the relative importance of the three desirable properties of fair division: equitability, envy-freeness, and Pareto optimality; and

(K) identify fair division procedures that exhibit envy-freeness.

(6) Game (or competition) theory. The student uses knowledge of basic game theory concepts to calculate optimal strategies. The student analyzes situations and identifies the use of gaming strategies. The student is expected to:

(A) recognize competitive game situations;

(B) represent a game with a matrix;

(C) identify basic game theory concepts and vocabulary;

(D) determine the optimal pure strategies and value of a game with a saddle point by means of the minimax technique;

(E) explain the concept of and need for a mixed strategy;

(F) compute the optimal mixed strategy and the expected value for a player in a game who has only two pure strategies;

(G) model simple two-by-two, bimatrix games of partial conflict;

(H) identify the nature and implications of the game called "Prisoners' Dilemma";

(I) explain the game known as "chicken";

(J) identify examples that illustrate the prevalence of Prisoners' Dilemma and chicken in our society; and

(K) determine when a pair of strategies for two players is in equilibrium.

(7) Theory of moves. The student analyzes the theory of moves (TOM). The student uses the TOM and game theory to analyze conflicts. The student is expected to:

(A) compare and contrast TOM and game theory;

(B) explain the rules of TOM;

(C) describe what is meant by a cyclic game;

(D) use a game tree to analyze a two-person game;

(E) determine the effect of approaching Prisoners' Dilemma and chicken from the standpoint of TOM and contrast that to the effect of approaching them from the standpoint of game theory;

(F) describe the use of TOM in a larger, more complicated game; and

(G) model a conflict from literature or from a real-life situation as a two-by-two strict ordinal game and compare the results predicted by game theory and by TOM.

Source Note: The provisions of this §111.46 adopted to be effective August 25, 2014, 38 TexReg 9027