Web Page

The class web page is located at http://www.cs.iastate.edu/~cs577/. You are suggested to check the web page on a daily basis for announcements regarding homeworks, exams, and other information.

Introduction and Objective

This course covers selected topics in algorithms, applied mathematics, and geometry that have found applications in areas such as geometric modeling, graphics, robotics, vision, human machine interface, speech recognition, computer animation, etc. The need for such a course is manifested by the nature of interdisciplinary work that draws upon techniques and expertise across different fields and by the importance of facilitating technical communication and idea exchange among computer scientists and engineers.

The course objective is to teach computer science and engineering students problem solving skills. Through the course study the students are expected to become acquainted with a set of powerful mathematical and computational tools, and moreover, to achieve certain understanding of their applications in the real world. In addition, the course strives to keep a sound balance between programming and analytical problem solving.

Computer science students have been trained primarily in discrete mathematics and algorithms but tend to lack understanding of continuous methods which are more and more present in the aforementioned applied areas. Meanwhile, engineering students are familiar with continuous methods but often short of necessary background in algorithm design for computer simulation of control and mechanical systems. The introduction of this course expects to address such issues and prepare the students for applied research and/or practice.

More specifically, the following topics will be covered in the course:

1. Projective Geometry & Transformations
   • homogeneous coordinates
   • plane & space transformations
   • perspective projection
   • quaternions & rotation sequences
2. Differential Geometry
   • parametric curves
   • curvature and torsion (Frenet formulas)
   • algebraic curves
   • surfaces
   • principal & Gaussian curvatures
3. Root Finding
   • nonlinear equations
   • linear equations (singular value decomposition)
   • polynomials
   • polynomial evaluation & multiplication (FFT)
4. Approximation
   • data fitting (least squares)
   • orthogonal polynomials
   • trigonometric polynomials (Fourier transform)
5. Optimization
   • linear programming
   • nonlinear optimization
   • Lagrange multipliers
   • calculus of variations

The course is intended for graduate students and undergraduate seniors in Computer Science and Mathematics as well as Electrical and Computer Engineering, Mechanical Engineering, HCI, Bioinformatics, and other engineering fields.

(i) Com S 228, (ii) Com S 330 or Cpr E 310, (iii) Math 166 and 307 (or 317); or consent from the instructor

Evaluation

A certain level of self-study is required. You are expected to pursue ideas and topics discussed in this course on your own beyond the lectures.

Regular assignments will be handed out to the students. Such assignments entail solving some problems on paper or implementing some of the algorithms discussed in the course.

For graduate credit, the student needs to complete an essay on some additional topic assigned by the instructor or self-chosen with the instructor's approval. The essay should either address some issue (such as the robustness of a numerical algorithm) that complements a lecture topic or branch out to an advanced topic (such as surface curvatures) not covered in the lectures. The essay will require 20 to 30 hours of self-study and writing and make up 10% of the total graduate grade.

Grades will be on the following scales:

	Homeworks	Midterm	Final	Essay
Undergrad	40%	30%	30%
Grad	36%	27%	27%	10%

Your final grade will be decided by the following grading scale subject to minor adjustments:

---

at least 85                             A
at least 80 but less than 85    A-
at least 75 but less than 80    B+
at least 70 but less than 75    B
at least 65 but less than 70    B-
at least 60 but less than 65    C+
at least 55 but less than 60    C
at least 50 but less than 55    C-
at least 47 but less than 50    D+
at least 43 but less than 47    D
at least 40 but less than 43    D-
less than 40                           F

---

 

The following books are on 2-hour-reserve:

1. W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery. Numerical Recipes in C++: The Art of Scientific Computing, 2nd edition, Cambridge University Press, 2002.

2. S. D. Conte and C. de Boor. Elementary Numerical Analysis: An Algorithmic Approach. McGraw-Hill, 3rd edition, 1980.

3. D. G. Luenberger. Introduction to Linear and Nonlinear Programming. Addison-Wesley, 1984.

4. D. Marsh. Applied Geometry for Computer Graphics and CAD. Springer-Verlag, 1999.

5. A. Pressley. Elementary Differential Geometry. Springer-Verlag, 2001.

6. J. B. Kuipers. Quaternions and Rotation Sequences. Princeton University Press, 1999.

Other reference books include:

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press and McGraw-Hill, 2nd edition, 2001.

2. B. O'Neill. Elementary Differential Geometry. Academic Press, Inc., 2nd edition, 1997.

3. G. Strang. Introduction to Applied Mathematics. Wellesley-Cambridge Press, 1986.

4. V. Chvátal. Linear Programming. W. H. Freeman and Company, 1983.

5. I. M. Gelfand and S. V. Fomin. Calculus of Variations. Dover Publications, Inc., 2000.

6. G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, 1983.

7. N. Gershenfeld. The Nature of Mathematical Modeling. Cambridge University Press, 1999.

8. J. Gallier. Geometric Methods and Applications for Computer Science and Engineering. Springer-Verlag, 2001.

By appointment. You can answer any questions that you may have regarding lecture material, exams or homework.

If you have questions with short answers or you cannot attend any of the office hours, alternatively, you can e-mail jia@cs.iastate.edu .

Disabilities for Special Accommodations

If you have a documented disability and anticipate needing accommodations in this course, please make arrangements to meet with me soon. Please request that a Disability Resources staff send a SAAR (Student Academic Accommodation Request) form verifying your disability and specifying the accommodation you will need.

Academic Honesty

In this course, you may discuss assignments with other students. (Do not assume this is true in all your courses!) We expect you to think through and fully understand assignment solutions. Thus, the solutions you turn in must be written based on your own understanding. Plagiarism will be dealt with harshly. You should consult the University Policy for details regarding academic misconduct and its consequences.