| Date | L# | Topic |
Thu. Aug.25
Dr. D. away:
ECEM
Dr. Malloy subs
|
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. Aug.30
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. Sep.01
|
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. Sep.06
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. Sep.08
Dr. D. away:
ITU
TA Tobias subs
|
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. Sep.13
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. Sep.15
Dr. D. away:
PETMEI
Dr. Malloy subs
|
07 |
vector and list in the STL
[(§ 3.3)]
vector and list
[(§ 3.3.1)]
Iterators
[(§ 3.5)]
list_t implementation
|
Tue. Sep.20
Dr. D. away:
PETMEI
TA Drachova subs
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. Sep.22
Dr. D. away:
PETMEI
TA Tobias subs
|
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. Sep.27
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. Sep.29
|
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. Oct.04
Lab 6: list_t
|
12 |
Quick Review
- C++
- Big-Oh
- Heaps
- Binary Trees
- AVL Trees
|
Thu. Oct.06
|
13 |
Q & A
DUE: Assignment 2 (at 23:59:59)
Solution
|
Tue. Oct.11
Lab 7: stack; infix notation
|
14 |
Midterm Exam (C++, big-oh notation, heaps, AVL trees)
Assignment 3: AVL trees
|
Thu. Oct.13
Dr. D. away:
A/VT
TA Tobias subs
|
15 |
[(§ 5.1)]
Hashing
[(§ 5.2)]
Hash Function
[(§ 5.3)]
Separate Chaining
[(§ 5.4)]
Hash Tables Without Linked Lists
|
Tue. Oct.18
|
— |
Fall Break
|
| Thu. Oct.20 |
16 |
Graphs
[(§ 9)]
Graph definitions, representation
- Using the
std::map<std::map< > >
- Using a
node_t to represent a graph vertex
|
Tue. Oct.25
Lab 8: binary search trees I
|
17 |
[(§ 9.3)]
Dijkstra's shortest path algorithm
[(§ 9.5)]
Prim's minimum spanning tree algorithm
DUE: Assignment 3 (at 23:59:59)
Solution
|
Thu. Oct.27
|
18 |
[(§ 12.6)]
kd-trees
[(§ 1.6.4 and footnote at bottom of p.295)]
Function Objects (functors)
Assignment 4: photon emission
|
Tue. Nov.01
Lab 9: binary search trees II
|
19 |
[(Figure 12.43, sort of)]
kd-tree insertion
- nn, knn, range queries
[wikipedia]
[Thinh Nguyen's lecture
][Andrew Moore's tutorial
]
|
Thu. Nov.03
Dr. D. away:
EPFL
|
20 |
[Qt]
[Qt Docs
][Qt 4.6
]
|
Tue. Nov.08
Lab 10: Qt photon visualizer
|
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
|
Thu. Nov.10
|
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
|
Tue. Nov.15
Lab 11: kd-tree
|
23 |
A decent math library, including a
matrix<> class
|
Thu. Nov.17
|
24 |
From C++ to Objective-C
(see Pierre Chatelier's very well-written and useful
document)
- main differences (dynamically allocated objects, no auto objects)
- member function calls'
[] syntax
- class interface and implementation
- memory management (important!)
- inheritance, protocols
- code parallelization via
omp
|
Tue. Nov.22
Lab 12: Dijkstra's shortest path
|
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
|
Thu. Nov.24
|
— |
Thanksgiving
|
Tue. Nov.29
|
26 |
Assignment 6: photon mapper
|
Thu. Dec.01
|
27 |
No class: Student Evaluations (online)
|
Tue. Dec.06
|
28 |
Final Review
|
Thu. Dec.08
Dr. D. away:
CHI 2012 PC
|
29 |
DUE: Assignment 6
|
Wed. Dec.14
|
30 |
FINAL EXAM 3:00pm-5:30pm |