Algorithms and data structures

Více o knize

The content spans various sessions focusing on algorithm theory and applications. It begins with foundational concepts, such as a theory of algorithms and k-restricted rotations relevant to search tree rebalancing and heap building bounds. The exploration continues with complex problems like the multi-radius cover and generalized vertex cover, alongside efficient priority queues and adaptive multi-digit branching in tries. Further sessions delve into combinatorial group testing, online set multicover problems, and max-stretch reductions for tree spanners. The text also addresses succinct triangulation representations and enhanced fixed-parameter algorithms for feedback set issues, alongside communication-aware processor allocation in supercomputing contexts. Additional topics include the minimum-area spanning tree problem, convex recolorings of strings and trees, and linear-time algorithms for edge dominating sets. The content discusses geometric dilation, kinetic data structures, and dynamic implicit adjacency labeling for line graphs. The latter sections focus on all-pairs shortest paths, k-link shortest paths, and power-saving scheduling for voltage scaling devices. Finally, it covers optimal prefix-free codes, trade-offs in sorting algorithms, and advancements in subquadratic algorithms for 3SUM, culminating in improved approximation bounds for various computational problems.