CPSC 212 Algorithms / Data Structures

Schedule

DateL#Topic
Thu. Aug.24 01 Introduction; course overview; hand out paper; problem demo
Tue. Aug.29 02 Go over paper & problem; identify key components
Phase I: Tangent Plane Estimation
Phase Ia: 2d point class: assignment: provide 2d point class implementation
Suggested code:
Thu. Aug.31 03 More on 2d point class
  • sorting points (using STL sort)
  • functors [p.34]
  • calculating averge
Tue. Sep.05 04 Principal Components Analysis (PCA): eigenvalues and eigenvectors Phase Ib: matrix class: assignment: provide matrix class implementation
Suggested code:
Thu. Sep.07 05 More on PCA, matrix
  • finding eigenvalues/eigenvectors
  • jacobi() (from Numerical Recipes)
  • matrix class [p.38]
  • templates
  • templated friends
Tue. Sep.1206 Guest lecture: Dr. Malloy, C++
Thu. Sep.14 07 Nbhd(xi): kd-trees and k-nn queries; see the wikipedia entry
Phase Ic: kdtree class: assignment: provide kdtree class implementation
Suggested code:
Tue. Sep.19 08 More on kd-trees [p.549]
Thu. Sep.21 09 Phase I wrapup
Phase Id: 3D classes: assignment: provide 3d class implementations for point, kdtree, matrix
Suggested data and output:
Tue. Sep.2610 Guest lecture: TBA
Thu. Sep.28 11 Algorithm analysis
Tue. Oct.03 12 Sorting
Thu. Oct.05 13 Priority queues (min heaps: sorted list, binheap [p.215])
Phase II: Consistent Tangent Plane Orientation
Phase IIa: binheap class: assignment: provide binheap class implementation
Suggested code:
Tue. Oct.10 14 Priority queues (binomial queue, fibheap)
Thu. Oct.12 15 Phase I due
Graph algorithms
Tue. Oct.17 16 Graph representation (Vertex node, Graph class)
Thu. Oct.19 17 Prim's MST algorithm
Phase IIb: graph class & Prim's algorithm: assignment: provide graph class implementation with Prim's MST
Tue. Oct.24 18 Depth-first and breadth-first search tree traversals
Thu. Oct.26 19 Phase III: Signed Distance Function
Tue. Oct.3120 Review of solution to Prim's algorithm
Thu. Nov.0221 Meet in lab
Tue. Nov.07-- Fall Break
Thu. Nov.0922 Meet in lab
Tue. Nov.1423 Meet in lab
Phase II due at end of class time
Thu. Nov.16 24 Phase III: Signed Distance Function (code)
Tue. Nov.2125 Meet in lab
Thu. Nov.23-- Thanksgiving
Tue. Nov.2826 Meet in lab
Phase III due at end of class time
Thu. Nov.30 27 Phase IV: Contour Tracing
Tue. Dec.0528 Meet in lab
Marching cubes cont'd
Thu. Dec.0729 Meet in lab
Phase IV due at end of class time
Sat. Dec.0930 FINAL EXAM: 8:00am-11:00am