CPSC 212 Computer Science IV
(Data Structures and Algorithms)
Spring 2012
TTh 11:00—12:15 McAdams 119

URL: http://andrewd.ces.clemson.edu/courses/cpsc212/s12/

DateL#Topic
Thu. Jan.12
 01
  1. (§ 1.4) C++ class syntax
  2. (§ 1.4) public/private member fucntions, data members
  3. (§ 1.5) "the big three"
    (see also: C++ operator overloading guidelines)
  4. (§ 1.6.3, footnote 8, see also p.88) operator overloading, friend operator<<
See also: Makefiles
Tue. Jan.17
Lab 1: array_t 		02
  1. (§ 1.5.2) parameter passing
  2. (§ 1.4.2) const member function (accessor/mutuator)
  3. (§ 1.6.2) templates
Assignment 0: ray tracer
Thu. Jan.19
 03
  1. (§ 1.7.2, esp. last par.) operator[]
  2. (§ 2.1) Asymptotic function definitions, e.g., O(f(n))
  3. (§ 2.3) What to analyze
  4. (§ 2.4) Running time calculations
  5. (§ 1.2.5) Inductive proof
Tue. Jan.24
Lab 2: timer_t, bubblesort 		04
  1. (§ 1.2.5) Inductive proof
  2. Recurrence relations
    1. telescoping sum
    2. recurisve backsubstitution
  3. (§ 7.6.1) Mergesort analysis
  4. Handy formulae
Thu. Jan.26
 05
  1. (§ 7.7.5) Quicksort analysis (worst and best cases)
  2. (§ 3.3) STL vector and list (e.g., vector implementation of insertion sort)
DUE: Assignment 0 (at 23:59:59) Solution
Tue. Jan.31
Lab 3: quicksort 		06
  1. (§ 6.3) Binary Heap (using vector<T>)
    1. insert()
    2. deleteMin()
  2. C++ iostream including ifstream and ofstream; see the input/output with files tutorial
  3. A useful istream member: get
  4. A useful istream manipulator: ws
Assignment 1: parallelized ray tracer
Thu. Feb.02
 07
  1. vector and list in the STL
  1. (§ 3.3) vector and list
  1. (§ 3.3.1) Iterators
  2. (§ 3.5) list_t implementation
Tue. Feb.07

Lab 4: omp and img_t class 		08 Q & A
Thu. Feb.09
 09
  • list_t<pairs_t>  vs.   list_t<pairs_t* >
  • (§ 3.6) The Stack ADT
  • (§ 3.6.3) Applications: Postfix Expressions and Infix to Postfix Conversion
  • std::ostringstream, std::istringstream objects
DUE: Assignment 1 (at 23:59:59) Solution
Tue. Feb.14
Lab 5: binary heap 		10
  • (§ 4.1) Trees (common terms)
  • (§ 4.1.2) Traversals
  • (§ 4.2) Binary Trees
  • (§ 4.3) Binary Search Trees
  • (§ 4.3.1) contains
  • (§ 4.3.2) findMain, findMax
Assignment 2: ray tracer transmission
Thu. Feb.16
 11
  1. (§ 4.3.3) insert implementation
  2. (§ 4.3.4) remove (erase) implementation
  3. (§ 4.3.5) destructor and copy assignment operator
  4. (§ 4.6) tree traversals
Tue. Feb.21
Lab 6: list_t 		12
  1. (§ 4.4) AVL Trees
  2. (§ 4.4.1) single rotation
  3. (§ 4.4.2) double rotation
  4. Revision of text's AVL tree implementation
  5. AVL node insertion
  6. rotate_left and rotate_write redux
  7. AVL node deletion
  8. For comparison, see the Eternally Confuzzled - Red Black Tree Tutorial
Thu. Feb.23
 13 Quick Review
  1. C++
  2. Big-Oh
  3. Heaps
  4. Binary Trees
  5. AVL Trees
DUE: Assignment 2 (at 23:59:59) Solution
Tue. Feb.28
Lab 7: stack; infix notation 		14 Midterm Exam (C++, big-oh notation, heaps, AVL trees)
Assignment 3: AVL trees
Thu. Mar.01
 15
  1. (§ 5.1) Hashing
  2. (§ 5.2) Hash Function
  3. (§ 5.3) Separate Chaining
  4. (§ 5.4) Hash Tables Without Linked Lists
Tue. Mar.06
Lab 8: binary search trees I 		16 Graphs
  1. (§ 9) Graph definitions, representation
  2. Using the std::map<std::map< > >
  3. Using a node_t to represent a graph vertex
Thu. Mar.08 17
  1. (§ 9.3) Dijkstra's shortest path algorithm
  2. (§ 9.5) Prim's minimum spanning tree algorithm
DUE: Assignment 3 (at 23:59:59) Solution
Tue. Mar.13
Lab 9: binary search trees II 		18
  1. (§ 12.6) kd-trees
  2. (§ 1.6.4 and footnote at bottom of p.295) Function Objects (functors)
Assignment 4: photon emission
Thu. Mar.15
 19
  1. Qt
  2. Qt Docs
  3. Qt 4.6
Tue. Mar.20
 — Spring Break
Thu. Mar.22
 — Spring Break
Tue. Mar.27
Lab 10: Qt photon visualizer
Dr. D. away: ETRA
20 No class.
Thu. Mar.29

Dr. D. away: ETRA
21 No class.
Tue. Apr.03
Lab 11: kd-tree 		22
  1. (Figure 12.43, sort of) kd-tree insertion
  2. nn, knn, range queries
  3. wikipedia
  4. Thinh Nguyen's lecture
  5. Andrew Moore's tutorial

DUE: Assignment 4 (at 23:59:59) Solution
Assignment 5: Qt kd-tree
Thu. Apr.05
 23
  1. menubar signals/slots, kd-tree construction
  2. kd-tree rendering
  3. void GLTexobj::initializeGL()
  4. void GLTexobj::resizeGL()
  5. void GLTexobj::paintGL()
  6. void GLTexobj::mousePressEvent(QMouseEvent* e)
  7. void GLTexobj::mouseReleaseEvent(QMouseEvent* e) for queries
Tue. Apr.10
Lab 11: cont'd 		24 More on the kd-tree
  1. the function object point_c
  2. kd-tree insertion with min and max
  3. nn-query and knn-query details

Thu. Apr.12
 25 Photon mapping
  1. Step 1: Shoot photons
    1. scale power by 1/n
    2. find photon min, max (for kd-tree bounding volume)
    3. insert photons into kd-tree
  2. Step 2: Trace rays
    1. find closest object (as before)
    2. get surface material properties (as before)
    3. compute ambient color contribution (as before)
    4. compute diffuse reflection contribution (as before)
    5. compute specular reflection contribution (spawn reflection ray; as before)
    6. compute transmissive color contribution (spawn refraction ray; as before)
    7. compute specular highlight contribution (as before)
    8. compute photon power density (flux)
      1. knn query (k=20), get r
      2. for each photon accumulate flux
      3. add in scaled flux to color
Tue. Apr.17
Lab 12: Dijkstra's shortest path 		26 From C++ to Objective-C (see Pierre Chatelier's very well-written and useful document)
  1. main differences (dynamically allocated objects, no auto objects)
  2. member function calls' [] syntax
  3. class interface and implementation
  4. memory management (important!)
  5. inheritance, protocols
  6. code parallelization via omp
DUE: Assignment 5 (at 23:59:59) Solution
Assignment 6: photon mapper
Thu. Apr.19
 27 No class: Student Evaluations (online)
Tue. Apr.24
 28 Final Review
Thu. Apr.26
 29 No class: Reading Day
DUE: Assignment 6
Wed. May.02
 30 FINAL EXAM 3:00pm-5:30pm