- 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.
- 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 )
- Bitonic sort in parallel.
In-switch anomaly detection using programmable switch.TCP, Transmission Control ProtocolTen programming assignments from Tsinghua Computational Geometry at edX
Only support 2-dimensional scenario.
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 ) |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 ) |
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 |
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() |
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 |
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 ) |
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() |
Description | Entry File/Link |
---|---|
keyframing | KeyFraming |
Linear Interpolation | static LinearInterpolation |
Spherical Linear Interpolation | static slerp |
Animation Program | index.html |
Example Video | Bilibili |
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 |
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 |
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 |
Description | Entry File/Link |
---|---|
Wireshark-like program(IPV4 packet analysis) | Pktsniffer.java |
Documentation | Instructions for Project 1 |
Description | Entry File/Link |
---|---|
RIP, Routing Information Protocol | RIP.java |
Documentation | Instructions for Project 2 |
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 |
Description | Entry File/Link |
---|---|
Build your own ping program | Xt1643Ping.py |
Build your own traceroute program | Xt1643Traceroute.py |
Documentation | Instructions for Lab3 |
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 |
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 ) |
Description | Entry File |
---|---|
Doubly Linked List ( With the ability to remove / insert a node directly from / into the list. ) | MyLinkedList.java |
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 |
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 |
Only support 2-dimensional scenario.
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 ) |
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 ) |
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 ) |
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 |
Description | Entry File/Package |
---|---|
Kd-tree | KdTree.java |
Range Tree | RangeTree.java |
Layered Range Tree ( Fractional Cascading ) | LayeredRangeTree.java |
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 |
Description | Entry File/Package |
---|---|
Trapezoidal Map | public class Trapezoid |
Search Structure( Tree-like DAG ) | public class SearchStructure |
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 |