Problem Solving Techniques for Applied Computer Science

COM S 477

Offered during Fall Semester each year.

  1. Credits and contact hours: 3 credits, 3 contact hours
  2. Instructor’s or course coordinator’s name: Yan-Bin Jia
  3. Text book, title, author, and year: None required
  4. Other supplemental materialsApplied Geometry for Computer Graphics and CAD, D. Marsh, 1999.; Elementary Differential Geometry, A. Pressley, 2001.; Elementary Differential Geometry, 2nd edition, B. O'Neill, 1997.; Optimal State Estimation, D. Simon, 2006.; Quaternions and Rotation Sequences, J.B. Kuipers; Calculus of Variations, I. M. Gelfand and S. V. Fomin, 2000.; Numerical Recipes in C++: The Art of Scientific Computing, 2nd edition, W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, 2002.; Elementary Numerical Analysis: An Algorithmic Approach, 3rd edition, S. D. Conte and C. de Boor, 1980.; Introduction to Linear and Nonlinear Programming, D. G. Luenberger, 1984.; Introduction to Algorithms, 2nd edition, T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, 2001.; Introduction to Applied Mathematics, G. Strang, 1986.; Linear Programming, V. Chvátal, 1983.; Matrix Computations, G. H. Golub and C. F. Van Loan, 1983.; Geometric Methods and Applications for Computer Science and Engineering, J. Gallier,  2001.

Specific course information

  1. Brief description of the content of the course: Selected topics in applied mathematics, algorithms, and geometry that have found applications in areas such as geometric modeling, graphics, robotics, vision, human machine interface, speech recognition, computer animation, etc. Homogeneous coordinates and transformations, perspective projection, rotations in space, quaternions, polynomial interpolation, roots of polynomials and polynomial systems, solution of linear and nonlinear equations, parametric and algebraic curves, curvature, torsion, Frenet formulas, surfaces, principal curvatures, Gaussian and mean curvatures, geodesics, approximation, Fourier series and fast Fourier transform, linear programming, data fitting, least squares, simplex method, nonlinear optimization, Lagrange multipliers, calculus of variations. Programming components. 
  2. Prerequisites or co-requisites: COM S 228, COM S 230 or CPR E 310, MATH 166, MATH 207 or MATH 317 or consent of the instructor
  3. Required, elective, or selected elective?   Selected Elective

Specific goals for the course

  1. Specific outcomes of instruction:
  • Students will learn powerful techniques used in applied areas such as geometric modeling, graphics, robotics, vision, etc. (1, 2)
  • Students will be able to implement the learned mathematical and modeling techniques to solve practical problems. (6)

Brief list of topics to be covered

  • Projective Geometry & Transformations
    • homogeneous coordinates
    • plane & space transformations
    • perspective projection
    • quaternions & rotation sequences
  • Differential Geometry
    • parametric curves
    • curvature and torsion (Frenet formulas)
    • surfaces
    • principal & Gaussian curvatures
    • geodesics
  • Computational Algebra & Root Finding
    • polynomial evaluation & multiplication (FFT)
    • polynomial interpolation
    • polynomial root finding
    • nonlinear equations
    • common roots of a system of polynomial (or nonlinear) equations
    • linear equations (singular value decomposition)
  • Approximation
    • data fitting (least squares)
    • trigonometric polynomials (Fourier transform)
  • Optimization
    • linear programming
    • nonlinear optimization
    • Lagrange multipliers
    • calculus of variations
  • Estimation/Filtering
    • probabilities
    • recursive least squares
    • Kalman filter