Physics 234 – Winter 2010

Previous iterations of this course: [ Winter 2009 ]

Course outline

Introductory Computational Physics
Lecture: CAB 239 MWF 12:00–12:50
Lab (section H31): CEB 324 T 14:00–16:50
Lab (section H71): CEB 324 R 14:00–16:50
Syllabus: pdf
Schedule: pdf

An old version of Numerical Recipes, the recommended text, is freely available online. The newest version makes the jump from C to C++.

Grades

Your final grade will be determined using the weights listing in the course syllabus:

Assignments	25%
Lab test	15%
Midterm exam	20%
Final exam	40%

Please click here to view your your individual marks. As usual, these are tabulated according to the last three digits of your student ID number. The final two columns represent your final grade and your rank in the class of 52 students.

Other resources

• You should be working your way through the class notes. These will be updated regularly. Make sure you try to solve all the programming exercises.
• Many of the lecture topics are covered in greater detail in various textbooks. I encourage you to at least peruse items 1–3 of this book list.
• A famous article: David Goldberg, “What Every Computer Scientist Should Know About Floating-Point Arithmetic,” ACM Computing Surveys 23, 5 (1991). [ pdf : html ]
• Project Euler has many interesting numerical problems that you should be able to solve with a short C++ program.

Lectures

Class starts on Wednesday, January 6. Hope to see you there.

1. Wednesday, January 6: outline + introductory remarks
2. Friday, January 8: number representations, basic types
3. Monday, January 11: literals, objects, scope/duration
4. Wednesday, January 13: functions, argument passing, overloading, prototypes
5. Friday, January 15: multiple files, default arguments, C Standard Library, casting + handed out Exercise 1
6. Monday, January 18: operators, operation counting, control structures
7. Wednesday, January 20: control structures, scope
8. Friday, January 22: arrays and pointers, C strings, C++ strings
9. Monday, January 25: const correctness, streams, command line arguments
10. Wednesday, January 27: memory allocation, mathematical vectors and matrices
11. Friday, January 29: matrix multiplication, command line arguments, function arguments
12. Monday, February 1: histograms, sampling continuous distributions
13. Wednesday, February 3: floating-point representations
14. Friday, February 5: representation error
15. Monday, February 8: floating-point operations, propagation of errors
16. Wednesday, February 10: accumulation, pairwise summation, avoiding overflow, testing for equality
17. Monday, February 22: machine epsilon, numerical differentiation, Richardson extrapolation
18. Wednesday, February 24: root finding, bisection, Newton-Raphson, and secant methods
19. Friday, February 26: Horner's scheme, synthetic division, Cauchy's bound
20. Wednesday, March 3: sequences and series: truncation, extrapolation, resummation, and acceleration
21. Friday, March 5: residuals, rate of convergence of iterative methods, curve fitting with linear cofficients, Runge's phenomenon, minimizing goodness-of-fit, linear regression
22. Monday, March 8: polynomial fitting, Lagrange interpolation, Neville's algorithm, splines (linear, quadratic, and cubic), spline length and curvature
23. Wednesday, March 10: uncertainties in curve fitting, analytical bounds, jack-knife analysis, bootstrapping
24. Friday, March 12: minimizing interpolation error, Chebyshev nodes, integrating polynomial interpolants, quadrature, Romberg integration
25. Monday, March 15: random numbers, Monte Carlo integration
26. Wednesday, March 17: ordinary differential equations, iterative methods (Euler, Picard, Runge-Kutta)
27. Friday, March 19: integrating Newton's equations, special case of elastic spheres falling under gravity, conservation laws (Euler versus Euler-Cromer)
28. Monday, March 22: extremization/optimization, connection to root finding, steepest descent/ascent, extremization in higher dimensions
29. Wednesday, March 24: Worked examples related to Newton's method, line search and conjugate gradient techniques for optimization
30. Friday, March 26: Composite objects in C++: structures and classes, how to build a matrix class
31. Monday, March 29: Fourier transforms and spectral methods, Danielson-Lanczos lemma, Fast Fourier Transform (FFT) algorithms
32. Wednesday, March 31: Lab Test review
33. Wednesday, April 7: Solutions to linear algebraic equations, LU decomposition, tridiagonal systems, iterative refinement, LAPACK
34. Friday, April 9: Exam review
35. Monday, April 12: Symmetry of physical laws, connection between symmetry-breaking and long-range order, thermodynamic limit, implication for computer simulations, finite-size scaling

Labs

Labs start either Tuesday, January 12 or Thursday, January 14, depending on your section. Detailed instructions on accessing the lab are provided here.

1. Introduction to UNIX, BASH, and C++
   instructions [ pdf ]
2. Working with columnar data files in gnuplot
   instructions [ pdf ], source code [ tar.gz ]
3. C++ streams, convergence of series expansions, numerical estimates of π
   instructions [ pdf ], source code [ tar.gz ]
4. Practice with C arrays: histograms and linear algebra
   instructions [ pdf ], source code [ tar.gz ]
5. Combinatorics: electronic transitions in hydrogen, addition of quantum angluar moment
   instructions [ pdf ], source code [ tar.gz ]
6. Heron's method and series expansion for roots
   instructions [ pdf ], source code [ tar.gz ]
7. Floating-point arithmetic, high-precision accumulation
   instructions [ pdf ], source code [ tar.gz ]
8. Interpolation and extrapolation
   instructions [ pdf ], source code [ tar.gz ]
9. Pseudo-random numbers, Monte Carlo integration
   instructions [ pdf ], source code [ tar.gz ]
10. Steepest descent optimization, least squares fitting
    instructions [ pdf ], source code [ tar.gz ]
11. ODE solving, Newtonian mechanics
    instructions [ pdf ], source code [ tar.gz ]

Assignments

During the term, you will be asked to turn in five program files selected from Labs 2–10. These constitute the five Assignments for this course. As an incentive to complete all the questions in each Lab, you will not always know in advance which program is earmarked for grading. Assignments and their due dates will be announced during Lectures.

To submit your work, use the submit234 script. Please include your name and lab section as a comment at the top of the file. You are free to resubmit as many times as you like up until the deadline. Only the most recent submission will be graded. Be aware that the submission script may fail if any of the directories in your current path contain spaces.

$ cd Lab?
$ ls mycode.cpp
mycode.cpp
$ head -n2 mycode.cpp
// Assignment ? (Lab ?)
// Student Name (Tuesday/Thursday section)
$ submit234 mycode.cpp

Exercises

These (ungraded) Exercises are not programming-related. They consist of pencil-and-paper problems designed to help you master the numerical analysis material covered in this course.

1. Integer represenations
   problems [ pdf ], solutions [ pdf ]
2. Floating-point represenations
   problems [ pdf ], solutions [ pdf ]

Midterm

We have an in-class midterm scheduled for Friday, February 12. You will be evaluated only on your knowledge of basic C++ syntax. An excellent study resource is this online tutorial. Be sure that you can correctly answer all of the following sample questions:
practice questions [ pdf ], solutions [ pdf ]
2009 midterm exam [ pdf ], solutions [ pdf ]

It may also be helpful to review the solutions to Labs 1–4.

Update: Your test papers have been graded and will be handed back in class on Monday, February 22. Individual results are available here, indexed by the last three digits of your student ID. The performance of the class as a whole was lower than I had expected. The midterm may have been slightly harder than last year's.
midterm exam [ pdf ], solutions [ pdf ]

The class average was 11.2/20 (56%). Approximate letter grade ranges (based on the standard distribution for 2nd year classes) are indicated on the histogram above.

Lab test

The lab test will take place on Tuesday, April 6 and Thursday, April 8 during the regularly scheduled lab periods. You will be given 2½ hours to solve several simple numerical problems using C++ (in combination with any BASH or UNIX command-line tools you like). The expectation is that you are now capable of writing small programs from scratch under reasonable time constraints without the coaching of your peers or the teaching assistants.

The problems you'll have to solve are not particularly challenging. The purpose of this test is to evaluate your acquisition of basic scientific programming skills. If you have taken the time to work through the labs (independently and carefully), you should do well. It may also be helpful to try your hand at solving these sample questions:
practice lab test [ pdf ], solutions [ pdf : tar.gz ]
2009 lab test [ pdf ], solutions [ pdf : tar.gz ]

To attempt the lab test, you will need a valid userID (of the form p234u1xx) and password for the computer lab in CEB 324. You should also be familiar enough with the environment on those machines to launch a BASH shell, to edit .cpp files using your favourite text editor, and to and compile them with g++.

Update: All the test papers have been graded. Individual results are available here, indexed by the last three digits of your student ID. The second column is the number of correct answers (/5) on your test paper; the third column is the final rescaled grade (/15) that includes partial marks awarded for your code submission. My solutions are posted below.
Tuesday lab test [ pdf ], solutions [ pdf : tar.gz ]
Thursday lab test [ pdf ], solutions [ pdf : tar.gz ]

The class average was 9.5/15 (63%). Approximate letter grade ranges (based on the standard distribution for 2nd year classes) are indicated on the histogram above.

Final exam

The final exam is scheduled for Thursday April 22 during the hours 14:00–17:00 in our usual lecture room, CAB 239. It will cover material drawn from Lectures 12–29 and Labs 3–11. And at least one question will touch on matrix representations, as discussed in Lectures 10, 11, and 33.

The exam is closed book. Students may bring to the exam one 8.5"×11" cheat sheet, written on both sides. Calculators are not permitted.

As preparation for the final, I suggest going through the Exercises, the examples worked out in class, and last year's final exam. But don't just focus on reproducing the calculations: be sure that you understand the concepts involved.
practice exam questions [ pdf ], partial solutions [ pdf ]
2009 final exam [ pdf ], solutions [ pdf ]

Update: Your final exam papers have been graded.

The class average was 19.4/40 (48%). Approximate letter grade ranges (based on the standard distribution for 2nd year classes) are indicated on the histogram above.