| Date | L# | Topic |
| Thu. Aug.20 |
01 |
Getting Started, C, C++
|
| Tue. Aug.25 |
02 |
[(§ 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<<
|
| Thu. Aug.27 |
03 |
[(§ 1.5.2)]
parameter passing
[(§ 1.4.2)]
const member function (accessor/mutuator)
[(§ 1.6.2)]
templates
Assignment 1
|
| Tue. Sep.01 |
04 |
[(§ 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
|
| Thu. Sep.03 |
05 |
[(§ 1.2.5)]
Inductive proof
- Recurrence relations
- telescoping sum
- recurisve backsubstitution
[(§ 7.6.1)]
Mergesort analysis
- Handy formulae
DUE: Assignment 1 (at 23:59:59)
Solution
|
| Tue. Sep.08 |
06 |
[(§ 7.7.5)]
Quicksort analysis (worst and best cases)
[(§ 3.3)]
STL vector and list
(e.g., vector implementation of insertion sort)
[(§ 6.3)]
Binary Heap (using vector<T>)
insert()
deleteMin()
Assignment 2
|
| Thu. Sep.10 |
07 |
- C++
iostream
including
ifstream
and
ofstream;
see the
input/output with files tutorial
- A useful
istream member:
get
- A useful
istream manipulator:
ws
|
| Tue. Sep.15 |
08 |
[(§ 3.3)]
vector and list in the STL
[(§ 3.3.1)]
Iterators
[(§ 3.5)]
List implementation
|
| Thu. Sep.17 |
09 |
List<Pairs> vs.
List<Pairs* >
[(§ 3.6)]
The Stack ADT
[(§ 3.6.3)]
Applications: Postfix Expressions and Infix to Postfix
Conversion
DUE: Assignment 2 (at 23:59:59)
Solution
|
| Tue. Sep.22 |
10 |
strstream objects
[(§ 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 3
|
| Thu. Sep.24 |
11 |
[(§ 4.3.3)]
insert implementation
[(§ 4.3.4)]
remove (erase) implementation
[(§ 4.3.5)]
destructor and copy assignment operator
[(§ 4.6)]
tree traversals
|
| Tue. Sep.29 |
12 |
[(§ 4.4)]
AVL Trees
[(§ 4.4.1)]
single rotation
[(§ 4.4.2)]
double rotation
|
| Thu. Oct.01 |
13 |
- Revision of text's AVL tree implementation
- AVL node insertion
rotate_left and rotate_write
redux
- AVL node deletion
DUE: Assignment 3 (at 23:59:59)
Solution
Assignment 4
|
| Tue. Oct.06 |
14 |
Quick Review
- C++
- Big-Oh
- Heaps
- Binary Trees
- AVL Trees
|
| Thu. Oct.08 |
15 |
Midterm Exam (C++, big-oh notation, heaps, AVL trees)
|
| Tue. Oct.13 |
16 |
Fall Break
|
| Thu. Oct.15 |
17 |
[(§ 5.1)]
Hashing
[(§ 5.2)]
Hash Function
[(§ 5.3)]
Separate Chaining
[(§ 5.4)]
Hash Tables Without Linked Lists
DUE: Assignment 4 (at 23:59:59)
Solution
|
| Tue. Oct.20 |
18 |
[(§ 9)]
Graph Algorithms
[(§ 9.3)]
Dijkstra's shortest path algorithm
Assignment 5
|
| Thu. Oct.22 |
19 |
[(§ 9)]
Graph Algorithms
[(§ 9.5)]
Prim's minimum spanning tree algorithm
|
| Tue. Oct.27 |
20 |
[(§ 12.6)]
kd-trees
|
| Thu. Oct.29 |
21 |
[(Figure 12.43, sort of)]
kd-tree insertion
[(§ 1.6.4 and footnote at bottom of p.295)]
Function Objects (functors)
DUE: Assignment 5 (at 23:59:59)
Solution
|
| Tue. Nov.03 |
22 |
- nn, knn, range queries
[wikipedia]
[Thinh Nguyen's lecture
][Andrew Moore's tutorial
]
Assignment 6
|
| Thu. Nov.05 |
23 |
[Qt]
(Acquired by Nokia in 2008? Interesting...)
[Qt Docs
(Still a ]trolltech.com domain)
[Qt 3.3
]
|
| Tue. Nov.10 |
24 |
void GLTexobj::mousePressEvent(QMouseEvent* e)
void GLTexobj::mouseReleaseEvent(QMouseEvent* e)
void GLTexobj::paintGL()
- Redrawwing via
updateGL();—don't call
paintGL() directly!
|
| Thu. Nov.12 |
25 |
- menubar signals/slots, kd-tree construction
- kd-tree rendering
void GLTexobj::mouseReleaseEvent(QMouseEvent* e)
for queries
DUE: Assignment 6 (at 23:59:59)
Solution
|
| Tue. Nov.17 |
25 |
- Qt wrapup
void GLTexobj::initializeGL()
void GLTexobj::resizeGL()
Assignment 7
|
| Thu. Nov.19 |
26 |
No class: Student Evaluations (online)
|
| Tue. Nov.24 |
27 |
No class: WSETM 2009
|
| Thu. Nov.26 | -- |
Thanksgiving
|
| Tue. Dec.01 |
28 |
Final Review
|
| Thu. Dec.03 |
29 |
DEMO: Assignment 7
(at class time, in 110 McAdams, main lab, back row, own laptop ok)
|
| Fri. Dec.11 | 30 |
FINAL EXAM 11:30am-2:00pm |