PHYSIQUAL 2006-2007

GENERAL INFORMATION:

The Physiqual is a qualifying examination in the Computer Science Department covering the areas of applied mathematics, computational geometry, computer graphics, computer vision, and robotics. The exam is offered once a year in the Spring quarter. The Physiqual is divided into two distinct, but equally important sections: an oral part covering the above five areas and a research presentation.

The Oral Exam

For each section of the exam, the examiners with expertise in that area are listed below. The student is responsible for approaching one of the potential examiners and scheduling a 30 minute block of time for the exam - although the exam may be as short as 15 minutes. The examiner will ask a sequence of questions covering a particular area. The scheduling may happen at any time during the Spring quarter, but via the honor code 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. Once all 5 sections have been completed you will get your overall results.

The possible grades for each area of the exam are pass, marginal pass and fail. A grade of at least marginal pass is required in each area to pass the first portion of the examination. However, if the candidate receives a fail in one or more areas, the student must retake those sections as well as those for which a marginal pass was received. The candidate must wait until the following Spring quarter to retake any required portions of the exam. Sections for which a pass grade is earned never need to be taken again. To satisfy the oral examination requirement in a given area, the student has the option of taking the relevant course(s) and receiving a grade of A- or better. The relevant courses are:

• Applied Mathematics: CS237a and CS237c
• Computational Geometry: CS268
• Computer Graphics: CS348a,
• Computer Vision: CS223b
• Robotics: CS223a and CS326.

• Numerical Analysis: Ron Fedkiw, Gene Golub
• Computational Geometry: Leo Guibas, Vladlen Koltun
• Computer Graphics: Pat Hanrahan, Marc Levoy
• Computer Vision: Sebastian Thrun
• Robotics: Oussama Khatib, Jean-Claude Latombe

The Research Presentation Exam

The paper presentation consists of the assignment of three or four papers on a research area, selected by the student's adviser. Within a period of a month, the student is expected to prepare a written report on the assigned papers and then make an oral presentation on their content in front of a three-person committee including the student's adviser. The student is responsible for forming the oral committee and for scheduling the date and room of the oral presentation.

This portion of the qual is very important. It is the student's chance to put together a potential reading committee, potential letter writers, etc. early in his/her career and develop contacts which they will hopefully maintain to the benefit of both people.

If you have further questions, contact Ron Fedkiw.

Instruction for taking the exam

You should submit your name to both Kathi DiTomasi and Ron Fedkiw letting them know your intention to take the exam by the first day of Spring quarter. Please include the name of your adviser in the email.

Reading List:

I. Applied Mathematics

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)

• 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")

• 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

II. Computational Geometry

• 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

III. Computer Graphics

• 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

• Gray-Scale and Color
• 15. Visible Surface Determination
• 16. Illumination and Shading

• 2. Rendering Concepts (by Pat Hanrahan)
• 3. Discretizing the Rendering Equation
• 4. The Form Factor
• 5. Radiosity Matrix Solutions

IV. Computer Vision

• 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

V. Robotics

• 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

• 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