Polynomial Multiplication

Given two polynomials and of degree-bound : Multiply  and , we get the product with coefficients: Here  is also called the Convolution of  and  (denoted ). If we calculate  by multiplying each term in by each term in  and then combining terms with equal powers (exactly the old way we learnt in the junior high school), the time complexity would … Continue reading "Polynomial Multiplication"

Read More

[Algorithm 101] Shortest Path Problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. Dijkstra’s algorithm For a given vertex called the source in a weighted connected graph, Dijkstra’s Algorithm can find the shortest paths to all the graph’s other vertices. This algorithm is applicable to both undirected … Continue reading "[Algorithm 101] Shortest Path Problem"

Read More

[Algorithm 101] Topological Sorting

A directed acyclic graph (DAG) is not only necessary but also sufficient for topological sorting to be possible. DFS Perform a DFS traversal and note the order in which vertices become dead-ends (i.e., popped off the traversal stack). Reversing this order yields a solution to the topological sorting problem, provided, of course, no back edge has been encountered … Continue reading "[Algorithm 101] Topological Sorting"

Read More

Matrix Multiplication: A Programmer’s Perspective

The problem find the nth fibonacci number(A000045) has an optimal solution: matrix multiplication. Similarly, the matrix representation of sequence An = An-1 + An-2 + An-3 (A000073) is: By using matrix multiplication, we can reduce the time complexity from O(n) to O(logn). In linear algebra textbooks, matrix multiplication is the composition of two linear functions. Suppose: Represent … Continue reading "Matrix Multiplication: A Programmer’s Perspective"

Read More

Online Judge from Scratch(2) – Dispatcher

The dispatcher, as the name implies, fetches judge tasks from RabbitMQ, dispatches them to the sandbox workers and gets the results back synchronously. In Justice, the sandboxes are language-specific: If the submission is written in Java, we can sandbox it with Java Security Manager. If the submission is written in C/CPP, we need another sandbox … Continue reading "Online Judge from Scratch(2) – Dispatcher"

Read More

Online Judge from Scratch(1) – Frontend

The frontend of Justice contains two sites: the web UI for users and the admin panel for administrators, the main reason to choose Yii2 is the Advanced Application Template provides both succinct project structure and great convenience to share the same logic between the two sites: Besides, we improved Yii2’s MVC pattern by adding an … Continue reading "Online Judge from Scratch(1) – Frontend"

Read More