Physics 234 – Winter 2011

Previous iterations of this course: [ Winter 2009 : Winter 2010 ]

Course outline

Introductory Computational Physics
Lecture: T 193 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

Grades

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

Quizzes	5%
Assignments	20%
Lab test	15%
Midterm exam	20%
Final exam	40%

Please click here to view your individual marks, tabulated according to the last three digits of your student ID number. (A dash indicates that no quiz or assignment was turned in.) The rightmost two columns represent your final numerical grade (as a percentage) and your rank in the class of 44 students.

Textbooks

There is no required textbook for this course. For the most part, students will work from class notes and exercises that will be available online.

Nonetheless, I make two recommendations in the syllabus—the first for students who do not have a strong C programming background and the second for students who are looking to invest in a valuable reference text:

• C++ Primer Plus, 5th Ed., Steven Prata, Sams (2004).
  ISBN-10: 0672326973 [ amazon.ca : google books : U of A bookstore ]
• Numerical Recipes: The Art of Scientific Computing, 3rd Ed., W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Cambridge University Press (2007).
  ISBN-10:0521880688 [ amazon.ca : google books]

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

Other resources

• There is a reasonably good C++ tutorial posted at cplusplus.com.
• Project Euler has many interesting numerical problems that you should be able to solve with a short C++ program. These are great practice problems.
• A famous article: David Goldberg, “What Every Computer Scientist Should Know About Floating-Point Arithmetic,” ACM Computing Surveys 23, 5 (1991). [ pdf : html ]
• Some additional information (from Bjarne Stroustrup, the creator of C++) on C++0x, which has just been ratified as C++ 2011. The new language specification contains many exciting, long-awaited features.

Exercises

These (ungraded) Exercises are not C++-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 (try at least problems 1 and 2)
   problems [ pdf ], solutions [ pdf ]
2. Iterative methods and approximating functions
   problems [ pdf ], solutions [ pdf ]
3. Packed storage schemes for matrices and efficent evaluation of arithmetic expressions
   problems [ pdf ], solutions [ pdf ]
4. Significant digits in floating-point, finite differences, Richardson extrapolation
   problems [ pdf ], solutions [ pdf ]
5. Root finding, finite differences
   problems [ pdf ]

Quizzes

There will be about ten 5-minute quizzes during the term, the top five of which will count toward your grade. These quizzes amount to only 5% of your total grade, so they're not a big part of my evaluation of your perfomance. But they are a wonderful tool for self-evaluation: please use them to diagnose weak spots in your understanding of the material.

1. Unsigned binary and two's complement, octal and hexadecimal
   quiz [ pdf ], solutions [ pdf ]
2. C++ syntax, loop control structures, object scope
   quiz [ pdf ], solutions [ pdf ]
3. Packed storage for a symmetric, band-diagonal matrix
   quiz [ pdf ], solutions [ worked out during Lecture 13 ]
4. Floating-point numbers
   quiz [ pdf ], solutions [ pdf ]
5. Root finding and finite differences
   quiz [ pdf ], solutions [ pdf ]

7. Curve fitting, error estimates, and steepest descent
   quiz [ pdf ], solutions [ pdf ]
8. Monte Carlo integration
   quiz [ pdf ], solutions [ pdf ]

Lectures

Class starts on Monday, January 10. Hope to see you there.

1. Monday, January 10:
   This material was covered in the first lecture:
   • Phys 234 : Introductory Computational Physics
   • Introduction
   Please start working your way through these sections of the notes:
   • Interacting via the Terminal
   • UNIX Tools
   • The C++ Programming Language
   You may also want to read chapter 1 of Prata's book.
2. Wednesday, January 12:
   See the notes on Integer Representations + more on two's complement here and here
3. Friday, January 14:
   C++ integer types, size guarantees literals, casting, compiler, structure of a C++ program
   Read chapter 2 of Prata's book.
4. Monday, January 17::
   properties of objects, scope/duration, operators, operation counting, expression evaluation
   Read chapter 3 of Prata's book.
5. Wednesday, January 19:
   functions, default arguments, C standard library, passing arguments by value and by reference, overloading, casting of function arguments, properties of objects and functions, declaration versus definition, global variables
6. Friday, January 21:
   control structures, branching, logical skeletons of the looping structures, looping examples
   Read chapters 5 and 6 of Prata's book.
7. Monday, January 24:
   basic C++ syntax, control structure syntax, scope rules, streams, file streams
8. Wednesday, January 26:
   Limiting processes, sequences and series, truncation, extrapolation, sequence transformations
9. Friday, January 28:
   C arrays and pointers, C strings, C++ strings
   Read the relevant parts of chapters 4 and 7 in Prata's book.
10. Monday, January 31:
    const correctness, command line arguments, static versus dynamic memory, avoiding unnecessary storage
11. Wednesday, February 2:
    Read the lecture on arrays as vectors and matrices + the wiki articles on index notation, array data structure, row-major order, and packed matrix storage.
12. Friday, February 4:
    The lecture covered these topics: packed storage, complexity scaling of linear algebra operations, inverse and pseudo-inverse solutions to linear systems of equations, LU decomposition. You may want to have a look at the wiki entries on matrix multiplication, the Strassen and Coppersmith-Winograd algorithms, and the LU and Cholesky decomposition schemes.
13. Monday, February 7:
    recursive function definitions, functions as arguments, review of argument passing, function prototypes
14. Wednesday, February 9:
    physics in the continuum, distributions and their connection to histograms, selection and sampling
15. Friday, February 11:
    Midterm review

• Monday, February 14:
  Midterm exam

16. Wednesday, February 16:
    machine representations of integers and reals, fixed-point binary, floating-point numbers, organization of the bit patterns, denormalized numbers, special floating-point values + more on floating point representations here and here
17. Friday, February 18:
    representation errors, loss of significance
18. Monday, February 28:
    floating-point operations, propagation of errors, accumulation, pairwise summation, avoiding overflow, testing for equality
19. Wednesday, March 2:
    root finding, bisection method, Newton's method
20. Friday, March 4:
    Horner's scheme, polynomial division (deflation), sythetic division, Cauchy's bound, multiplicities, root finding algorithm
21. Wednesday, March 9:
    numerical differentiation, finite differences, Richardson extrapolation
22. Friday, March 11:
    curve fitting with linear coefficients, polynomial interpolation, Lagrange polynomials, Neville's algorithm
23. Monday, March 14:
    Uncertainties in curve fitting, interpolation error, Chebyshev nodes, splines
24. Wednesday, March 16:
    Quadratic splines of mimimum length and curvature, clamped and natural cubic splines, judging quality of fit (Jackknife and bootstrap analysis), fitting as a minimization procedure, nonlinear fits.
25. Friday, March 18:
    Numerical integration, Rhomberg's method, Guassian quadrature, handling singularities, pseudo-random numbers, Monte Carlo
26. Monday, March 21:
    Connection between root finding and extremum problems, steepest descent/ascent, extremization in higher dimensions
27. Wednesday, March 23:
    Worked examples of Newton's method in higher dimensions, line search and conjugate gradient methods, optimization in the linear algebra context, C++ structures and classes
28. Friday, March 25:
    Ordinary differential equations, iterative methods (Euler, Picard, Runge-Kutta)
29. Monday, March 28:
    Integrating Newton's equations, special case of elastic spheres falling under gravity, conservation laws (Euler versus Euler-Cromer)
30. Wednesday, March 30:
    Lab test review
31. Friday, April 1:
    Fourier transforms and spectral methods
32. Monday, April 4:
    
33. Wednesday, April 6:
    Symmetry of physical laws, connection between symmetry-breaking and long-range order, thermodynamic limit, implication for computer simulations, finite-size scaling
34. Friday, April 8:
    Exam review (?)
35. Monday, April 11:
    Eigenvalue problems, characteristic polynomial, power methods, LAPACK conventions
36. Wednesday, April 13:
    

Labs

Labs start either Tuesday, January 18 or Thursday, January 20, depending on your section. Detailed instructions on accessing the lab are provided here. An easy way to work outside of school (without either installing Linux on your home machine or logging in to our lab remotely) is to visit codepad.org. It provides a web interface for compilers in a variety of languages, C++ included. Check out this example.

The lead TA and grader for this course is Dr. Shohreh Abdolrahimi. If need be, you can reach her at . Aatif Butt will also be in the lab to help answer questions and troubleshoot your code. His email address is .

1. Introduction to UNIX, BASH, and C++; integer representations
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
2. Working with columnar data files in gnuplot
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
3. C++ streams, convergence of series expansions, numerical estimates of π
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
4. Combinatorics and linear algebra with C arrays
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
5. Distributions and histograms
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
6. Floating-point arithmetic, high-precision accumulation
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
7. Kepler's equations, root finding via Newton-Raphson
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
8. Interpolation and extrapolation
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
9. Steepest descent optimization, least squares fitting
   instructions [ pdf ], source code [ tar.gz ], solutions [ tar.gz ]
10. ODE solving, Newtonian mechanics
    instructions [ pdf ], source code [ tar.gz ], solutions [ 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.

1. Question 8 from Lab 2, due February 1/3
2. Question 7 from Lab 3, due February 8/10
3. Question 6 from Lab 5, due March 8/10
   And here's what your plot should look like:
   
4. Question 3 from Lab 7, due March 22/24
   Here are plots of the time evolution of distance and angle. These might help you debug your code:
   
5. Question 7 from Lab 9, due March 29/31

To submit your work, use the submit234 script. Please include your name and lab section as a comment at the top of the file, and be sure to name your file exactly as indicated in the lab instructions. 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 *.cpp *.gp
mycode.cpp   myscript.gp
$ head -n2 my*.{cpp,gp}
==> mycode.cpp <==
// Assignment ? (Lab ?)
// Student Name (Tuesday/Thursday section)
==> mycode.cpp <==
# Assignment ? (Lab ?)
# Student Name (Tuesday/Thursday section)
$ submit234 mycode.cpp
$ submit234 myscript.gp

Midterm

We have an in-class midterm scheduled for Monday, February 14. You will be evaluated primarily on your knowledge of basic C++'s syntax and type system. In addition to the online notes and the recommended text, you might want to use this online tutorial as a study resource. Also, have a go at these practice questions and the previous years' midterms:
practice questions [ pdf ], solutions [ pdf ]
2009 midterm exam [ pdf ], solutions [ pdf ]
2010 midterm exam [ pdf ], solutions [ pdf ]

It may also be helpful to review the solutions to the Quizzes, Exercises 1–3, and Labs 1–4.

Update: Your test papers have been graded and will be handed back in class on Wednesday, February 16. Individual results are available here, indexed by the last three digits of your student ID. Here are the exam and solutions.
2011 midterm exam [ pdf ], solutions [ pdf ]

The class average was 11.5/20 (57.5%). Approximate letter grade ranges (based on the standard distribution for 2nd year classes) are indicated on the histogram above. The performance of the class was as a whole was pretty typical.

Lab test

The lab test will take place on Tuesday, April 5 and Thursday, April 7 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 ]
2010 Tuesday lab test [ pdf ], solutions [ pdf : tar.gz ]
2010 Thursday 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: The lab test and solutions are posted below.
Tuesday lab test [ pdf ], solutions [ pdf : tar.gz ]
Thursday lab test [ pdf ], solutions [ pdf : tar.gz ]

The class average was 11.25/15 (75%). Approximate letter grade ranges (based on the standard distribution for 2nd year classes) are indicated on the histogram above. The performance of the class as a whole was quite good.

Final exam

The final exam is scheduled for Tuesday April 26 during the hours 14:00–17:00 in our usual lecture room, T 193. All the material we've covered is fair game, but the focus is less on C++ programming and more on numerical methods and analysis. The exam questions will mostly be drawn from Lectures 11–33, Labs 3–10, and the Quizzes and Exercises.

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 strongly suggest that students go through the Exercises and previous years' final exams. 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 ]
2010 final exam [ pdf ]