Code Archive to Do List: =========================================================================== Symbols: + in updated archive in old archive X not yet done ? hell if I know 2D Geometry: ------------------------ + angle_2d.c Magnitude of angle (in radians) between 3 points + angle_2d180.cc Magnitude of angle (in radians) between 3 points v2 + area_ellipse.c Area of an arbitrary ellipse in quadratic form + area_heron.c Area of a triangle given lengths of three sides + area_poly.c Finds the signed area of a simple polygon + area_regpoly.c Area of a regular N-gon with side length S + area_tri.c Area of a triangle given its 3 vertices + area_unionrect.c Finds the area of a union of rectangles + ccw.c Orientation analysis + centroid.c Finds the centroid (center of mass) of a polygon + circ_3pts.c Returns circle parameters defined by 3 points + circ_tangents.c Given a point and circle, finds points of tangency + closest_pair Finds closest pair of point from a set of point + closest_pt_iline.c Find point on infinite line AB closest to point C + closest_pt_lineseg.c Find point on line segment AB closest to point C + convex_hull.c Finds the convex hull of a point set X coslaw.c Cosine Law for triangles + dist_2d.c Finds the distance between two points + dist_iline.c Shortest distance from a point to an infinite line + isect_circ_area.c Finds the area of intersection of two circles + isect_circ_line.c Intersection pt(s) of circle and line/line segment + isect_circ_pts.c Finds the intersection points of two circles + isect_circ_test.c Finds the intersection status of two circles + isect_iline Finds the intersection of two infinite lines + isect_lineseg.c Finds the intersection of two line segments ? isect_lineseg_test.c Tests if two line segments intersect + isect_poly_area.cc Area of intersection of two simple polygons X isect_polygons.c Finds the intersection of two polygons + laser.cc Simulates laser bouncing off mirror + lat_poly_pick.c # of interor/boundary points on a lattice polygon + max_empty_rect.cc Largest empty rectangle in W*H field with N points + midpts2vert.c Finds a polygon given its midpoints + min_circle.c Finds minimum bounding circle around set of points + point_in_convexpoly.c Tests if a point is in a convex poly ? point_in_poly.c Tests if a point is in a polygon poly_bisect.c Given pt. on convex polygon, find bisection point poly_intersect.c Intersection of two convex polygon + poly_similar.c Tests if two polygons are similar to one another X poly_triangulate.c Triangulates a polygon + pt_in_poly.c Test if a point is inside a polygon + pt_leftright.c Test if point is left/right/collinear with line + pts2_genline.c Given two points, returns the line Ax+By = C + rect_in_rect_test.c Test if rectangle can fit inside another rectangle + reflect.c Reflect a point across a given line + rotate_2d.c Rotates a point about another point X sinlaw.c Sin Law for triangles + soddy_circ_radius.c Finds radius of Soddy circle given 3 radii tin_cutting.c Generic Tin-Cutting algorithm traverse.c Traverse a point set following most counter-clockwise X tri_incircle.c Finds the largest circle fitting inside a triangle + triangulate.cc Triangulates a simple 2D polygon 3D Geometry: ------------------------ + area_cpoly3d.c Finds the area of a planar convex polygon X convex_hull3d.cc 3-D Convex hull + geom.cc Ashley's 3D-do it all library + greatcircle.c Finds shortest distance on a sphere isect_cyl-line.c Infinite Cylinder/Line intersection X isect_sphere_line.c Intersection of a sphere and a line segment rotate_3d_4d.c Rotate a point in higher dimensions + sphere_from_4pts.c Calculates sphere defined by 4 points Arithmetic: ------------------------ bignum_natural.c Arbitrary precision on natural numbers X bignum_strings.c Arbitrary precision using string representation X bignum_signed.c Arbitrray precision on signed numbers binom.c Compute binomial coefficients without overflow chinese_rem.c Chinese remainder Theorem diophantine.c Solve Diophantine equations ax + by =c diophantine_gen.c Solve generalized Diophantine equations + discrete_log.c Solves discrete logarithms: b^x == n mod (prime p) + fast_exp.c Fast exponentiation b^a + fast_exp_mod.c Fast exponentiation b^ a mod n fflinsolve.c Solves systems of linear equations over integers X fractions.c Mathematics with fractions (+,-,*,/) gausselim.c Compute upper echelon form and determinant of a matrix gcd.c Euclid's GCD algorithm gcd_extended.c Extended Euclid's algorithm: ax + by = gcd(a,b) int_mult.c Integer multiplication without overflow mult.c Multiplication/Division without overflow X multinomials.c Mathematics with multinomials (+,-,*,/,gcd) linear_eq.c Solves systems of linear equations X polynomials.c Mathematics with polynomials (+,-,*,/,gcd) simplex.c Simplex system solver + simpson.c Simpson's Rule for Numerical Integration + solve_cubic.c Solves cubic equations ax^3+bx^2+cx+d = 0 + solve_quad.c Solve quadratic equations ax^2+bx+c = 0 + t_func.c Find avg. number of trials to collect n pieces zero_one.c Solves binary linear systems C++: ------------------------ + maps.cc Maps tempalte for C++ STL + next_permutation.cc Given a sequence, generates next permutation + pqueue.cc Priority queue template for C++ STL + string_tokenizer.cc String tokenizer template for C++ + stl_quickref.ps STL quick reference Combinatorics: ------------------------ + binomial.c Calculate binomial coefficients up to Choose(68,34) + digit_count.c Counts number of times a digit occurs from 1..N + factorial_dig.c Find the number of digits of N! in base B + josephus.c Find the (n,m)-Josephus ring survivor + necklace.c Find # of size-N necklaces/bracelets with K colors + permdex_distinct.c Find permutation # for distinct-character strings Data Structures: ------------------------ bitset.c Set operations implemented by a bitmap circ_queue.c Circular queue implementation deque.c Deque implementation + heap_static.c Heap implementation rbtree.cc Red Black Tree implementation + unionfind.c Set operations implemented by unionfind Dynamic Programming: ------------------------ + asc_subseq.c Longest ascending subsequence O(n log n) + asc_subseq2.c Longest ascending subsequence O(n^2) X bitonic_euclid_tsp.c Solve Bitonic Euclidiean travelling salesman problem + edit_dist.c Find the edit distance between two strings edit_dist_transpose.c Edit distance with transposes + integer_partition.c Find the # of ways to partition N into M pos. ints long_asc_subseq.c Finds the longest ascending subsequence + long_common_subseq.c Find the longest common subsequence between two strings + max_submatrix.c Find maximum submatrix sum X opt_binary_tree.c Finds optimal binary tree cost X opt_matrix_mult.c Finds optimal maxtrix multiplication sequence vecsum.c Finds the largest subvector sum Generators: ------------------------ + catalan.c Generates Nth Catalan number debruijn.c Generates Debruijn sequences + gen_bin_card.c Generates binary strings based ordered by # of 1's + gen_ksubset.c Generate subsets of size k, (lex, colex, minchange) X gen_perfect_match.c Generates all pairs of perfect matchings X gen_perm_lex.c Generates permutations in lexographical order gray_code.c Generates Gray codes + nqueens.c Generates a solution for the N-Queens problem in O(n) + pyth.c Generate pythagorean triples Graph Theory: ------------------------ + articulation_pts.c Finds the articulation points of a graph + bellmanford.c Shortest path allowing negative weights biconnect.c Finds biconnected components of a graph + bipartitematch.c Finds maximum matching in bipartite graph (v2) bipartite_matching.c Finds max matching in bipartite graph bridges.cc Find articulating points and bridges in a graph dijkstra.c Shortest path from a single point dijkstra_sparse.c Shortest path from a single point in spare graph ? escape.c Generic escape problem solver + euler.c Checks for Eulerian graphs, finds Euler paths/cycles + euler_d.c Template for directed Eulerian graphs + floyd.c All pairs shortest path floyd_path.c All pairs shortest path with path recovery + maxflow.cc Finds maximum flow in a directed graph O(|V|^2*|E|) + maxflow_v2.cc Find max flow in a directed graph O(|V|^3) + maxflow_lb.cc Finds max flow in a network with upper/lower bounds + minpath_vertexcover Min # vertex-disjoint paths covering acyclic digraph min_span_tree.c Finds a minimal spanning tree + min_span_tree2.c Finds a minimal spanning tree version 2 + postman.c Solves the Chinese Postman problem + scc_d_tour_kcycle.cc Find k-cycle in directed tournament graph + stable.c Solves the stable marriage problem + strong_conn.cc Finds strongly-connected components in digraphs + top_sort.cc Find a topological sorting of a DAG + tree_isomorph.cc Computes certificate for tree isomorphism + weighted_bipmatch.cc Weighted bipartite matching Java Templates: ------------------------ + base_convert.java Convert numbers from one base to another + BigDecimal.java Template for using BigDecimal in Java + BigInteger.java Template for using BigInteger in Java + IO.java Template for input/output formatting in Java X DataTypes.java Template for maps, vectors, hashtables in Java Miscellaneous: ------------------------ ispow2.c Determines if a number is a power of 2 + bitcount.c Counts number of set bits in a number ? keymap.txt Scancode something or others ispow2.c Don't know what it does, but it's short and cute next_permutation.c Use STL instead + roman.cc Conversion between Roman and Arabic numbers + rubik.c Rubik's cube simulator + sqr_index.c Routines for square rotation/flipping + strrev.c Reverses a string + ud_find.cc Find smallest lex-first ambiguous message + ud_test.cc Test if a set of codewords is uniquely decipherable NP Complete templates: ------------------------ X bin_packing.c Bin packing search X chromatic.c Chromatic color of a graph X subset_sum.c Subset Sum search X tsp_search.c Travelling Salesman search Number Theory: ------------------------ + binarygcd.c Find the gcd of two numbers (algorithm B) + eulerphi.c Calculates number of integers < N relative prime to N + factinfact.c Finds how many factors of k in N! + farey.cc Linear time/constant space Farey sequence generator + isprime.c Checks if a number if prime + num_divisors.c Calculates the number of positive divisors of N + primes.c Generates an array of primes up to N + primefactor.c Factor a number into primes + sum_divisors.c Calculates the sum of all positive divisors of N + sieve.c Fast primality testing Parsing: ------------------------ + infix_eval.c Parse a simple infix math expression (+,-,*,/) + infix_to_postfix.c Convert infix expression to postfix with prescedence X parse_bottomup.c Generalized bottom-up parsing template X parse_topdown.c Generalized top-down parsing template + parse_exp.cc Arithmetic expression parser (+,-,*,/,^,vars.) template Search Templates: ------------------------ X alpha_beta.c Generalized 2 Player Alpha-Beta Search bfs.c Generalized Breadth-First Search template + binsearch.c Generalized Binary Search template + cage.c Find minimum order (r-g) cages + color.c K-coloring template X dfs.c Generalized Depth-First Search template + golden.c Find the minimum value of a + hamming.cc Find maximum set of codewords with given hamming dist X hill_climbing.c Generalized Hill-Climbing template + ortho_latin.c Finds sets of orthogonal Latin squares + queen.c Find valid configurations for N non-attacking queens + suffix.c Build suffix arrary in O(n log n) X tri_search.c Generalized Trinary Search template + walk.c Find all self avoiding walks of length N + word_search.c Find all occurences of some strings in text