mo_algorithm_example.cc File Reference

Four creative scenarios demonstrating Mo's algorithm. More...

#include <tpl_mo_algorithm.H>
#include <tpl_dynMapOhash.H>
#include <tpl_dynSetHash.H>
#include <algorithm>
#include <cassert>
#include <cstdio>

Include dependency graph for mo_algorithm_example.cc:

Go to the source code of this file.

Classes
struct	Packet_Sum_Sq_Policy
	Custom Mo policy: sum of squared packet sizes in a window. More...

Functions
static void	biodiversity_survey ()
static void	powerful_array ()
static void	election_polling ()
static void	network_packet_analysis ()
int	main ()

Detailed Description

Four creative scenarios demonstrating Mo's algorithm.

SCENARIO 1 — "Biodiversity Survey"

Count distinct species observed by a wildlife camera trap across different time windows. Uses Distinct_Count_Mo.

SCENARIO 2 — "Powerful Array"

Classic competitive programming problem: compute sum(cnt[x]^2 * x) for several ranges. Uses Powerful_Array_Mo.

SCENARIO 3 — "Election Polling"

Find the most reported candidate (mode) across polling windows. Uses Range_Mode_Mo.

SCENARIO 4 — "Network Packet Analysis" (Custom Policy)

Sum of squared packet sizes in time windows. Demonstrates writing a custom MoPolicy from scratch.

Definition in file mo_algorithm_example.cc.

Function Documentation

biodiversity_survey()

static void biodiversity_survey ( )

static

Definition at line 71 of file mo_algorithm_example.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynHashTable< Key, HashTable, Cmp >::insert(), l, and r.

Referenced by main().

election_polling()

static void election_polling ( )

static

Definition at line 166 of file mo_algorithm_example.cc.

References Aleph::divide_and_conquer_partition_dp(), l, and r.

Referenced by main().

main()

int main

(

)

Definition at line 298 of file mo_algorithm_example.cc.

References biodiversity_survey(), Aleph::divide_and_conquer_partition_dp(), election_polling(), network_packet_analysis(), and powerful_array().

network_packet_analysis()

static void network_packet_analysis ( )

static

Definition at line 245 of file mo_algorithm_example.cc.

References Aleph::divide_and_conquer_partition_dp(), l, and r.

Referenced by main().

powerful_array()

static void powerful_array ( )

static

Definition at line 126 of file mo_algorithm_example.cc.

References Aleph::divide_and_conquer_partition_dp().

Referenced by main().