Introduction to Algorithm Repository

0. Overview

0.1 Implementation details

1. Dictionaries/HashMaps/HashSets may not be the solution we're looking for, so I haven't used Hash Table in the current implementation. We're always exploring an alternative solution that does not rely on the expected O(1) performance of operations involving a hash table. Well, the reason behind this is simply that this is an algorithm-based repository, not project-based one. We're eager for finding a cleverer and more amazing algorithm and data structure to solve the problem.
2. For computational geometry. Java is not that good at visualizing 3D scenario, so I thinking of not using Java when digging into 3D or higher-dimensions scenario. ( but there is indeed a 3D Java library )

0.2 updating plans

1. Bitonic sort in parallel.
2. In-switch anomaly detection using programmable switch.
3. TCP, Transmission Control Protocol
4. Ten programming assignments from Tsinghua Computational Geometry at edX

1. Algorithm

1.1 Computational Geometry

Only support 2-dimensional scenario.

1.1.1 Numerical Tests

Description	Entry method
toLeft test	boolean toLeft( Vector base1, Vector base2, Vector point )
inCircle test	double inCircle( Vector a, Vector b, Vector c, Vector p )

1.1.2 Convex Hull

Description	Entry method\File
Graham's Scan	List<Vector> grahamScan( List<Vector> points )
Brute force	List<Vector> slowConvexHull( List<Vector> points )
Program ( including visualization )	CG2017 PA1-1 Convex Hull / CG2017 PA5-2 Dynamic Convex Hull

1.1.3 Geometric Intersection

Description	Entry method\File
Line and line	Vector lineIntersect( Line l )
Segment and segment	Vector segmentIntersect( Line l )
Segment and Circle	Vector[] segmentCircle( Segment s, Circle c )
Line and Circle	Line lineCircleIntersect( Line line, Circle circle )
Brute Force	List<Vector> bruteForce( List<E> S )
Bentley Ottmann's algrithom( Intersection Of segment, ray, line and Circle )	List<EventPoint2D> findIntersection( List<IntersectionShape> S )
Program ( including visualization )	CG2017 PA1-2 Crossroad

1.1.4 Triangulation

Description	Entry method\File
Partionting monotone polygons	List<Face> makeMonotone( List<Vertex> vertices )
Triangulation	List<Face> triangulate( List<Face> monotonePolygons )
BFS in a dual graph	void BFS( int sizeOfGraph, DualVertex start, DualVertex end )
Funnel algorithm	List<Vector> Funnel( DualVertex startTriangle, Vector startPoint, Vector endPoint )
Program ( including visualization )	CG2017 PA2-1 Shortest Path in The Room
Pedagogical Aid Webpage	Pedagogical Aid of Triangulation

1.1.5 Voronoi Diagrams

Description	Entry method\File
Build Voronoi Diagrams	BoundingBox voronoiDiagrams( List<Vector> P )
Find on which cell ( Voronoi Face ) the query point is.	List<Face> findCell( SearchVertex v, Vector p )
Generate segments from Voronoi edges to compute the trapezoidal Map of the Voronoi Diagrams.	List<Line> getSegments( BoundingBox b )
Program ( including visualization )	CG2017 PA2-2 Find Dancing Partners

1.1.6 Delaunay Triangualtion

Description	Entry method\File
Build Delaunay Triangulation	Face delaunayTriangulation( List<Vertex> P )
Find a triangle piPjPk ∈ T containing pr.	DelaunayVertex get( Vector pr )
Program ( including visualization )	CG2017 PA3-1 Delaunay Triangulation

1.1.7 Point Location

Description	Entry method\File
Build trapezoidal Map and search structure	BoundingBox trapezoidalMap( List<Line> S, , List<Vector> Q )
Point Locatoin	SearchVertex get( Vector p )
Program ( including visualization )	CG2017 PA3-2 Which wall are you looking at

1.1.8 Orthogonal Range Query

Description	Entry method\File
Build Kd-tree	KdNode build( List<Vector> P, int d )
2D Range Query in Kd-tree	List<Vector> query( List<Vector> R )
Build Range Tree	RangeNode build( List<Vector> P )
1D Range Query in Range Tree	List<Vector> query1D( List<Vector> R )
2D Range Query in Range Tree	List<Vector> query2D( String[] R )
Build layered range tree with fractional cascading,	List<LayerNode> build( RangeNode n )
2D Range Query in Layered Range Tree	List<Vector> query( String[] R )
Program ( including visualization )	CG2017 PA4-1 Planar Range Query

1.1.9 Orthogonal Windowing Query

Description	Entry method\File
Build Interval Tree	IntervalNode build( List<LineNode> I )
Stabbing query with Interval Tree	List<Line> query( Vector q )
Build Interval Tree combing Range Tree	IntervalRangeNode build( List<LineNode> I )
Windowing query in Interval Range Tree	List<Line> query( List<Vector> R )
Build Interval Tree combing Priority Search Tree	PriorityNode build( List<LineNode> I )
Windowing query in Priority Interval Tree	List<Vector> query( QueryVector[] R )
Build Segment Tree	SegmentNode build( List<Interval> I )
Stabbing query with Segment Tree	List<Line> query( Vector q )
Build Segment Tree combing Range Tree	SegmentRangeNode build( List<Interval> I )
Windowing query in Segment Range Tree	List<Line> query( List<Vector> R )
Program ( including visualization )	CG2017 PA4-2 Orthogonal Windowing Query

1.1.10 MapOverlay & Boolean Operations

Description	Entry method\File
Computing the overlay of two subdivisions	Face compute( Face s1, Face s2 )
Compute the intersection of two subdivisions, P1 ∩ P2.	List<Face> intersection( Face s1, Face s2 )
Compute the union of two subdivisions, P1 ∪ P2,	List<Face> union( Face s1, Face s2 )
Compute the difference of two subdivisions, P1 \ P2.	List<Face> difference( Face s1, Face s2 )

1.1.11 Half-plane Intersection

Description	Entry method\File
Compute half-plane intersection.	void intersect( List<HalfPlane> H )
Get current result type.	Type getResultType()
Program ( including visualization )	CG2017 PA5-2 FruitNinja

1.1.12 Duality

Description	Entry method\File
Transform this point in the primary plane into the dual plane, point to line.	Line toDuality()
Transform this point in the dual plane into the primary plane, point to line.	Line fromDuality()
Transform this line in the primary plane into the dual plane, line to point.	Vector toDuality()

1.2 POJ

Problem	Description	Entry File
Subsequence(ID 3061)	Two approaches, binary search and ruler	Subsequence.java
Face The Right Way(ID 3276)	One approach, switch	FaceTheRightWay.java

1.3 Sorting

Description	Entry method\File
Counting sort	void countingSort( List<NumberRadix> numbers, ... )
Radix sort	List<NumberRadix> radixSort( long[] arr, int radix )
Insertion sort	void insertionSort( List<E> arrayToSort )
Merge sort	List<E> mergeSort( List<E> arrayToSort )
Bucket sort	void bucketSort( List<Double> arrayToSort )

1.4 Graph

Description	Entry method\File
Breath First Search, BFS	void BFS( int sizeOfGraph, Vertex start, Vertex end )
Depth Frist Search, DFS	int DFS( Vertex vertex, boolean[] visited )
DFS in Haskell	dfs :: ( Ix i ) => Graph i -> [ Vertex i ] -> Forest ( Vertex i )
Bellman Ford( Constricted to make only one edge of progress at a given step)	void constrictedBellmanFord( Graph<ShortestVertex> aGraph ... )
Find the max flow in a internet flow	int findMaxFlow( InternetFlowVertex start )
Get all matching from a bipartite matching	List<List<InternetFlowVertex>> getAllMatching()

1.5 Animation

1.5.1 keyframing

Description	Entry File/Link
keyframing	KeyFraming
Linear Interpolation	static LinearInterpolation
Spherical Linear Interpolation	static slerp
Animation Program	index.html
Example Video	Bilibili

1.5.2 Collision System

Description	Entry File/Link
Collision Object	CollidingObject
Detect collision and trackback to the point where the first collision happens	static detectCollision
Binary Search to find the point where the first collision happens	static __binarySearchCollision
Find collided objects( brute force )	static __isColliding
Animation Program - Billiards	index.html
Example Video	Bilibili

1.5.3 Motion Capture System

Description	Entry File/Link
Set up Articulated Figures from the Skeleton in three.js	static setupShapes
Animate Hierarchical Models	static orientBone
Animation Program	index.html
Example Video	Bilibili

1.5.4 Particle System

Description	Entry File/Link
Particle System	ParticleSystem
Get random Unit Vector3 bounded by a given Cone.	randomUnitVector3InCone
Animation Program - comet	index.html
Animation Program - Static wall and gravity applied	SaticWall.html
Example Video	Bilibili

1.6 Networking

1.6.1 Packet Analysis

Description	Entry File/Link
Wireshark-like program(IPV4 packet analysis)	Pktsniffer.java
Documentation	Instructions for Project 1

1.6.2 RIP

Description	Entry File/Link
RIP, Routing Information Protocol	RIP.java
Documentation	Instructions for Project 2

1.6.3 TCP

Description	Entry File/Link
File Transfer Protocol (FTP) using self-implemented TCP.	MyFTP.java
TCP Socket	MySocket.java
Send data in byte to the receiver.	boolean send( byte[] t, ...... )
Try to connect to the other side. / Close this socket and notify the other side to close.	connect() / close()
Documentation( including My FTP instructions )	Instructions for Project 3
Implementing TCP with UDP	Implementing TCP with UDP

1.6.4 Ping & Traceroute

Description	Entry File/Link
Build your own ping program	Xt1643Ping.py
Build your own traceroute program	Xt1643Traceroute.py
Documentation	Instructions for Lab3

1.6.4 in-switch anomaly detection

Description	Entry File/Link
Detect network attacks, like DDos or flood attacks, using programmable switch	inswitch_anomaly repositories
P4 entry file	inswitch_anomaly.p4
P4 package	includes
Python package	fengkeyleaf

1.7 Boolean Operation

Description	Entry File/Link
Boolean Operation( Not perfect )	BExp.java
Get a boolean expression containing evaluating expression and target to be evaluated.	BExp<T> getBool( T t, Predicate<T> p )
Get an AND expression, a And b.	BExp<T> getAnd( BExp<T> a, BExp<T> b )
Get a OR expression, a Or b.	BExp<T> getOr( BExp<T> a, BExp<T> b )
Get a NOT expression, Not a.	BExp<T> getNot( BExp<T> a )
Evaluate this boolean expression.	boolean evaluate()
Assemble target objects into this boolean expression.	assemble( T... T )

2. Data Structure

2.1 Basics

Description	Entry File
Doubly Linked List ( With the ability to remove / insert a node directly from / into the list. )	MyLinkedList.java

2.1 Tree

Description	Entry File
Binary Search Tree ( put(), deleteMin(), deleteMax(), delete(), min(), max(), etc.)	BinarySearchTree.java
Red Black Tree ( put(), deleteMin(), deleteMax(), delete(), min(), max(), etc. )	RedBlackTree.java
Segment Tree ( Range maximum and minimum Query )	SegmentTree.java
Priority Queue	MyPriorityQueue.java
Doubly Linked Binary Search Tree ( With the ability delete / insert a node directly from / into the BST )	DoublyLinkedBST.java
Doubly Linked Red Black Tree ( With the ability delete / insert a node directly from / into the R-B Tree )	DoublyLinkedRBT.java

2.2 Graph

Description	Entry File
Graph	Graph.java
Graph in Haskell	Graph.hs
Strongly connected component, SCC	SCC.java
Directed acyclic graph, DAG	DAG.java
Minimum spanning tree, MST.	MST.java
Union Find	UnionFind.java
Internet Flow	InternetFlow.java
Bipartite Matching	BipartiteMatching.java

2.3 Computational Geometry

Only support 2-dimensional scenario.

2.3.1 DCEL

2.3.1.1 Vertex

Description	Entry File
Get all incident edges of the vertex	public List<HalfEdge> allIncidentEdges()
Find the first ClockWise Edge with two vertices destination and origin	HalfEdge firstClockWiseEdge( Vertex origin )
Find the first CounterClockWise Edge with two vertices destination and origin	HalfEdge firstCounterClockWiseEdge( Vertex destination )
Connect two vertices by adding new half-edges	Face connect( Vertex v )
Re-connect half-edges incident to this vertex.(Duality Implementation)	void connect( List<HalfEdge> E )

2.3.1.2 Half-edge

Description	Entry File
Walk around all halfEdges connected to this one, and get vertices incident to them.	List<Vertex> walkAroundVertex()
Walk around and get all halfEdges connected to this one.	List<HalfEdge> walkAroundEdge()
Split the edge into two parts	Vertex split( Vertex split )
Get all inner faces bounded by this half-edge, but not including holes.	Collection<HalfEdge> getInners()
Sort half-edges in clock wise order with the point i as the center.	List<HalfEdge> sortInClockWise( List<HalfEdge> E, Vector i )

2.3.1.3 Face

Description	Entry File
Walk around all halfEdges, starting at this face and get visited halfEdges.	List<HalfEdge> walkAroundEdge()
Walk around all halfEdges, starting at this face and get visited vertices.	List<Vertex> walkAroundVertex()
Is the point inside this convex hull? but excluding the boundary.	boolean isInsideConvexHull( Vector p )
Is the point on this convex hull? including the boundary.	boolean isOnConvexHull( Vector p )
Is the point inside This Polygon?	boolean isInsidePolygon( Vector p )
Is the point On This Polygon?	boolean isOnPolygon( Vector p )

2.3.2 Shapes

Description	Entry File/Package
Vector (2D Point)	Vector.java
BoundingBox ( Bounding box for a half plane )	BoundingBox.java
Arc	Arc.java
Circle	Circle.java
Line	Line.java
Ray	Ray.java
Segment	Segment.java
Parabola	Parabola.java
HalfPlane	HalfPlane.java

2.3.3 Space Trees

2.3.3.1 Orthogonal Range Query

Description	Entry File/Package
Kd-tree	KdTree.java
Range Tree	RangeTree.java
Layered Range Tree ( Fractional Cascading )	LayeredRangeTree.java

2.3.3.2 Orthogonal Windowing Query

Description	Entry File/Package
Interval Tree	IntervalTree.java
Segment Tree	SegmentTree.java
Interval Range Tree	IntervalRangeTree.java
Priority Interval Tree	PriorityIntervalTree.java
Segment Range Tree	SegmentRangeTree.java

2.3.4 Point Location

Description	Entry File/Package
Trapezoidal Map	public class Trapezoid
Search Structure( Tree-like DAG )	public class SearchStructure

2.4 Networking

Description	Entry File/Package
Pacp file	Pacp.java
Packet	Packet.java
Internet Protocol version 4	IPv4.java
User Datagram Protocol	UDP.java
Transmission Control Protocol	TCP.java
Internet Control Message Protocol	ICMP.java
Logging System	MyLogger.java