wiki_research

commit 730f3ac0be2f4e703553a94f70823d0f4e65cd4b
parent c01232e15614bacf4908f9e3f69c8e6ae773d435
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Mon, 15 Sep 2025 12:55:46 +0200

Merge branch 'master' of a3nm.net:git/wiki_research

Diffstat:
algorithms_list
 | 
1
+
arithmetic
 | 
2
++
average
 | 
2
+-
binary_search
 | 
7
+++++++
circuit
 | 
1
+
circuit_value_problem
 | 
7
+++++++
context_free_grammar
 | 
1
+
context_free_grammar_membership
 | 
12
++++++++++++
context_free_language_membership
 | 
2
++
exponential_search
 | 
7
+++++++
median
 | 
8
++++++++
stern_brocot_tree
 | 
11
+++++++++++
tree_binary
 | 
2
++
tree_evaluation_problem
 | 
2
++

14 files changed, 64 insertions(+), 1 deletion(-)
diff --git a/algorithms_list b/algorithms_list
@@ -17,5 +17,6 @@
 - [tortoise_and_hare_algorithm]
 - [stable_marriage]
 - [binary_search]
+- [exponential_search]
 
 Up: [algorithms]
diff --git a/arithmetic b/arithmetic
@@ -7,6 +7,8 @@
 - [presburger_arithmetic]
 - [divisibility]
 - [modulo]
+- [GCD]
+- [coprime]
 
 Up: [mathematics]
 
diff --git a/average b/average
@@ -4,4 +4,4 @@ relevant [academic_paper]: [hemenway1982classes]
 
 Up: [statistics]
 
-See also: [expectation]
+See also: [expectation], [median]
diff --git a/binary_search b/binary_search
@@ -0,0 +1,7 @@
+# Binary search
+
+https://en.wikipedia.org/wiki/Exponential_search
+
+Up: [algorithms_list]
+
+See also: [binary_search_tree], [interpolation_search]
diff --git a/circuit b/circuit
@@ -23,6 +23,7 @@
 
 - [enumeration_circuit]
 - [satisfiability]
+- [circuit_value_problem]
 
 ## Measure [circuit_parameter]
 
diff --git a/circuit_value_problem b/circuit_value_problem
@@ -0,0 +1,7 @@
+# Circuit value problem
+
+Given a [Boolean_circuit] with Boolean values on the gates, and a [gate], decide if that [gate] evaluates to [true]
+
+Up: [decision_problem] on [circuit]
+
+See also: [formula_value_problem]
diff --git a/context_free_grammar b/context_free_grammar
@@ -36,6 +36,7 @@
 - [context_free_grammar_equivalence]
 - [context_free_grammar_universality]
 - [smallest_grammar_problem]
+- [context_free_grammar_membership]
 
 ## Fields
 
diff --git a/context_free_grammar_membership b/context_free_grammar_membership
@@ -0,0 +1,12 @@
+# Context free grammar membership
+
+Given a [CFG] G and a [word] w, decide whether w is accepted by G
+
+Can be studied in:
+- [combined_complexity]
+  - can do [CFG_parsing] like [CYK]
+- [data_complexity]: cf [context_free_language_membership]
+
+Up: [context_free_grammar], [membership_problem]
+
+See also: [context_free_language_membership]
diff --git a/context_free_language_membership b/context_free_language_membership
@@ -6,3 +6,5 @@
   - [Valiant's_parser]
 
 Up: [membership_problem], [context_free_language]
+
+See also: [context_free_grammar_membership]
diff --git a/exponential_search b/exponential_search
@@ -0,0 +1,7 @@
+# Exponential search
+
+https://en.wikipedia.org/wiki/Exponential_search
+
+Up: [algorithms_list]
+
+Aliases: galloping search
diff --git a/median b/median
@@ -0,0 +1,8 @@
+# Median
+
+- [Weighted_median]
+- [Median_of_medians]
+
+See also: [average], [mediant]
+
+Up: [statistics]
diff --git a/stern_brocot_tree b/stern_brocot_tree
@@ -0,0 +1,11 @@
+# Stern-Brocot tree
+
+https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree
+
+Should be seen as having 0/1 to the left and 0/1 to the right: for each node you sum the numerators and the denominators ([mediant]) of the closest left node and right node
+
+Gives all [irreducible_fractions], in sorted order
+
+Up: [tree] of [rational_numbers]
+
+See also: [farey_sequence]
diff --git a/tree_binary b/tree_binary
@@ -7,3 +7,5 @@ A [tree] in which [internal_nodes] have at most two [children]
 Up: [tree]
 
 Aliases: binary tree, binary trees
+
+See also: [binary_search_tree]
diff --git a/tree_evaluation_problem b/tree_evaluation_problem
@@ -7,3 +7,5 @@ It is in O(log n log log n), cf [cook2023tree]
 Up: [computational_problem] on [tree]
 
 Aliases: TreeEval
+
+See also: [formula_value_problem]