# Topics

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

22 Aug | T/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 | ||||

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

29 Aug | T/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) | |||||||

31 Aug | R/2 | Red-black tree deletion cases | ||||||||

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

7 Sep | R/3 | Probability, Bayes' Law | 5.2, 5.4 | 5.2, 5.4 | Conditional probability; Joint probability; Bayes theorem | |||||

12 Sep | T/4 | Bayes nets, Naïve Bayes | 9.3 | 9.3 | Bayesian inference; Naive Bayes classifier; Chain rule | |||||

14 Sep | R/4 | Information retrieval, Precision and recall | Information retrieval; Precision and recall | |||||||

19 Sep | T/5 | Using maps | 4.8 | map in C++; Map in Java | ||||||

21 Sep | R/5 | User interfaces, UI perception and cognition, Affordances, Feedback, Diversity and accessibility | User interface; User interface design; Affordance; Web accessibility | |||||||

26 Sep | T/6 | Paper prototyping | Paper prototyping | |||||||

28 Sep | R/6 | Design tradeoffs, UI evaluation criteria, UI standards and guidelines | Usability testing; List of UI style guides; Best practices in GUI design | |||||||

3 Oct | T/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 | ||||

5 Oct | R/7 | Dijkstra's algorithm | 9.3.2 | Dijkstra's algorithm; Dijkstra example (graphical); Dijkstra example (good pseudocode, great data trace) | ||||||

10 Oct | T/8 | A and A* | 4.2, 4.3 | 4.2, 4.3 | Admissibility; A*; Dijkstra's and A* | |||||

12 Oct | R/8 | Implementing best-first search, Using priority queues, Using hash tables | priority_queue in C++; PriorityQueue in Java; unordered_set in C++; HashSet in Java | |||||||

19 Oct | R/9 | Writing hash functions, Stateful comparators | Hash functions; hash in C++; hashCode() in Java | |||||||

24 Oct | T/10 | Problem spaces | 3.1.3 | 3.1.3 | State space search | |||||

26 Oct | R/10 | 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) | |||||

31 Oct | T/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. | |||||

2 Nov | R/11 | Database components, Relational models | 3.1 | 1.2 | 2.4, 5.1 | 2.4, 3.1 | Database; Relational database; Relation | |||

7 Nov | T/12 | SQL | 6.1, 6.5 | 8.1, 8.4 | 4.1, 4.3 | SQL; SQL syntax (SQLite dialect) | ||||

9 Nov | R/12 | Entity-relationship models | 2.1, 2.2 | 3.3, 3.4 | 7.3, 7.4 | E-R model | ||||

14 Nov | T/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) | ||||

16 Nov | R/13 | Database constraints, Database correctness (ACID), Distributing databases | 7.1, 7.2, 1.2.4 | 5.2, 8.2, 17.3 | 3.2, 4.2, 21.3 | Database constraints; Database transaction; ACID; Shard; No SQL | ||||

21 Nov | T/14 | Computational geometry, Convex hulls | 1.2, 1.3, 1.1 | Computational geometry; Convex hull | ||||||

28 Nov | T/15 | Convex hulls cont'd, Algorithm analysis | ||||||||

30 Nov | R/15 | Line segment intersection, Doubly-connected edge lists | 2.1, 2.2, 2.3 | Line segment intersection; Doubly connected edge list |