| Date | L# | Topic |
| Thu. Jan.13 |
01 |
[(§ 1.4)]
C++ class syntax
[(§ 1.4)]
public/private member fucntions, data members
[(§ 1.5)]
"the big three"
[(§ 1.6.3, footnote 8, see also p.88)]
operator overloading,
friend operator<<
|
Tue. Jan.18
Lab 1: array_t
|
02 |
[(§ 1.5.2)]
parameter passing
[(§ 1.4.2)]
const member function (accessor/mutuator)
[(§ 1.6.2)]
templates
Assignment 0: ray tracer
|
| Thu. Jan.20 |
03 |
[(§ 1.7.2, esp. last par.)]
operator[]
[(§ 2.1)]
Asymptotic function definitions, e.g., O(f(n))
[(§ 2.3)]
What to analyze
[(§ 2.4)]
Running time calculations
[(§ 1.2.5)]
Inductive proof
|
Tue. Jan.25
Lab 2: timer_t, bubblesort
|
04 |
[(§ 1.2.5)]
Inductive proof
- Recurrence relations
- telescoping sum
- recurisve backsubstitution
[(§ 7.6.1)]
Mergesort analysis
- Handy formulae
|
| Thu. Jan.27 |
05 |
[(§ 7.7.5)]
Quicksort
analysis (worst and best cases)
[(§ 3.3)]
STL vector and list
(e.g., vector implementation of insertion sort)
DUE: Assignment 0 (at 23:59:59)
Solution
|
Tue. Feb.01
Lab 3: quicksort
|
06 |
[(§ 6.3)]
Binary Heap (using vector<T>)
insert()
deleteMin()
- C++
iostream
including
ifstream
and
ofstream;
see the
input/output with files tutorial
- A useful
istream member:
get
- A useful
istream manipulator:
ws
Assignment 1: parallelized ray tracer
|
| Thu. Feb.03 |
07 |
vector and list in the STL
[(§ 3.3)]
vector and list
[(§ 3.3.1)]
Iterators
[(§ 3.5)]
list_t implementation
|
Tue. Feb.08
Lab 4: omp and img_t class
|
08 |
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
|
| Thu. Feb.10 |
09 |
[(§ 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
DUE: Assignment 1 (at 23:59:59)
Solution
|
Tue. Feb.15
Lab 5: binary heap
|
10 |
[(§ 4.3.3)]
insert implementation
[(§ 4.3.4)]
remove (erase) implementation
[(§ 4.3.5)]
destructor and copy assignment operator
[(§ 4.6)]
tree traversals
Assignment 2: ray tracer transmission
|
| Thu. Feb.17 |
11 |
[(§ 4.4)]
AVL Trees
[(§ 4.4.1)]
single rotation
[(§ 4.4.2)]
double rotation
- Revision of text's AVL tree implementation
- AVL node insertion
rotate_left and rotate_write
redux
- AVL node deletion
- For comparison, see the
Eternally Confuuzzed - Red Black Tree Tutorial
|
Tue. Feb.22
Lab 6: list_t
|
12 |
Quick Review
- C++
- Big-Oh
- Heaps
- Binary Trees
- AVL Trees
|
| Thu. Feb.24 |
13 |
Q & A
DUE: Assignment 2 (at 23:59:59)
Solution
|
Tue. Mar.01
Lab 7: stack; infix notation
|
14 |
Midterm Exam (C++, big-oh notation, heaps, AVL trees)
Assignment 3: AVL trees
|
| Thu. Mar.03 |
15 |
[(§ 5.1)]
Hashing
[(§ 5.2)]
Hash Function
[(§ 5.3)]
Separate Chaining
[(§ 5.4)]
Hash Tables Without Linked Lists
|
Tue. Mar.08
Lab 8: binary search trees I
|
16 |
Graphs
[(§ 9)]
Graph definitions, representation
- Using the
std::map<std::map< > >
- Using a
node_t to represent a graph vertex
|
| Thu. Mar.10 |
17 |
[(§ 9.3)]
Dijkstra's shortest path algorithm
[(§ 9.5)]
Prim's minimum spanning tree algorithm
DUE: Assignment 3 (at 23:59:59)
Solution
|
Tue. Mar.15
Lab 9: binary search trees II
|
18 |
[(§ 12.6)]
kd-trees
[(§ 1.6.4 and footnote at bottom of p.295)]
Function Objects (functors)
Assignment 4: photon emission
|
| Thu. Mar.17 |
19 |
[Qt]
[Qt Docs
][Qt 4.2
]
|
| Tue. Mar.22 |
— |
Spring Break
|
| Thu. Mar.24 |
— |
Spring Break
|
Tue. Mar.29
Lab 10: Qt photon visualizer
|
20 |
[(Figure 12.43, sort of)]
kd-tree insertion
- nn, knn, range queries
[wikipedia]
[Thinh Nguyen's lecture
][Andrew Moore's tutorial
]
|
| Thu. Mar.31 |
21 |
- menubar signals/slots, kd-tree construction
- kd-tree rendering
void GLTexobj::initializeGL()
void GLTexobj::resizeGL()
void GLTexobj::paintGL()
void GLTexobj::mousePressEvent(QMouseEvent* e)
void GLTexobj::mouseReleaseEvent(QMouseEvent* e)
for queries
DUE: Assignment 4 (at 23:59:59)
Solution
|
Tue. Apr.05
Lab 11: kd-tree
|
22 |
Photon mapping
- Step 1: Shoot photons
- scale power by 1/n
- find photon min, max
(for kd-tree bounding volume)
- insert photons into kd-tree
- Step 2: Trace rays
- find closest object (as before)
- get surface material properties (as before)
- compute ambient color contribution (as before)
- compute diffuse reflection contribution (as before)
- compute specular reflection contribution
(spawn reflection ray; as before)
- compute transmissive color contribution
(spawn refraction ray; as before)
- compute specular highlight contribution (as before)
- compute photon power density (flux)
- knn query (k=20), get r
- for each photon accumulate flux
- add in scaled flux to color
Assignment 5: Qt kd-tree
|
| Thu. Apr.07 |
23 |
A decent math library, including a
matrix<> class
|
Tue. Apr.12
Lab 12: Dijkstra's shortest path
|
24 |
Dynamic Programming
- Applications to eye movement (scanpath) comparisons
- Applications to bioinformatics: DNA sequence alignment
- Needleman-Wunsch algorithm
|
| Thu. Apr.14 |
25 |
More on the kd-tree
- the function object
point_c
- kd-tree insertion with
min and max
- nn-query and knn-query details
DUE: Assignment 5 (at 23:59:59)
Solution
|
Tue. Apr.19
|
26 |
Assignment 6: photon mapper
|
| Thu. Apr.21 |
27 |
No class: Student Evaluations (online)
|
| Tue. Apr.26 |
28 |
Final Review
|
| Thu. Apr.28 |
29 |
DUE: Assignment 6
|
| Wed. May.04 |
30 |
FINAL EXAM 3:00pm-5:30pm |