Windsooon

海外兔

sharmaeklavya2

Competitive Programming Syllabus

Geometry

• Graham Scan algorithm for Convex Hull O(n * log(n))
• Online construction of 3-D convex hull in O(n^2)
• Bentley Ottmann algorithm to list all intersection points of n line segments in O((n + I) * logn)
  • Suggested Reading - http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm
• Rotating Calipers Technique
  • Suggested Reading - http://cgm.cs.mcgill.ca/~orm/rotcal.html

• Problems - Refer the article for a list of problems which can be solved using Rotating Calipers technique.

jboner

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD