From 3daadcecd8525514918341b9c7c722480912582e Mon Sep 17 00:00:00 2001 From: Jakob Cornell Date: Mon, 2 Sep 2019 16:20:50 -0500 Subject: [PATCH] Initial commit --- .gitignore | 1 + algorithms/dijkstra/impl/java/Graph.java | 50 ++++++++ algorithms/dijkstra/impl/java/Main.java | 35 ++++++ algorithms/dijkstra/impl/python3/dijkstra.py | 24 ++++ algorithms/dijkstra/impl/python3/usage.py | 16 +++ algorithms/dijkstra/topic.tex | 43 +++++++ algorithms/hull-2d/impl/java/Hull.java | 49 ++++++++ algorithms/hull-2d/impl/java/Main.java | 14 +++ algorithms/hull-2d/impl/python3/hull.py | 15 +++ algorithms/hull-2d/impl/python3/usage.py | 2 + algorithms/hull-2d/topic.tex | 30 +++++ .../network-flows/impl/java-junk/FlowNet.java | 117 ++++++++++++++++++ .../network-flows/impl/java-junk/Main.java | 28 +++++ algorithms/network-flows/impl/java-junk/usage | 22 ++++ .../network-flows/impl/python3/flows.py | 67 ++++++++++ algorithms/network-flows/topic.tex | 19 +++ config.py | 30 +++++ contributors | 6 + doc.tex | 39 ++++++ license | 7 ++ makefile | 22 ++++ readme | 20 +++ todo | 8 ++ 23 files changed, 664 insertions(+) create mode 100644 .gitignore create mode 100644 algorithms/dijkstra/impl/java/Graph.java create mode 100644 algorithms/dijkstra/impl/java/Main.java create mode 100644 algorithms/dijkstra/impl/python3/dijkstra.py create mode 100644 algorithms/dijkstra/impl/python3/usage.py create mode 100644 algorithms/dijkstra/topic.tex create mode 100644 algorithms/hull-2d/impl/java/Hull.java create mode 100644 algorithms/hull-2d/impl/java/Main.java create mode 100644 algorithms/hull-2d/impl/python3/hull.py create mode 100644 algorithms/hull-2d/impl/python3/usage.py create mode 100644 algorithms/hull-2d/topic.tex create mode 100644 algorithms/network-flows/impl/java-junk/FlowNet.java create mode 100644 algorithms/network-flows/impl/java-junk/Main.java create mode 100644 algorithms/network-flows/impl/java-junk/usage create mode 100644 algorithms/network-flows/impl/python3/flows.py create mode 100644 algorithms/network-flows/topic.tex create mode 100644 config.py create mode 100644 contributors create mode 100644 doc.tex create mode 100644 license create mode 100644 makefile create mode 100644 readme create mode 100644 todo diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..16be8f2 --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +/output/ diff --git a/algorithms/dijkstra/impl/java/Graph.java b/algorithms/dijkstra/impl/java/Graph.java new file mode 100644 index 0000000..eefd961 --- /dev/null +++ b/algorithms/dijkstra/impl/java/Graph.java @@ -0,0 +1,50 @@ +import java.util.*; + +public class Graph { + public Set nodes = new HashSet<>(); + + // only needed for repeated search + public void reset() { + for (Node n : nodes) { + n.seen = false; + n.dist = Long.MAX_VALUE; + n.prev = null; + } + } + + public void search(Node root) { + Set q = new HashSet<>(); + root.dist = 0l; + q.add(root); + + while (!q.isEmpty()) { + Node a = Collections.min(q); + q.remove(a); + if (a.seen) continue; + a.seen = true; + for (Node b : a.adj.keySet()) { + long d = a.dist + a.adj.get(b); + if (d < b.dist) { + b.dist = d; + b.prev = a; + q.add(b); + } + } + } + } +} + +class Node implements Comparable { + public boolean seen; + public long dist = Long.MAX_VALUE; + public Node prev; + public Map adj = new HashMap<>(); + + public boolean equals(Object o) { + return dist == ((Node) o).dist; + } + + public int compareTo(Node n) { + return Long.compare(dist, n.dist); + } +} diff --git a/algorithms/dijkstra/impl/java/Main.java b/algorithms/dijkstra/impl/java/Main.java new file mode 100644 index 0000000..8ca56a7 --- /dev/null +++ b/algorithms/dijkstra/impl/java/Main.java @@ -0,0 +1,35 @@ +import java.util.Collections; + +public class Main { + public static void main(String[] args) { + Graph graph = new Graph(); + Node a = new Node(); + Node b = new Node(); + Node c = new Node(); + Node d = new Node(); + Node e = new Node(); + Node f = new Node(); + + // add each node to `graph.nodes' + Collections.addAll(graph.nodes, new Node[] {a,b,c,d,e,f}); + + // make edges between nodes + a.adj.put(c, 6l); + b.adj.put(a, 9l); + c.adj.put(a, 6l); + d.adj.put(b, 2l); + d.adj.put(c, 11l); + e.adj.put(b, 14l); + e.adj.put(d, 9l); + e.adj.put(f, 7l); + f.adj.put(c, 15l); + f.adj.put(d, 10l); + + // search the whole graph, starting at node `e' + graph.search(e); + System.out.println(a.dist); + System.out.println(a.prev == b); + // be sure to reset the graph before performing another search + graph.reset(); + } +} diff --git a/algorithms/dijkstra/impl/python3/dijkstra.py b/algorithms/dijkstra/impl/python3/dijkstra.py new file mode 100644 index 0000000..3f8e6db --- /dev/null +++ b/algorithms/dijkstra/impl/python3/dijkstra.py @@ -0,0 +1,24 @@ +import math + +class Node: + def __init__(s, data = None): + s.data = data + s.adj = {} + + def search(s): + dists = {s: 0} + prev = {} + expl = set() + q = {s} + while q: + a = min(q, key = lambda n: dists.get(n, math.inf)) + q.remove(a) + if a not in expl: + expl.add(a) + for n in a.adj: + d = dists[a] + a.adj[n] + if d < dists.get(n, math.inf): + dists[n] = d + prev[n] = a + q.add(n) + return (dists, prev) diff --git a/algorithms/dijkstra/impl/python3/usage.py b/algorithms/dijkstra/impl/python3/usage.py new file mode 100644 index 0000000..6000afd --- /dev/null +++ b/algorithms/dijkstra/impl/python3/usage.py @@ -0,0 +1,16 @@ +a = Node() +b = Node('foo bar') +c = Node() +d = Node([1, 2, 3]) +e = Node() + +# each node has an adjacency `dict'; each key is the destination of an outward edge, and the corresponding value is the edge cost +a.adj[b] = 5 +b.adj[c] = 5 +c.adj[d] = 5 +a.adj[d] = 30 + +(dists, prev) = a.search() +assert e not in dists +assert dists[d] == 15 +assert prev[c] == b diff --git a/algorithms/dijkstra/topic.tex b/algorithms/dijkstra/topic.tex new file mode 100644 index 0000000..28e4d35 --- /dev/null +++ b/algorithms/dijkstra/topic.tex @@ -0,0 +1,43 @@ +{ +\newcommand{\BasePath}{\ProjRootPrefix/algorithms/dijkstra} + +\TopicHeader{Weighted Shortest Path: Dijkstra's Agorithm} + + Dijkstra's algorithm is useful for computing the shortest path between nodes in a graph where edges have nonnegative weights. + The worst-case performance of the algorithm is $O(E + V \log V)$, if the graph has $E$ edges and $V$ nodes. + + All implementations here provide as output, for each node, the following information: + \begin{itemize} + \item whether the node was reachable from the search root + \item the shortest distance between the root and the node + \item the previous node along the shortest path, i.e. the node that was being explored when this node was first found + \end{itemize} + Note that the path of nodes from the root to any reachable node can be computed by following the previous-node links iteratively until the search root is reached. + + The implementations use directed graphs, so in order to emulate searching an undirected graph, two directed edges going in opposite directions should be made for each edge in the desired undirected graph. + + \TopicSubHeader{Python 3} + + \inputminted{python}{\BasePath/impl/python3/dijkstra.py} + + The \texttt{Node} constructor accepts a \texttt{data} parameter. + Any value can be passed in, and it will be stored in the node to facilitate associating the nodes with data specific to the problem. + Here's a usage example: + + \inputminted{python}{\BasePath/impl/python3/usage.py} + + In this implementation, two dictionaries are returned which provide the distance and previous-node information. + To see if a node is reachable, simply check whether the node is a key in the first (distance) dictionary. + + \TopicSubHeader{Java} + + \centerline{\texttt{Graph.java}} + \inputminted{java}{\BasePath/impl/java/Graph.java} + + The code may be used as follows. + If you need to attach some data to the nodes, you could add a field to the \texttt{Node} class or use a \texttt{Map} to keep track of the association. + + \inputminted{java}{\BasePath/impl/java/Main.java} + + The visited flag, previous-node links, and distances are accessible as fields on the \texttt{Node} objects after the search. +} diff --git a/algorithms/hull-2d/impl/java/Hull.java b/algorithms/hull-2d/impl/java/Hull.java new file mode 100644 index 0000000..dbc0f2a --- /dev/null +++ b/algorithms/hull-2d/impl/java/Hull.java @@ -0,0 +1,49 @@ +import java.util.*; + +public class Hull { + static long dir(Point a, Point b, Point c) { + return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x); + } + static List hull(Set pts) { + if (pts.isEmpty()) { + return new ArrayList<>(); + } + Point s = Collections.min(pts, new Comparator() { + public int compare(Point a, Point b) { + int yCmp = Long.compare(a.y, b.y); + return yCmp == 0 ? Long.compare(a.x, b.x) : yCmp; + } + }); + LinkedList srt = new LinkedList<>(pts); + srt.remove(s); + Collections.sort(srt, new Comparator() { + double cos(Point p) { + return (p.x - s.x) / Math.sqrt((s.x - p.x)*(s.x - p.x) + (s.y - p.y)*(s.y - p.y)); + } + public int compare(Point a, Point b) { + return -Double.compare(cos(a), cos(b)); + } + }); + srt.addFirst(s); + if (srt.size() < 3) { + return srt; + } + LinkedList out = new LinkedList<>(srt.subList(0, 3)); + for (Point p : srt.subList(3, srt.size())) { + while (dir(out.get(out.size() - 2), out.get(out.size() - 1), p) <= 0) { + out.removeLast(); + } + out.add(p); + } + return out; + } +} + +class Point { + long x; + long y; + Point(long x, long y) { + this.x = x; + this.y = y; + } +} diff --git a/algorithms/hull-2d/impl/java/Main.java b/algorithms/hull-2d/impl/java/Main.java new file mode 100644 index 0000000..b7b61cc --- /dev/null +++ b/algorithms/hull-2d/impl/java/Main.java @@ -0,0 +1,14 @@ +import java.util.*; + +public class Main { + public static void main(String[] args) { + Point a = new Point(0, 0); + Point b = new Point(-2, 2); + Point c = new Point(0, 4); + Point d = new Point(2, 2); + Point e = new Point(0, 2); + + List hull = Hull.hull(new HashSet<>(Arrays.asList(new Point[] {a, b, c, d, e}))); + assert hull.equals(Arrays.asList(new Point[] {a, d, c, b})); + } +} diff --git a/algorithms/hull-2d/impl/python3/hull.py b/algorithms/hull-2d/impl/python3/hull.py new file mode 100644 index 0000000..c4ddd9d --- /dev/null +++ b/algorithms/hull-2d/impl/python3/hull.py @@ -0,0 +1,15 @@ +import math + +def hull(points): + if not points: + return [] + sx, sy = s = min(points, key = lambda p: p[::-1]) + cos = lambda p: (p[0] - sx) / math.sqrt((sx - p[0])**2 + (sy - p[1])**2) + dir_ = lambda ax, ay, bx, by, cx, cy: (bx - ax)*(cy - ay) - (by - ay)*(cx - ax) + points = [s] + sorted(points - {s}, key = cos, reverse = True) + stack = points[:3] + for p in points[3:]: + while dir_(*stack[-2], *stack[-1], *p) <= 0: + stack.pop() + stack.append(p) + return stack diff --git a/algorithms/hull-2d/impl/python3/usage.py b/algorithms/hull-2d/impl/python3/usage.py new file mode 100644 index 0000000..d8fff87 --- /dev/null +++ b/algorithms/hull-2d/impl/python3/usage.py @@ -0,0 +1,2 @@ +points = {(0,0), (-2,2), (0,4), (2,2), (0,2)} +assert hull(points) == [(0,0), (2,2), (0,4), (-2,2)] diff --git a/algorithms/hull-2d/topic.tex b/algorithms/hull-2d/topic.tex new file mode 100644 index 0000000..ca7efc8 --- /dev/null +++ b/algorithms/hull-2d/topic.tex @@ -0,0 +1,30 @@ +{ +\newcommand{\BasePath}{\ProjRootPrefix/algorithms/hull-2d} + +\TopicHeader{Convex Hull (2D)} + + Convex hull algorithms are given a collection of points and output a subset of just the outermost points. + Formally, the output is the points of a polygon within which lie all points in the input. + + The implementations here use a technique called Graham scan to compute the convex hull with time complexity $O(n \log n)$, where $n$ is the number of input points. + The output points are ordered: the bottom-most (and then leftmost) point appears first, then the remaining hull points in counterclockwise order. + + \TopicSubHeader{Java} + + \centerline{\texttt{Hull.java}} + \inputminted{java}{\BasePath/impl/java/Hull.java} + + This may be used as follows: + + \inputminted{java}{\BasePath/impl/java/Main.java} + + \TopicSubHeader{Python 3} + + \inputminted{python}{\BasePath/impl/python3/hull.py} + + To run the algorithm, pass a set of $(x, y)$ pairs (\texttt{tuple}s) to \texttt{hull}. + + A sample usage: + + \inputminted{python}{\BasePath/impl/python3/usage.py} +} diff --git a/algorithms/network-flows/impl/java-junk/FlowNet.java b/algorithms/network-flows/impl/java-junk/FlowNet.java new file mode 100644 index 0000000..de0f1b6 --- /dev/null +++ b/algorithms/network-flows/impl/java-junk/FlowNet.java @@ -0,0 +1,117 @@ +import java.util.*; + +class FlowNet { + Map nodes = new HashMap<>(); + long value; + Node source, sink; + + void addNode(Node n) { + nodes.put(n, false); + } + + Edge edgeFor(Node one, Node two) { + return one.edgeTo.containsKey(two) ? one.edgeTo.get(two) : two.edgeTo.get(one); + } + + long findMax() { + long value = 0; + + AP augPath = getPath(); + while (augPath != null) { + Node from, to = augPath.path.pop(); + while (!augPath.path.isEmpty()) { + from = to; + to = augPath.path.pop(); + edgeFor(from, to).sendTo(to, augPath.value); + } + value += augPath.value; + augPath = getPath(); + } + + return value; + } + + // for min cut + Set srcSide() { + Set srcSide = new HashSet<>(); + for (Node n : nodes.keySet()) { + if (nodes.get(n)) { + srcSide.add(n); + } + } + return srcSide; + } + + AP getPath() { + Map prev = new HashMap<>(); + Queue q = new LinkedList<>(); + q.offer(source); + prev.put(source, null); + while (!q.isEmpty()) { + Node n = q.poll(); + for (Node other : n.adj) { + Edge e = edgeFor(n, other); + if (e.capTo(other) > 0 && !prev.containsKey(other)) { + prev.put(other, n); + q.offer(other); + } + } + } + for (Node n : nodes.keySet()) { + nodes.put(n, prev.keySet().contains(n)); + } + + if (nodes.get(sink)) { + LinkedList path = new LinkedList<>(); + long value = Long.MAX_VALUE; + + Node n = sink, p = prev.get(n); + path.push(n); + while (p != null) { + value = Math.min(value, edgeFor(p, n).capTo(n)); + path.push(p); + n = p; + p = prev.get(p); + } + + AP ap = new AP(); + ap.path = path; + ap.value = value; + return ap; + } else { + return null; + } + } + + class AP { + LinkedList path; + long value; + } +} + +class Node { + Set adj = new HashSet<>(); + Map edgeTo = new HashMap<>(); +} + +class Edge { + Node from, to; + long cap, flow; + + Edge(Node f, Node t, long c) { + from = f; + to = t; + cap = c; + f.adj.add(t); + t.adj.add(f); + f.edgeTo.put(t, this); + } + + long capTo(Node n) { + return n == to ? cap - flow : flow; + } + + void sendTo(Node n, long amt) { + flow += n == to ? amt : -amt; + } +} diff --git a/algorithms/network-flows/impl/java-junk/Main.java b/algorithms/network-flows/impl/java-junk/Main.java new file mode 100644 index 0000000..1410824 --- /dev/null +++ b/algorithms/network-flows/impl/java-junk/Main.java @@ -0,0 +1,28 @@ +public class Main { + public static void main(String[] args) { + FlowNet net = new FlowNet(); + Node s = new Node(); + Node t = new Node(); + Node u = new Node(); + Node v = new Node(); + for (Node n : new Node[] {s,t,u,v}) { + net.addNode(n); + } + net.source = s; + net.sink = t; + new Edge(s, u, 20); + new Edge(s, v, 10); + new Edge(u, v, 30); + new Edge(u, t, 10); + new Edge(v, t, 20); + System.out.println(net.findMax()); + for (Node n : net.srcSide()) { + char name = 0; + if (n.equals(s)) name = 's'; + if (n.equals(t)) name = 't'; + if (n.equals(u)) name = 'u'; + if (n.equals(v)) name = 'v'; + System.out.println(name); + } + } +} diff --git a/algorithms/network-flows/impl/java-junk/usage b/algorithms/network-flows/impl/java-junk/usage new file mode 100644 index 0000000..008896d --- /dev/null +++ b/algorithms/network-flows/impl/java-junk/usage @@ -0,0 +1,22 @@ +Usage: + + FlowNet net = new FlowNet(); + + Node s = new Node(); + Node t = new Node(); + Node u = new Node(); + Node v = new Node(); + for (Node n : new Node[] {s,t,u,v}) { + net.addNode(n); + } + net.source = s; + net.sink = t; + + new Edge(s, u, 20); + new Edge(s, v, 10); + new Edge(u, v, 30); + new Edge(u, t, 10); + new Edge(v, t, 20); + + System.out.println(net.findMax()); + System.out.println(net.srcSide()); diff --git a/algorithms/network-flows/impl/python3/flows.py b/algorithms/network-flows/impl/python3/flows.py new file mode 100644 index 0000000..41ac788 --- /dev/null +++ b/algorithms/network-flows/impl/python3/flows.py @@ -0,0 +1,67 @@ +from collections import deque + +class Edge: + def __init__(s, frm, to, cap): + s.frm = frm + s.to = to + s.cap = cap + s.flow = 0 + + def cap_to(s, node): + return {s.frm: s.flow, s.to: s.cap - s.flow}[node] + + def add_to(s, node, amt): + s.flow += {s.frm: -amt, s.to: amt}[node] + + def other(s, node): + return {s.frm: s.to, s.to: s.frm}[node] + +class Node: + def __init__(s, data = None): + s.data = data + s.edges = set() + + @staticmethod + def edge(f, t, cap): + e = Edge(f, t, cap) + f.edges.add(e) + t.edges.add(e) + +def ff(nodes, src, sink): + def path(): + prev = {} + q = deque([src]) + while q: + n = q.popleft() + for e in n.edges: + o = e.other(n) + if o not in prev and e.cap_to(o) > 0: + prev[o] = e + q.append(o) + d = sink + p = deque() + while d in prev and d is not src: + p.appendleft((prev[d], d)) + d = prev[d].other(d) + return p if d is src else [] + + p = path() + val = 0 + while p: + amt = min(e.cap_to(d) for e, d in p) + val += amt + for e, d in p: + e.add_to(d, amt) + p = path() + + cut_src = set() + w = [src] + while w: + n = w.pop() + cut_src.add(n) + for e in n.edges: + o = e.other(n) + if o not in cut_src and e.cap_to(o) != 0: + w.append(o) + + return (val, cut_src) diff --git a/algorithms/network-flows/topic.tex b/algorithms/network-flows/topic.tex new file mode 100644 index 0000000..ed9685f --- /dev/null +++ b/algorithms/network-flows/topic.tex @@ -0,0 +1,19 @@ +{ +\newcommand{\BasePath}{\ProjRootPrefix/algorithms/network-flows} + +\TopicHeader{Network Flows: Edmonds--Karp} + + Network flows algorithms find the maximum flow through and the minimum cut of a flow network. + This terminology and relevant algorithms are covered in Algorithms (CS 280) at Oberlin. + + The implementations here use the Edmonds--Karp algorithm on flow networks with integer capacities. + The time complexity of the algorithm is $O\left( VE^2 \right)$, where $V$ and $E$ are the number of vertices and edges in the network, respectively. + + \TopicSubHeader{Java} + + Coming soon... + + \TopicSubHeader{Python 3} + + \inputminted{python}{\BasePath/impl/python3/flows.py} +} diff --git a/config.py b/config.py new file mode 100644 index 0000000..928f34d --- /dev/null +++ b/config.py @@ -0,0 +1,30 @@ +r''' +This file is responsible for configuring the document build. +Some/all parameters are passed to LaTeX as generated code, which is probably a bad idea, but oh well. + +The keys in the `config' dictionary are the command names to assign in LaTeX. +So if I use `FooBar' in the dictionary, then the command `\FooBar' is available to the LaTeX code. +Note that an error will be raised if one of these names matches an existing LaTeX command. +''' + +config = { + # whether to insert page breaks before reference items to ease lookup + 'RefPageBrk': False, + # languages for which to exclude implementations (java, python3) + 'exclude_langs': [], +} + +# Require LaTeX config var names to be alphabetic to prevent code injection and weird errors +def test_latex(name): + assert name.isalpha() + +def enc_bool(name, val): + test_latex(name) + return ( + '\\newbool{' + name + '}\n' + + '\\setboolean{' + name + '}{' + str(val).lower() + '}\n' + ) + +with open('output/latex-defines', 'w') as f: + f.write('% Beware! This file is autogenerated by the build system.\n') + f.write(enc_bool('RefPageBrk', config['RefPageBrk'])) diff --git a/contributors b/contributors new file mode 100644 index 0000000..1d362a4 --- /dev/null +++ b/contributors @@ -0,0 +1,6 @@ +Contributors + - Jakob Cornell (creator): LaTeX code, build system, Python/Java algorithm implementations + +Attribution + - Dijkstra's Algorithm implementations and complexity analysis based on content here: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm (reused under CC-BY-SA) + - convex hull implementation and complexity analysis based on content here: https://en.wikipedia.org/wiki/Graham_scan (reused under CC-BY-SA) diff --git a/doc.tex b/doc.tex new file mode 100644 index 0000000..17a16e4 --- /dev/null +++ b/doc.tex @@ -0,0 +1,39 @@ +\documentclass{article} + +\usepackage{minted} % for code listings +\usepackage[margin=1in]{geometry} % for margin adjustment +\usepackage{parskip} % replaces paragraph indentation with vertical space +\usepackage{float} % used for captions on code listings +\usepackage{ifthen} % for conditional inclusion (page breaks) + +\newcommand{\ProjRootPrefix}{..} + +% read build options +\input{\ProjRootPrefix/output/latex-defines} + +% included files use these commands to make their headers +\newcommand{\TopicHeader}{\subsection} +\newcommand{\TopicSubHeader}{\subsubsection} + +\newcommand{\RefBreak}{ + \ifthenelse{\boolean{RefPageBrk}}{\pagebreak}{} +} + +\setminted{ + breaklines=true, + tabsize=4, + xleftmargin=0.25in, +} + +\begin{document} + \tableofcontents + + \pagebreak + + \section{Algorithms} + \input{\ProjRootPrefix/algorithms/dijkstra/topic.tex} + \RefBreak + \input{\ProjRootPrefix/algorithms/hull-2d/topic.tex} + \RefBreak + \input{\ProjRootPrefix/algorithms/network-flows/topic.tex} +\end{document} diff --git a/license b/license new file mode 100644 index 0000000..8a04732 --- /dev/null +++ b/license @@ -0,0 +1,7 @@ +Copyright for this work is held by those listed in the `contributors' file. + +This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/4.0/ or send a letter to Creative Commons, PO Box 1866, Mountain View, CA 94042, USA. + +Note that the entire work, including LaTeX code, build software, and algorithm implementations, falls under this license. + +Please consult the license information for guidelines on redistributing parts of this project. Of course it is acceptable to use the code samples without attribution in personal software and in programming contests (so long as the work isn't redistributed). diff --git a/makefile b/makefile new file mode 100644 index 0000000..6edc49f --- /dev/null +++ b/makefile @@ -0,0 +1,22 @@ +# defensively depend on all files in the `algorithms' tree +ALG_FILES := $(shell find algorithms -type f) + +BUILD_CMD := ( cd output && pdflatex -shell-escape ../doc.tex ) + +all: doc + +doc: output/doc.pdf + +output/latex-defines: config.py + python3 config.py + +output/doc.pdf: makefile output/latex-defines doc.tex $(ALG_FILES) + # build twice for table of contents + $(BUILD_CMD) + $(BUILD_CMD) + +clean: + rm -rf output + mkdir output + +.PHONY: clean doc all diff --git a/readme b/readme new file mode 100644 index 0000000..0059876 --- /dev/null +++ b/readme @@ -0,0 +1,20 @@ +# Overview + +This project aims to (ultimately) provide a reference document covering any information useful to participants in college programming contests, which typically only allow printed materials. This primarily includes algorithm implementations and documentation, but the project may at some point support building custom selections of language and standard library documentation. The text and programming language coverage are to some extent tailored to use by Oberlin College students. + +# Build + +The following are currently needed to build the document using the Make build file: + - Make + - Python 3 + - `pdflatex' LaTeX compiler + - LaTeX packages (see `doc.tex') + - Unix shell environment (typical MacOS or Linux should work) + +Currently all LaTeX-related requirements are provided by the TeX Live distribution. + +To configure the document build, take a look at `config.py', which contains a configuration dictionary and a mechanism for passing values to LaTeX. To start the build, just run the command `make' from the project root. The document is placed at `output/doc.pdf'. + +# Contribution, attribution, and redistribution + +This document is intended to be freely editable and redistributable. For more information, see the `license' file. Please ensure that copyright and license restrictions are compatible with this project when adding algorithm implementations based on others' work. diff --git a/todo b/todo new file mode 100644 index 0000000..903d8cc --- /dev/null +++ b/todo @@ -0,0 +1,8 @@ +- add tests for implementations and automate +- implement configurable sections (select specific algorithms) +- copy useful stuff from https://en.wikibooks.org/wiki/Algorithm_implementation + - DFS, BFS, Bellman Ford, area of polygons, minimum spanning tree, brute force TSP + - canonical problems (24: ecna17 twentyfour, coin problem) +- overall techniques: simulation, dynamic programming, brute force +- look into language/stdlib docs, custom and/or full (see if full docs are well indexed) +- add problem descriptions -- 2.30.2