Mathematics topics for computer science majors

Please edit and add a * where you agree with the topic. Also add new topics that have not been included.

Our criteria for inclusion? Topics that we believe are important for the undergraduate education of computer science majors. Appropriate topics might be chosen because they are necessary preparation for required and elective courses or because they are expected by graduate programs where our students may apply.

If you believe a topic is optional, please put a ? next to it.

I have not checked carefully for duplicates.

We do not necessarily have to group the topics into course units at this time. It is most important to get the list of topics that we want.

To add an item to the list, just start the line with three blank spaces and then * To indent the item as a subtopic of another, start the line with 6 blank spaces, then *

I am making a starter list from materials we have had during our meetings. Red text is from the CC2001 Body of Knowledge. Bold is from the Core Material in blue represents edits by Bill F.

• Propositions, Conditional Propositions
• Quantifiers, nested quantifiers
• Methods of proofs
• Mathematical induction
• Sets
• Functions
• Sequences and sums
• Recurrence relations
• 2nd order [linear] recurrence relations
• Matrices
• Relations
• Equivalence relations
• Basic principles of counting
• Permutations and combinations
• Binomial coefficients
• Probability (Discrete Probabiliy)
• Random variable, expected value, variance, and standard deviation
• Graphs
• Paths and cycles, connectivity
• Euler and Hamilton cycles and paths
• Shortest paths
• Planar graphs, 4-color theorem
• Free trees, spanning trees, MST (Trees)
• Ordered trees, binary trees
• Vectors in R^n
• Algebra of matrices
• Systems of linear equations
• Vector spaces
• Linear transformations
• Determinants
• Eigenvalues and eigenvectors
  • Eigenvalues and dynamical systems
  • Finding (approximating) the principle eigenvalue

Topics from the Calculus book by Hughes-Hallett, Gleason, McCallum, et al

• Functions
  • Functions and change
  • Exponential Functions
  • Logarithmic functions
  • Trigonometric functions
  • Powers, polynomials, and rational functions
  • Continuity
• The Derivative
  • The derivative at a point
  • The derivative function
  • Interpretations of the derivative
  • The second derivative
  • Differentiability
• Short-cuts to differentiation
  • Powers and polynomials
  • The exponential function
  • The product and quotient rules
  • The chain rule
  • The trigonometric functions
  • The chain rule and inverse functions
  • Linear approximation and the derivative
  • Theorems about differentiable functions
• Using the derivative
  • Using first and second derivatives
  • Families of curves
  • Optimization
  • Applications to marginality
  • Optimization and modeling
  • Rates and related rates
  • L'Hopital's rule, growth and dominance
  • Parametric equations
• The Definite Integral
  • The definite integral
  • The fundamental theorem and interpretations
  • Theorems about definite integrals
• Constructing antiderivatives
  • Antiderivatives graphically and numerically
  • Constructing antiderivatives analytically
  • Differential equations
  • Second fundamental theorem of calculus
  • The equations of motion
• Integration
  • Integration by substitution
  • Integration by parts
  • Tables of integrals ??
  • Approximation errors and Simpson's rule
  • Improper integrals
• Using the definite integral
  • Applications to economics
  • Distribution functions
  • Probability, mean, [variance,] and median
• Sequences and Series
  • Sequences
  • Geometric series
  • Convergence of series
  • Tests for convergence
  • Power series and interval of convergence
• Approximating functions using series
  • Taylor poynomials
  • Taylor series
  • Finding and using Taylor series
  • The error in Taylor polynomial approximations
  • Fourier series
• Differential equations
  • What is a differential equation?
  • Slope fields
  • Euler's method
  • Separation of variables
  • Growth and decay
  • Applications and modeling
  • Models of population growth
  • Systems of differential equations
  • Analyzing the phase plane
  • Second-order differential equations
• Roots, accuracy and bounds
• Complex numbers
• Newton's method

And topics not from the book that should be included in our calculus offering

• Functions of several variables (several = two)
  • Domain, contour lines, and graphs
  • Partial derivatives
  • Critical points, relative extrema, and saddle points
  • Derivation of coefficients for the least squares line of best fit
  • Chain rule for several variables, directional derivatives, gradient

Other things that have come up

• Summations
• Limits
• Dot Products
• Graphing functions
• Matrix operations
• Vector operations
• Error propagation
• Numerical methods
  • Solution of nonlinear equations
  • Numerical differentiation
  • Numerical integration
  • Numerical solution of o.d.e's - Euler and Runge-Kutta methods
  • Error of approximation - truncation error, round-off error, propagation error
  • Curve-fitting - least squares, splines, Chebyshev polynomials
  • Finite element method
  • Fast Fourier transform
• Functions of several variables
• Mathematical modeling
• Information theory
• Logic
• Recurrence relations

From Giorgi at the beginning of our discussions. He included two versions of the topics for a course in logic:

TRADITIONAL

• 1. Propositional (Boolean) logic, its semantics (truth tables etc.)

and proof theory (axiomatizations, sequent systems, natural deduction systems).

• 2. Predicate (first-order) logic (quantifiers, etc.). Again, semantics

and proof theory.

• 3. Applied formal systems based on first-order logic, such as set

theory and number theory.

• 4. Godel's incompleteness theorems. These are just as important and

relevant to CS as the existence of undecidable problems taught in every Theory of Computability course. It is a shame that very few CS students have even heard about Godel's theorems.

• 5. Certain advanced topics, time permitting.

COMPUTER SCIENCE ORIENTED: The more CS-ORIENTED version, in addition to the above (with the depth of the above somewhat reduced to free up time), may include:

• 6. Logic-based programming languages, such us Prolog or Datalog.
• 7. The resolution and unification methods, on which the compilers of the above are heavily based.
• 8. Logics of knowledge and action, used in AI.
• 9. As an experiments, some elements of my "computability logic" could also be included, very carefully. The latter is an attempt to turn logic from a formal theory of truth into a formal theory of computability.
• 10. There are many other interesting topics that may vary from semester to semester.

to top