TeaPort

Seeing is believing. It used to be such a universally acknowledged viewpoint that almost all languages, eastern or western, possess similar expressions. Throughout history, this common idea has guided us and encouraged our ancestors to seek the truth, and, to some extent, it also leads to the advent of experimental science and other branches of scientific knowledge. With a deeper understanding of the world we live, people begin to doubt and challenge this proverb. Given the interest in, debate o ...

There is an intriguing fact in this age: when people turn on the television or their mobile phones, they frequently find out that there is abundant shocking news concerning celebrities. Most of them uncovers appalling dark sides of these people who seemed to be perfect and admirable in the past. It seems that no one is innocent under media scrutiny and it is only a matter of fact before some negative evidence appears. How do we interpret this phenomenon? Two main factors contribute to this fact. ...

When compiling, computer needs to manage variables: Inserting (new variables) Searching (references of variables) Dynamic Searching Problems Two main problems about Hashing: Calculating positions: creating a hashing function to locate the keyword Dealing with Collisions Hashing Table Name: SymbolTable Data Object Set: Name-Attribute Operation Set: 123456SymbolTable InitializeTable(int TableSize);bool IsIn(SymbolTable Table, NameType Name);AttributeType Find(SymbolTable Table, NameType Name); ...

Quick Sort Divide and Conquer Choosing the Principal Component Remark: rand() is not very efficient! One common approach is to use the median number at the head, tail and center of the array: 1234567891011ElementType Median3(ElementType A[], int Left, int Right) { int Center = (Left + Right) / 2; if (A[Left > A[Center]]) Swap(&A[Left], &A[Center]); if (A[Left] > A[Rihgt]) Swap(&A[Left], &A[Right]); if (A[Center] > A[Right]) Swap(&A[ ...

Lower Bound of Time Complexity Inversion For index i and j, if A[i] > A[j] then (i, j) is an inversion. For insertion sort: T(N,I)=O(N+I)T(N, I)=O(N+I) T(N,I)=O(N+I) Theorem A: For N different elements, the average number of inversions are I=N(N−1)/4I=N(N-1)/4 I=N(N−1)/4 Theorem B: For any algorithm which only swaps the adjacent 2 elements, the average time complexity is: From B we know that if we want to make our algorithms more efficient, we should eliminate more than one inversions each ti ...

When I tried to synchronize my site.db to github.com, something wrong happened. There is an error on nginx 502 Bad Gateway. When checking the error log on my server at: cat /var/log/flaskblog/flaskblog.err.log I found the error. 1sqlite3.OperationalError: attempt to write a readonly database To change the authority of writing in this database, I used: chmod a+rw ./site.db to give all users the authority to read and wirte this database file. This solves the problem.

Topological Sorting AOV(Activity On Vertex) network Topological Order a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. The process of getting the order is called topological sorting. If AOV has a reasonable topological order, it has to be DAG(Directed Acyclic Graph). Algorithm Find vertexes that has no in-degree, delete them and their out-degree. ...

Minimum Spanning Tree Characteristics A tree We can regard a tree as a special graph No loop |V| - 1 edges with |V| vertexes Spanning Include all nodes in this tree |V| - 1 edges are in the graph Minimum The weighted sum is minimum If there exists a minimum spanning tree, the graph must be connected. Greedy Algorithm Every step should be the optimal! Optimal means that the weight should be as little as possible Restrictions Only use the edges in the graph Use |V| - 1 edges No loo ...

Shortest Path Problem Find the minimum weight in all the paths between 2 vertexes. This is called the Shortest Path. The start point is called Source Vertex the end point is called Destination Vertex. Problems Single-source Shortest Paths (directed) Unweighted graph (directed) Weighted graph Multi-Source Shortest Paths Single Source Shortest Path Algorithm for Unweighted Graphs Find the shortest path in Non-decreasing order. It is very similar to BFS! 12345678910111213void Unweighted(Vertex ...

Zhejiang University Two Methods of Optimization Merge by Rank The tree can always grow higher and higher if it is not optimized properly! If we try to merge the higher tree to the lower one, the total height will increase by 1. Thus, we should avoid this kind of merging. To realize this optimization, we can store the height of the tree to the root node, in a negative way. Then the union function will be like: 123456789void Union(SetType s, SetName root1, SetName root2) { if (s[root1] & ...