2013_spring_cs_261 [Michael's Wiki]

Trace: › 2013_spring_cs_261

Data Structures

[http://www.ics.uci.edu/~eppstein/261/ Class Webpage] [http://en.wikipedia.org/wiki/Book:Fundamental_Data_Structures Textbook]

Data structures are described in terms of the data they contain and an API for accessing and updating the data. API defines the set of functions which perform an “update” or change to the data, or perform a “query” in order to return information based on the data.

Tricks

$(1 - \frac{1}{n})^n = e^{-1}$ and therefore $(1 - \frac{1}{n})^x = \left( (1 - \frac{1}{n})^{nx} \right)^{1/n} = e^{-\frac{x}{n}}$

Lecture 5

Dictionary Problem Hash Tables

Lecture 6

Cuckoo Hashing Hash Functions

Lecture 7

Sets Bloom Filters

Lecture 8

Streaming Sketches Min Hash

Lecture 9

Priority Queues

Lecture 10

Fibonacci Heaps

Lecture 11

Binary Search Trees Competetive Ratio

Lecture 12

Lecture 13

Midterm

Lecture 14

Tries Suffix Trees

Lecture 15

Subarray Average Problem Dynamic Prefix Sum

Lecture 16

Range Searching

Lecture 17

Range Minimum Lowest Common Ancestors Problem

Lecture 18

Persistent Data Structures

Lecture 19

Priority Queues Integer Searching

Lecture 20

Kruskal's Algorithm Union Find