PHYSIQUAL 2012-2013

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.

NOTE: Starting with Fall 2010 admits, there is no longer a Research Presentation portion of the Physiqual, and the THESIS PROPOSAL needs to be taken instead. Fall 2009 and earlier admits may have done the Research Presentation, which can be used in place of the THESIS PROPOSAL. Since the quals are supposed to have been completed in 3 years, the Physiqual no longer offers the Research Proposal component. If you were admitted in Fall 2009 or before and did not yet do the Research Presentation because you are behind on your quals, you *must* take the THESIS PROPOSAL option ---- but we recommend that your advisor and the admin staff waive the 9 month before graduating requirement.

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: CS205a
• Computational Geometry: CS268
• Computer Graphics: CS348b
• Computer Vision: CS231a
• Robotics: CS223a

• Numerical Analysis: Ron Fedkiw
• Computational Geometry: Leo Guibas
• Computer Graphics: Pat Hanrahan, Marc Levoy
• Computer Vision: Fei-Fei Li, Marc Levoy
• Robotics: Oussama Khatib

Instructions for taking the exam

You should submit your name to both Verna Wong 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