# Topics

Topics | Luger6 |
Luger5 |
Weiss3 |
Ullman2 |
Elmasri4 |
Elmasri6 |
deBerg3 |
Web links | ||
---|---|---|---|---|---|---|---|---|---|---|

26 Aug | M/1 | Introduction, Data independence, Physical data storage, B-trees | 4.7 | 2.2, 13.1, 14.3 | 2.2, 17.1, 18.3 | Data independence; B-tree | ||||

28 Aug | W/1 | 234-trees, Red-black trees | 12.2 | 2-3-4 tree; Red-black tree | ||||||

04 Sep | W/2 | Red-black tree implementation cases | Slides on 234/RB insertion cases; RB insertion (with examples); RB insertion and deletion with 234 correspondences (English is imperfect but examples are very good) | |||||||

09 Sep | M/3 | Red-black tree deletion cases | ||||||||

11 Sep | W/3 | Tries, Huffman coding, Information theory, Compression, Lossy compression | 10.1.2 | Huffman coding; Information theory; Run-length encoding; Lossy data compression; Trie | ||||||

16 Sep | M/4 | Probability, Bayes' Law | 5.2, 5.4 | 5.2, 5.4 | Conditional probability; Joint probability; Bayes theorem | |||||

18 Sep | W/4 | Bayes nets | 9.3 | 9.3 | Bayesian inference | |||||

23 Sep | M/5 | Naïve Bayes, Using maps | 4.8 | map in C++; Map in Java; Naive Bayes classifier; Chain rule | ||||||

25 Sep | W/5 | Information retrieval, Precision and recall | Information retrieval; Precision and recall | |||||||

30 Sep | M/6 | User interfaces, UI perception and cognition, Affordances, Feedback, Diversity and accessibility | User interface; User interface design; Affordance; Web accessibility; The Supreme Court, Domino's, and web accessibility for the visually impaired | |||||||

02 Oct | W/6 | Paper prototyping | Paper prototyping | |||||||

07 Oct | M/7 | Design tradeoffs, UI evaluation criteria, UI standards and guidelines | Usability testing; List of UI style guides; Best practices in GUI design | |||||||

09 Oct | W/7 | Graphs, Pathfinding, Brute-force search | 3.1, 3.2 | 3.1, 3.2 | 9.1, 9.3.1, 9.6 | Graph; Tree; Depth-first search; Breadth-first search; Iterative deepening depth-first search; Iterative deepening vs depth-first search | ||||

16 Oct | W/8 | Dijkstra's algorithm | 9.3.2 | Dijkstra's algorithm; Dijkstra example (graphical); Dijkstra example (good pseudocode, great data trace) | ||||||

21 Oct | M/9 | A and A* | 4.2, 4.3 | 4.2, 4.3 | Admissibility; A*; Dijkstra's and A* | |||||

23 Oct | W/9 | Implementing best-first search, Using priority queues, Using hash tables | priority_queue in C++; PriorityQueue in Java; unordered_set in C++; HashSet in Java | |||||||

28 Oct | M/10 | Writing hash functions, Stateful comparators | Hash functions; hash in C++; hashCode() in Java | |||||||

30 Oct | W/10 | Problem spaces | 3.1.3 | 3.1.3 | State space search | |||||

04 Nov | M/11 | Problem spaces, cont'd, Minimax, Alpha-beta pruning | 4.4, 4.4.3 | 4.4, 4.4.3 | Minimax; Minimax in AI/games (don't miss part 2); Minimax with examples and pseudocode (don't miss pages 2 and 3); Alpha-beta pruning; Branch and bound; Alnilam (game) | |||||

06 Nov | W/11 | Nature of intelligence | 16.1 | 17.1 | Turing test; Chinese room; ELIZA; Turing, A.M. (1950). Computing machinery and intelligence. Mind, 59, 433-460.; How Machines Learn (CGP Grey) | |||||

11 Nov | M/12 | Database components, Relational models | 3.1 | 1.2 | 2.4, 5.1 | 2.4, 3.1 | Database; Relational database; Relation; Examples of CREATE/INSERT | |||

13 Nov | W/12 | SQL | 6.1, 6.5 | 8.1, 8.4 | 4.1, 4.3 | SQL; SQL syntax (SQLite dialect); SQL query semantics | ||||

18 Nov | M/13 | Entity-relationship models | 2.1, 2.2 | 3.3, 3.4 | 7.3, 7.4 | E-R model | ||||

20 Nov | W/13 | Converting between models, Database design principles, Database security | 3.2 | 7.1, 12.2, 23.1, 23.2 | 9.1, 10.2, 24.1, 24.2 | Database security; "Exploits of a Mom" (Little Bobby Tables) | ||||

25 Nov | M/14 | Database constraints, Database correctness (ACID), Distributing databases, Computational geometry, Convex hulls | 7.1, 7.2, 1.2.4 | 5.2, 8.2, 17.3 | 3.2, 4.2, 21.3 | 1.2, 1.3, 1.1 | Database constraints; Database transaction; ACID; Shard; No SQL; Computational geometry; Convex hull | |||

02 Dec | M/15 | Convex hulls cont'd, Algorithm analysis | ||||||||

04 Dec | W/15 | Line segment intersection, Doubly-connected edge lists | 2.1, 2.2, 2.3 | Line segment intersection; Doubly connected edge list |