Advanced Algorithms and Data Structures, Video Edition

1 Introducing data structures
2 Improving over basic data structures
3 Describing a data structure
4 Packing your knapsack – Data structures meet the real world
5 Algorithms to the rescue
6 Improving priority queues – d-way heaps
7 Solutions at hand – Keeping a sorted list
8 Concrete data structures
9 Priority, min-heap, and max-heap
10 How to implement a heap
11 PushDown
12 Top
13 Heapify
14 Use case – Find the k largest elements
15 More use cases
16 Analysis of branching factor
17 Performance analysis – Finding the best branching factor
18 Interpreting results
19 The mystery with heapify
20 Treaps – Using randomization to balance binary search trees
21 Treap
22 A few design questions
23 Delete
24 Applications – Randomized treaps
25 Performance analysis and profiling
26 Profiling height
27 Profiling memory usage
28 Bloom filters – Reducing the memory for tracking content
29 Alternatives to implementing a dictionary
30 Concrete data structures
31 Binary search tree – Every operation is logarithmic
32 Implementation
33 Constructor
34 Applications
35 Why Bloom filters work
36 Performance analysis
37 Explanation of the false-positive ratio formula
38 Improved variants
39 Disjoint sets – Sub-linear time processing
40 Reasoning on solutions
41 Naïve solution
42 Using a tree-like structure
43 Heuristics to improve the running time
44 Applications
45 Trie, radix trie – Efficient string search
46 Trie
47 Search
48 Insert
49 Keys matching a prefix
50 Radix tries
51 Search
52 Applications
53 String sorting
54 45 Chapter 7 Use case – LRU cache
55 First attempt – Remembering values
56 Handling asynchronous calls
57 Memory is not enough (literally)
58 Getting rid of stale data – LRU cache
59 Temporal ordering
60 When fresher data is more valuable – LFU
61 How to use cache is just as important
62 Solving concurrency (in Java)
63 Read locks
64 Multidimensional queries
65 Nearest neighbors search
66 Simplifying things to get a hint
67 Moving to k-dimensional spaces
68 K-d trees – Multidimensional data indexing
69 Constructing the BST
70 Methods
71 Balanced tree
72 Remove
73 Nearest neighbor
74 Region search
75 Similarity Search Trees – Approximate nearest neighbors search for image retrieval
76 R-tree
77 Inserting points in an R-tree
78 Similarity search tree
79 SS-tree search
80 Insert
81 Insertion – Split nodes
82 Delete
83 Similarity Search
84 Approximated similarity search
85 SS+-tree
86 Reducing overlap
87 Applications of nearest neighbor search
88 79 Chapter 11.Centralized application
89 Moving to a distributed application
90 Other applications
91 Multidimensional DB queries optimization
92 Clustering
93 Types of learning
94 K-means
95 The curse of dimensionality strikes again
96 Boosting k-means with k-d trees
97 DBSCAN
98 From definitions to an algorithm
99 And finally, an implementation
100 OPTICS
101 From reachability distance to clustering
102 Hierarchical clustering
103 4 Chapter 12. Evaluating clustering results – Evaluation metrics
104 Parallel clustering – MapReduce and canopy clustering
105 Canopy clustering
106 MapReduce
107 First map, then reduce
108 MapReduce k-means
109 Parallelizing canopy clustering
110 MapReduce canopy clustering
111 MapReduce DBSCAN – Part 1
112 MapReduce DBSCAN – Part 2
113 Planar graphs and minimum crossing number
114 An introduction to graphs – Finding paths of minimum distance
115 Implementing graphs
116 Graph properties
117 Graph traversal – BFS and DFS
118 Reconstructing the path to target
119 Shortest path in weighted graphs – Dijkstra
120 Beyond Dijkstra’s algorithm – A
121 How good is A search
122 Heuristics as a way to balance real-time data
123 Graph embeddings and planarity – Drawing graphs with minimal edge intersections
124 Some basic definitions
125 Planar graphs
126 Planarity testing
127 Improving performance
128 Non-planar graphs
129 Rectilinear crossing number
130 Edge intersections
131 Polylines
132 Intersections between quadratic Bézier curves
133 Gradient descent – Optimization problems (not just) on graphs
134 Did you just say heuristics
135 How optimization works
136 Gradient descent
137 When is gradient descent appliable
138 Applications of gradient descent
139 Gradient descent for graph embedding
140 Simulated annealing – Optimization beyond local minima
141 Sometimes you need to climb up to get to the bottom
142 Why simulated annealing works
143 Short-range vs long-range transitions
144 Simulated annealing + traveling salesman
145 Exact vs approximated solutions
146 State transitions
147 Simulated annealing and graph embedding
148 Force-directed drawing
149 Genetic algorithms – Biologically inspired, fast-converging optimization
150 Inspired by nature
151 Chromosomes
152 Natural selection
153 Selecting individuals for mating
154 Crossover
155 The genetic algorithm template
156 TSP
157 Results and parameters tuning
158 Minimum vertex cover
159 Other applications of the genetic algorithm
160 Beyond genetic algorithms
161 62 Appendix A. A quick guide to pseudo-code
162 63 Appendix A Conditional instructions
163 64 Appendix A Blocks and indent
164 65 Appendix B. Big-O notation
165 66 Appendix B Notation
166 67 Appendix C. Core data structures
167 68 Appendix C Tree
168 69 Appendix C Hash table
169 70 Appendix D. Containers as priority queues
170 71 Appendix E. Recursion
171 72 Appendix E Tail recursion
172 73 Appendix F. Classification problems and randomnized algorithm metrics
173 74 Appendix F Classification metrics