Topics
| Topic | Readings |
|---|---|
| 234-trees | 2-3-4 tree |
| A and A* | Luger5 §4.2,
Luger5 §4.3,
Luger6 §4.2,
Luger6 §4.3
Admissibility, A*, Dijkstra's and A* |
| Affordances | Affordance |
| Algorithm analysis | |
| Alpha-beta pruning | Luger5 §4.4.3,
Luger6 §4.4.3
Alpha-beta pruning, Branch and bound |
| Assorted review | |
| B-trees | Elmasri4 §14.3,
Elmasri6 §18.3,
Weiss3 §4.7
B-tree |
| Bayes' Law | Luger5 §5.4,
Luger6 §5.4
Bayes theorem |
| Bayesian inference | Luger5 §9.3,
Luger6 §9.3
Bayesian inference |
| Brute-force search | Luger5 §3.2,
Luger6 §3.2,
Weiss3 §9.3.1,
Weiss3 §9.6
Depth-first search, Breadth-first search, Iterative deepening depth-first search, Iterative deepening vs depth-first search |
| Compression | Run-length encoding |
| Computational geometry | deBerg3 §1.2,
deBerg3 §1.3
Computational geometry |
| Converting between models | Elmasri4 §7.1, Elmasri6 §9.1, Ullman2 §3.2 |
| Convex hulls | deBerg3 §1.1
Convex hull |
| Convex hulls cont'd | |
| DEFLATE | RFC 1951, DEFLATE |
| Data independence | Elmasri4 §2.2,
Elmasri6 §2.2
Data independence |
| Database components | Elmasri4 §2.4,
Elmasri6 §2.4,
Ullman2 §1.2
Database |
| Database constraints | Elmasri4 §5.2,
Elmasri4 §8.2,
Elmasri6 §3.2,
Elmasri6 §4.2,
Ullman2 §7.1,
Ullman2 §7.2
Database constraints |
| Database correctness (ACID) | Elmasri4 §17.3,
Elmasri6 §21.3,
Ullman2 §1.2.4
Database transaction, ACID |
| Database design principles | Elmasri4 §12.2, Elmasri6 §10.2 |
| Database security | Elmasri4 §23.1,
Elmasri4 §23.2,
Elmasri6 §24.1,
Elmasri6 §24.2
Database security, "Exploits of a Mom" (Little Bobby Tables) |
| Design tradeoffs | |
| Dijkstra's algorithm | Weiss3 §9.3.2
Dijkstra's algorithm, Dijkstra example (graphical), Dijkstra example (good pseudocode, great data trace) |
| Distributing databases | Shard, No SQL |
| Diversity and accessibility | Web accessibility, The Supreme Court, Domino's, and web accessibility for the visually impaired |
| Doubly-connected edge lists | deBerg3 §2.2,
deBerg3 §2.3
Doubly connected edge list |
| Entity-relationship models | Elmasri4 §3.3,
Elmasri4 §3.4,
Elmasri6 §7.3,
Elmasri6 §7.4,
Ullman2 §2.1,
Ullman2 §2.2
E-R model |
| Feedback | |
| Graphs | Luger5 §3.1,
Luger6 §3.1,
Weiss3 §9.1
Graph, Tree |
| Heuristics, take 2 (minimax) | |
| Huffman coding | Weiss3 §10.1.2
Huffman coding |
| Implementing best-first search | |
| Information retrieval | Information retrieval |
| Information theory | Information theory |
| Introduction | |
| Line segment intersection | deBerg3 §2.1
Line segment intersection |
| Logic | Luger5 §2.1,
Luger5 §2.2,
Luger5 §3.3,
Luger6 §2.1,
Luger6 §2.2,
Luger6 §3.3
Propositional logic, Predicate logic, First-order predicate logic, Theorem proving |
| Lossy compression | Lossy data compression |
| Minimax | Luger5 §4.4,
Luger6 §4.4
Minimax, Minimax in AI/games (don't miss link to part 2) |
| Nature of intelligence | Luger5 §17.1,
Luger6 §16.1
Turing test, Chinese room, ELIZA, Turing, A.M. (1950). Computing machinery and intelligence. Mind, 59, 433-460., How Machines Learn (CGP Grey) |
| Naïve Bayes | Naive Bayes classifier, Chain rule |
| Paper prototyping | Paper prototyping |
| Pathfinding | |
| Physical data storage | Elmasri4 §13.1, Elmasri6 §17.1 |
| Precision and recall | Precision and recall |
| Probability | Luger5 §5.2,
Luger6 §5.2
Conditional probability, Joint probability |
| Problem spaces | Luger5 §3.1.3,
Luger6 §3.1.3
State space search |
| Problem spaces, cont'd | Alnilam (game) |
| Project 2 design | |
| Project design work | |
| Prolog | Luger5 §15.1
Prolog, Prolog tutorial |
| Red-black tree deletion cases | |
| Red-black tree implementation cases | Slides on 234/RB insertion cases, RB insertion and deletion with 234 correspondences (English is imperfect but examples are very good), RB insertion (with examples) |
| Red-black trees | Weiss3 §12.2
Red-black tree |
| Relational models | Elmasri4 §5.1,
Elmasri6 §3.1,
Weiss3 §3.1
Relational database, Relation, Examples of CREATE/INSERT |
| SQL | Elmasri6 §4.1,
Elmasri6 §4.3,
Ullman2 §6.1,
Ullman2 §6.5,
Elmasri4 §8.1,
Elmasri4 §8.4
SQL, SQL syntax (SQLite dialect), SQL query semantics |
| SQL cont'd | |
| Sliding window: LZ77 | LZ77 |
| Stateful comparators | |
| Tries | Trie |
| UI evaluation criteria | Usability testing |
| UI perception and cognition | |
| UI standards and guidelines | Best practices in GUI design, List of UI style guides |
| Unification | |
| User interfaces | User interface, User interface design |
| Using hash tables | unordered_set in C++, HashSet in Java |
| Using maps | Weiss3 §4.8
map in C++, Map in Java |
| Using priority queues | priority_queue in C++, PriorityQueue in Java, queue.PriorityQueue in Python |
| Writing hash functions | Hash functions, hash in C++, hashCode() in Java |