Theory of Computing Appendix C

The structures within the discipline, the historical roots and evolving nature of mathematics, and the interaction between technology and the discipline.

Graded homework problems build from the basic models of computation to the more complex ones following the historical development of the models.

Facilitating the building of student conceptual and procedural understanding.

Homework problems deal with using regular expressions, finite automata, transition graphs, context-free grammars and Turing machines as tools for developing algorithms that solve problems.

Helping all students build understanding of the discipline including:

. Confidence in their abilities to utilize mathematical knowledge.

. Awareness of the usefulness of mathematics.

. The economic implications of fine mathematical preparation.

Problems on context-free languages assess student's understanding of how mathematics provides ways to precisely describe the syntax of programming languages. Problems on Turing machines assess student's understanding of how mathematics provides tools for developing computer algorithms.

Exploring, conjecturing, examining and testing all aspects of problem solving.

In solving homework problems that require constructing regular expressions or context-free grammars for a language students must consider and test a variety of forms. The same conjecturing and testing is done as machines are developed to recognize a given language.

Formulating and posing worthwhile mathematical tasks, solving problems using several strategies, evaluating results, generalizing solutions, using problem solving approaches effectively, and applying mathematical modeling to real-world situations.

Since the course looks at how to model computation, answers to exam questions and homework require presenting solutions to a given problem using more than one method. For example, they must construct both a finite automata and a regular expression to describe a language. Problems also deal with how to describe a complicated language by using descriptions of parts of the language.

Making convincing mathematical arguments, framing mathematical questions and conjectures, formulating counter-examples, constructing and evaluating arguments, and using intuitive, informal exploration and formal proof.

Homework problems and exam questions explain how a particular finite automata or regular expression solves a particular problem. These explanations involve both formal proofs and informal explanations of what the expressions and machines do.

Expressing ideas orally, in writing, and visually-, using mathematical language, notation, and symbolism; translating mathematical ideas between and among contexts.

Problems on homework and exams require the use of standard notation for regular expressions and context-free grammars. Additional problems require drawing finite automata and transition graphs.

Connecting the concepts and procedures of mathematics, drawing connections between mathematical strands, between mathematics and other disciplines, and with daily life.

Homework and exam problems that analyze and construct Turing machines show the connection between mathematics and computer science. Construction of context-free grammars and syntax trees in problems link programming languages to mathematics.

Selecting appropriate representations to facilitate mathematical problem solving and translating between and among representations to explicate problem-solving situations.

Assigned problems allow students to show they understand the circumstances under which regular expressions, finite automata and transition graphs are appropriate alternatives for representing a language. Additional problems test students understanding of the process of normalizing context-free grammars and the advantages in doing the normalization.

Mathematical processes including:

. Problem solving.

. Communication.

. Reasoning and formal and informal argument.

. Mathematical connections.

. Representations.

. Technology.

Many assigned problems test students' ability to develop the appropriate expression, model or grammar. Both formal and informal techniques need to be used to explain the correctness of the expression, model or grammar.

Number operations and relationships from both abstract and concrete perspectives identifying real world applications, and representing and connecting mathematical concepts and procedures including:

. Number sense.

. Set theory.

. Number and operation.

. Composition and decomposition of numbers, including place value, primes, factors, multiples, inverses, and the extension of these concepts throughout mathematics.

. Number systems through the real numbers, their properties and relations.

. Computational procedures.

. Proportional reasoning.

. Number theory.

N/A

Mathematical concepts and procedures, and the connections among them for teaching upper level number operations and relationships including:

. Advanced counting procedures, including union and intersection of sets, and parenthetical operations.

. Algebraic and transcendental numbers.

. The complex number system, including polar coordinates.

. Approximation techniques as a basis for numerical integration, fractals, and numerical-based proofs.

. Situations in which numerical arguments presented in a variety of classroom and real-world situations (e.g., political, economic, scientific, social) can be created and critically evaluated.

. Opportunities in which acceptable limits of error can be assessed (e.g., evaluating strategies, testing the reasonableness of results, and using technology to carry out computations).

N/A

Geometry and measurement from both abstract and concrete perspectives and to identify real world applications, and mathematical concepts, procedures and connections among them including:

. Formal and informal argument.

. Names, properties, and relationships of two- and three-dimensional shapes.

. Spatial sense.

. Spatial reasoning and the use of geometric models to represent, visualize, and solve problems.

. Transformations and the ways in which rotation, reflection, and translation of shapes can illustrate concepts, properties, and relationships.

. Coordinate geometry systems including relations between coordinate and synthetic geometry, and generalizing geometric principles from a two-dimensional system to a three-dimensional system.

. Concepts of measurement, including measurable attributes, standard and non-standard units, precision and accuracy, and use of appropriate tools.

. The structure of systems of measurement, including the development and use of measurement systems and the relationships among different systems. Measurement including length, area, volume, size of angles, weight and mass, time, temperature, and money.

. Measuring, estimating, and using measurement to describe and compare geometric phenomena.

. Indirect measurement and its uses, including developing formulas and procedures for determining measure to solve problems.

N/A

Mathematical concepts, procedures, and the connections among them for teaching upper level geometry and measurement including:

. Systems of geometry, including Euclidean, non-Euclidean, coordinate, transformational, and projective geometry.

. Transformations, coordinates, and vectors and their use in problem solving. Three-dimensional geometry and its generalization to other dimensions. Topology, including topological properties and transformations.

. Opportunities to present convincing arguments by means of demonstration, informal proof, counter-examples, or other logical means to show the truth of statements and/or generalizations.

N/A

Statistics and probability from both abstract and concrete perspectives and to identify real world applications, and the mathematical concepts, procedures and the connections between them including:

. Use of data to explore real-world issues.

. The process of investigation including formulation of a problem, designing a data collection plan, and collecting, recording, and organizing data.

. Data representation through graphs, tables, and summary statistics to describe data distributions, central tendency, and variance.

. Analysis and interpretation of data.

. Randomness, sampling, and inference.

. Probability as a way to describe chances or risk in simple and compound events.

. Outcome prediction based on experimentation or theoretical probabilities.

N/A

Mathematical concepts, procedures, and the connections among them for teaching upper level statistics and probability including:

. Use of the random variable in the generation and interpretation of probability distributions.

. Descriptive and inferential statistics, measures of disbursement, including validity and reliability, and correlation.

. Probability theory and its link to inferential statistics.

. Discrete and continuous probability distributions as bases for inference.

. Situations in which students can analyze, evaluate, and critique the methods and conclusions of statistical experiments reported in journals, magazines, news media, advertising, etc.

N/A

Functions, algebra, and basic concepts underlying calculus from both abstract and concrete perspectives and to identify real world applications, and the mathematical concepts, procedures and the connections among them including:

. Patterns.

. Functions as used to describe relations and to model real world situations.

. Representations of situations that involve variable quantities with expressions, equations and inequalities and that include algebraic and geometric relationships.

. Multiple representations of relations, the strengths and limitations of each representation, and conversion from one representation to another.

. Attributes of polynomial, rational, trigonometric, algebraic, and exponential functions.

. Operations on expressions and solution of equations, systems of equations and inequalities using concrete, informal, and formal methods.

. Underlying concepts of calculus, including rate of change, limits, and approximations for irregular areas.

N/A

Mathematical concepts, procedures, and the connections among them for teaching upper level functions, algebra, and concepts of calculus including:

. Concepts of calculus, including limits (epsilon-delta) and tangents, derivatives, integrals, and sequences and series.

. Modeling to solve problems.

. Calculus techniques including finding limits, derivatives, integrals, and using special rules.

. Calculus applications including modeling, optimization, velocity and acceleration, area, volume, and center of mass.

. Numerical and approximation techniques including Simpson's rule, trapezoidal rule, Newton's Approximation, and linearization.

. Multivariate calculus.

. Differential equations.

N/A

Discrete processes from both abstract and concrete perspectives and to identify real world applications, and the mathematical concepts, procedures and the connections among them including:

. Counting techniques.

. Representation and analysis of discrete mathematics problems using sequences, graph theory, arrays, and networks.

. Iteration and recursion.

Homework and exam problems on finite automata and transition graphs use graph theory representations. How Turing machines model iteration and recursion is assessed in other such problems.

Mathematical concepts, procedures, and the connections among them for teaching upper level discrete mathematics including:

. Topics, including symbolic logic, induction, linear programming, and finite graphs.

. Matrices as a mathematical system, and matrices and matrix operations as tools for recording information and for solving problems.

. Developing and analyzing algorithms.

N/A