~/talk

Proof Pearl: Braun Trees

on YouTube 21m
Talkat CPP 2020 · 2020-01-20..01-21· [compilers-and-language-design]

speaker

name:Tobias Nipkow
links:none on file

resources

video:https://youtu.be/EipOEWKlSBQ
slides:none on file

summary

Paper supplies verified code and machine-checked proofs that pin down concrete claims: computing size in log^2 time, building an all-equal tree with n nodes in log n time, converting a list to a Braun tree in linear time and — crucially — a new linear-time tree→list algorithm. Two practical priority-queue Delmin implementations are given (one sift‑down style, one merge/extract style) and used to sort in n log n. Complexity arguments are done by explicit recurrence/time functions proven against the implementations.

AI-written summary · about

chapters (7)

  1. 0:00Introduction to brown trees
  2. 1:33Defining brown tree properties
  3. 3:28Array operations
  4. 5:53Conversion algorithms
  5. 10:08Priority queue implementations
  6. 14:15Sorting and performance
  7. 17:23Q&A and conclusion

related talks

~/search
type to search 6,249 conferences, 138,987 speakers and 185,172 talks
~/help
cmdctrl k
search every conference, speaker and series
/
focus the filter search
h
home
c
conferences
s
speakers
e
series
t
light / dark — the status bar button does the same
?
this help
esc
close this, then clear every filter — or just the search, while you are typing in it

Ignored while you are typing. Pages without a filter rail have no search to focus.