Navigation

General Information

The Physiqual is a qualifying examination in the Computer Science Department covering a wide range of topics focused on applied mathematics and the physical world. A student must choose and complete one of the following tracks to pass the Physiqual. Each track is composed up of five sections. For each section, the candidate may take the relevant course(s) and receive a grade of A- or better. Make sure to notify Ronald Fedkiw if you do so. Alternatively, the student may approach the examiner listed under "Contacts" to schedule a block of time for an exam. We request that you do not discuss an exam that you have taken with any other student who has yet to take that section (as they may choose the same examiner who may use the same questions). After completing an exam section, have your examiner email fedkiw@cs.stanford.edu with the results. Be sure to CC Verna Wong on all communications to be able to track your progress.

Tracks

Of the following five tracks, any may be taken to complete the Physiqual.

Traditional

  • Applied Mathematics (CS205a)
  • Computational Geometry (CS268)
  • Computer Graphics (CS348b)
  • Computer Vision (CS231a)
  • Robotics (CS223a)

Visual Computing

  • Applied Mathematics (CS205a)
  • Computational Geometry (CS268)
  • Convex Optimization (CS334a)
  • Computer Graphics (CS348b)
  • Computer Vision (CS231a)

Robotics/Vision

  • Applied Mathematics (CS205a)
  • Computational Geometry (CS268)
  • Convex Optimization (CS334a)
  • Computer Vision (CS231a)
  • Robotics (CS223a)

Machine Learning

  • Applied Mathematics (CS205a)
  • Computational Geometry (CS268)
  • Convex Optimization (CS334a)
  • Machine Learning (CS229)
  • Robotics (CS223a) OR Computer Vision (CS231a)

Computational Geometry

  • Applied Mathematics (CS205a)
  • Computational Geometry (CS268)
  • Convex Optimization (CS334a)
  • Geometric Modeling and Processing (CS348a)
  • Geometric and Topological Data Analysis (CS233)

Section Reading Lists

Applied Mathematics (CS205a)

From: Scientific Computing: An Introductory Survey, Second edition,
Author: Michael T. Heath, McGraw Hill, 2002.
  1. Scientific Computing (1.1-1.3)
  2. Systems of Linear Equations (2.1-2.6)
  3. Linear Least Squares (3.1-3.7)
  4. Eigenvalue Problems (4.1-4.7)
  5. Nonlinear Equations (5.1-5.6)
  6. Optimization (6.1-6.7)
  7. Interpolation (7.1-7.4)
  8. Numerical Integration and Differentiation (8.1-8.7)
  9. Initial Value Problems for Ordinary Differential Equations ( 9.1-9.3)
  10. Boundary Value Problems for Ordinary Differential Equations ( 10.1-10.7)
  11. Partial Differential Equations (11.1-11.6)
  12. Fast Fourier Transform (12.1-12.4)
  13. Random Numbers and Stochastic Simulation (13.1-13.4)
From: Numerical Linear Algebra
Author: L. N. Trefethen and D. Bau, III, SIAM 1997
Pages: 1-47, 77-85, 181-193 (69 total).
  • 1. Fundamental
    • 1. Matrix Vector Multiplication
    • 2. Orthogonal Vectors and Matrices
    • 3. Norms
    • 4. The Singular Value Decomposition
    • 5. More on the SVD
  • 2. QR Factorization and Least Squares
    • Projection
    • 11. Least Squares Problems (skip section on QR factorization on page 83)
  • 5. Eigenvalues
    • 24. Eigenvalue Problems
    • 25. Overview of Eigenvalue Algorithms (stop on page 193, just before "The Two Phases of Eigenvalue Computations")
From: Practical Optimization,
Author: Gill, W. Murray, and M. H. Wright, Academic Press, 1993
Pages: 59-154 (96 total).
  • 3. Optimality Conditions
    • 4.1 Methods for Univariate Functions
    • 4.2 Methods for Multivariate Non-Smooth Functions
    • 4.3 Methods for Multivariate Smooth Functions
    • 4.4 Second Derivative Methods
    • 4.5 First Derivative Methods
    • 4.6 Non-Derivative Methods for Smooth Functions
    • 4.7 Methods for Sums of Squares
    • 4.8 Methods for Large-Scale Problems

Computational Geometry (CS268)

From: Computational Geometry, Algorithms and Applications,
Author: M. De Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf,
Pages: 19-248, 289-304 (246 pages total) [[but omit all *'ed sections, page count about 210]].
  • 2. Line Segment Intersection
    • 2.1. Line Segment Intersection
    • 2.2. The Doubly-Connected Edge List
    • 2.3. Computing the Overlay of Two Subdivisions
    • 2.4. Boolean Operations
  • 3. Polygon Triangulation
    • 3.1, Guarding and Triangulations
    • 3.3. Partitioning a Polygon into Monotone Pieces
    • 3.4. Triangulating a Monotone Polygon
  • 4. Linear Programming
    • 4.1. The Geometry of Casting
    • 4.2. Half-Plane Intersection
    • 4.3. Incremental Linear Programming
    • 4.4. Randomized Linear Programming
    • 4.5. Unbounded Linear Programs
  • 5. Orthogonal Range Searching
    • 5.1. 1-Dimensional Range Searching
    • 5.2. Kd-Trees
    • 5.3. Range Trees
    • 5.4. Higher-Dimensional Range Trees
    • 5.5. General Sets of Points
  • 6. Point Location
    • 6.1. Point Location and Trapezoidal Maps
    • 6.2. A Randomized Incremental Algorithm
    • 6.3. Dealing with Degenerate Cases
  • 7. Voronoi Diagrams
    • 7.1. Definition and Basic Properties
    • 7.2. Computing the Voronoi Diagram
  • 8. Arrangements and Duality
    • 8.1. Computing the Discrepancy
    • 8.2. Duality
    • 8.3. Arrangements of Lines
    • 8.4. Levels and Discrepancy
  • 9. Delaunay Triangulations
    • 9.1. Triangulations of Planar Point Sets
    • 9.2. The Delaunay Triangulation
    • 9.3. Computing the Delaunay Triangulation
    • 9.4. The Analysis
  • 10. More Geometric Data Structures
    • 10.1. Interval Trees
    • 10.2. Priority Search Trees
    • 10.3. Segment Trees
  • 11. Convex Hulls
    • 11.1. The Complexity of Convex hulls in 3-Space
    • 11.2. Computing Convex Hulls in 3-Space
  • 14. Quad Trees
    • 14.1. Uniform and Non-Uniform Meshes
    • 14.2. Quadtrees for Point Sets
    • 14.3. From Quadtrees to Meshes

Convex Optimization (CS334a)

Convex Optimization,
Author: Stephen Boyd and Lieven Vandenberghe
Source: available at the Stanford bookstore and online here.

Machine Learning (CS229a)

CS229 Lectures Notes,
Author: Andrew Ng
Source: online here.

Computer Vision (CS231a)

Introductory Techniques for 3-D Computer Vision
Author: E. Trucco and A. Verri, Prentice Hall, 1998,
Pages: 15-278 (253 total).
  • 2. Digital Snapshots
    • 2.1. Introduction
    • 2.2. Intensity Images
    • 2.3. Acquiring Digital Images
    • 2.4. Camera Parameters
    • 2.5. Range Data and Range Sensors
  • 3. Dealing with Image Noise
    • 3.1. Image Noise
    • 3.2. Noise Filtering
  • 4. Image Features
    • 4.1. What are Image Features?
    • 4.2. Edge Detection
    • 4.3. Point Features: Corners
    • 4.4. Surface Extraction from Range Images
  • 5. More Image Features
    • 5.1. Introduction: Line and Curve Detection
    • 5.2. The Hough Transform
    • 5.3. Fitting Ellipses to Image Data
    • 5.4. Deformable Contours
    • 5.5. Line Grouping
  • 6. Camera Calibration
    • 6.1. Introduction
    • 6.2. Direct Parameter Calibration
    • 6.3. Camera Parameters from the Projection Matrix
    • 6.4. Concluding Remarks
  • 7. Stereopsis
    • 7.1. Introduction
    • 7.2. The Correspondence Problem
    • 7.3. Epipolar Geometry
    • 7.4. 3-D Reconstruction
  • 8. Motion
    • 8.1. Introduction
    • 8.2. The Motion Field of Rigid Objects
    • 8.3. The Notion of Optical Flow
    • 8.4. Estimating the Motion Field
    • 8.5. Using the Motion Field
    • 8.6. Motion-based Segmentation

Robotics (CS223a)

From: Robot Motion Planning,
Author: J.C. Latombe, Kluwer Academic Publishers, 1991,
Pages: 3-54 (52 pages total).
  • Chapter 1. Introduction and Overview
    • 1. Aspects of Motion Planning
    • 2. Basic Problem
    • 3. Configuration Space Formulation
      • 3.1. Notion of Configuration Space
      • 3.2. Notion of a Path
      • 3.3. Obstacles in Configuration Space
      • 3.4. Translational Case
    • 4. Planning Approaches
      • 4.1. Roadmap
      • 4.2. Cell Decomposition
      • 4.3. Potential Field
      • 4.4. Global vs. Local Method
    • 5. Extensions of the Basic Problem
      • 5.1. Multiple Moving Objects
        • Moving Obstacle
        • Multiple Robots
        • Articulated Robots
      • 5.2. Kinematic Constraints
        • Holonomic Constraints
        • Nonholonomic Constraints
      • 5.3. Uncertainty
      • 5.4. Movable Objects
    • 6. Computational Complexity
    • 7. Reduction of Complexity
      • 7.4. Focusing Attention on a Subset of the Workspace
    • 8. Relation to Other Problems
      • 8.1. Interaction with Real-Time Motion Control
      • 8.2. Interaction with Sensing
      • 8.3. Interaction with Task-Level Planning
    • 9. Literature Landmarks
From: Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces,
Author: L.E. Kavraki, P. Svestka, J.C. Latombe, and M. Overmars. IEEE Transactions on Robotics and Automation, 12(4):566-580, 1996.
Source: http://robotics.stanford.edu/~latombe/pub.html#C (27 pages).

From: Introduction to Robotics,
Author: Oussama Khatib and Krasimir Kolarov – Lecture Notes (CS223A)
Source: available at the Stanford bookstore.
  • 1. Spatial Description
    • 1.1. Manipulator Structure
    • 1.2. Transformations
    • 1.3. Configuration Representations
  • 2. Direct Kinematics
    • 2.1. Introduction
    • 2.2. Link Description
    • 2.3. Conventions for the First and Last Link
    • 2.4. Attaching Frames to Links
    • 2.5. Propagation of Frames
    • 2.6. Kinematics of Manipulators
    • 2.7. Direct Kinematics
  • 3. Inverse Kinematics
    • 3.1. Introduction
    • 3.2. Closed Form Solutions
    • 3.3. Pieper’s Solution
    • 3.4. Existence of Solution
    • 3.5. Workspace of the Manipulator
    • 3.6. Number of Solutions
  • 4. The Jacobian
    • 4.1. Introduction
    • 4.2. Differential Motion
    • 4.3. Basic Jacobian
    • 4.4. Linear/Angular Motion
    • 4.5. Combined Linear and Angular Motion
    • 4.6. Jacobian: Velocity Propagation
    • 4.7. Jacobian: Explicit Form
    • 4.8. Kinematic Singularities
    • 4.9. Jacobian at Wrist/EndEffector
    • 4.10.Static Forces
    • 4.11.More on Explicit Form: Jv
  • 5. Dynamics
    • 5.1. Introduction
    • 5.2. Newton-Euler Formulation
    • 5.3. Lagrange Formulation
  • 6. Trajectory Generation
    • 6.1. Introduction
    • 6.2. Joint Space vs. Cartesian Space
    • 6.3. Path Planning With Polynomial Trajectories
    • 6.4. Planning With Intermediate Points
    • 6.5. Straight Paths With Parabolic Blends
    • 6.6. Generalized Path Planning
  • 7. Manipulator Control
    • 7.1. Introduction
    • 7.2. Passive Natural Systems
    • 7.3. Passive-Behavior Control
    • 7.4. Disturbance Rejection
    • 7.5. Actuation System
    • 7.6. PD Control for Multi-Link Systems
    • 7.7. Operational Space Control

Computer Graphics (CS348b)

From: CS348a course reader
Source: available at the Stanford bookstore.
  • Handout 15. The Polar Forms of Polynomial Curves
  • Handout 16. Modeling Smooth Curved Shapes
  • Handout 17. Cubic Parameteric Curves
  • Handout 18. Spline Curves
  • Handout 19. Joints and Splines via Polar Forms
  • Handout 20. B-splines
  • Handout 21. Rational Curves; Tensor Product Surfaces
  • Handout 22. Total Degree Surfaces
From: Computer Graphics, Principles and Practice,
Author: J. D. Foley, A. van Dam, S. K. Feiner, and J. F. Hughes,
Addison-Wesley, 1990, Pages: 563-604 and 648-757 (149 pages total)
  • Gray-Scale and Color
  • 15. Visible Surface Determination
  • 16. Illumination and Shading
From: Radiosity and Realistic Image Synthesis,
Author: M. F. Cohen and J. R. Wallace, Academic Press, 1993,
Pages: 13-130 (118 pages total)
  • 2. Rendering Concepts (by Pat Hanrahan)
  • 3. Discretizing the Rendering Equation
  • 4. The Form Factor
  • 5. Radiosity Matrix Solutions

Geometric Modeling and Processing (CS348a)

CS348a Course Reader,
Author: Leonidas Guibas
Source: available at the Stanford bookstore.

Geometric and Topological Data Analysis (CS233)

CS233 Assigned Readings,
Author: Multiple
Source: online here.

Contacts

Potential examiners for each area include:

Applied Mathematics

Computational Geometry

Convex Optimization

Machine Learning

Computer Vision

Robotics

Computer Graphics

Geometric Modeling and Processing

Geometric and Topological Data Analysis