CS Background Lecture Slides

Basic Data Structures

• Lists, Stacks, and Queues
• AVL Trees
• Splay Trees
• B-Trees
• Skip Lists
• Heaps

Other Data Structures

• RRR Compressed Bitvectors

Interval & Spatial Data Structures

• Quadtrees (PR, MX, Point)
• kd-Trees
• Searching in kd-Trees
• Range Trees
• Interval Trees
• Finding Closest Pair of Points
• Demos for Spatial Data Structures by Brabec and Samet

Programming Languages

• Python
• C++

Network Flow Algorithms

• Network Flows
• Bipartite Matching
• Edge-disjoint paths
• Flows with Demands, etc.
• Shortest paths with negative weights

The Theory of NP-Completeness

• The P and NP Complexity Classes
• NP-completeness
• SAT, Coloring, TSP Problems
• 3-dimensional Matching, Subset Sum Problems