Discussion 14: Misc.onclusion Christine Zhou Agenda Announcements Worksheet CS Courses Overview Optional: Interview Question Tips Announcements Cookies!! HW8 due Friday 12/1 Proj3 due Wednesday 12/6 Tentative plan for dead week: No discussion OH as normal Lab will be converted to topic based review Design! Weighted Quick Union with Path Compression Used to represent connectivity between items Each item belongs to its own set, “union” the items together by connecting the sets together Sets will have a tree like structure Optimizations: Union by weight: connect the root of the “lighter” set to the root of the “heavier” set (determined by number of nodes in the set) Path compression: when you “find” a node, compress the node and the path to the node by connecting it to the root of the set 61BL Lab about Disjoint Sets HashMaps Use an array to represent your data For each key-value pair, assign each key a “hash code” mod (%) the hash code by the length of the array (this gives you a number between 0 and array.length - 1), use this as the index! N = num elements, M = num buckets, C = some constant If N/M > C, then increase M! N/M is called the load factor If we have multiple elements that go to same place in the array, usually we will keep track of a list Be careful about negative numbers when modding! This is called external chaining What is the runtime of .contains and .insert? Course Overview (Personal experiences) CS61C: Machine Structures C, assembly language Learn about how computers work! Caching, MapReduce, parallelism CS170: Algorithms CS70: Discrete Math/Probability Proofs for things we’ve seen so far Problem set every week Stable marriage, modular arithmetic, graph theory, etc. CS186: Databases Learn SQL and how databases keep track of all your data, Java “Chill”, though exam was tough this time around…, some projects Guest speakers from the industry Learn to analyze runtimes,