TeaPort

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(&...

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...

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-degre...

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 ...

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(Ver...

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...

Intro to Troubleshooting and the Future of Networking Intro to Troubleshooting and the Future of Networking Error-detection: The ability for a protocol or program to determine that something went wrong. Eg: cyclic redundancy check Error-recovery: The ability for a protocol or program to attempt to fix it. Verifying Connectivity Pring: Internet Control Message Protocol Internet Control Message Protocol (ICMP): Mainly used for a router or a remote host to communicate why transmission has failed...

Google crash course Intro to Connecting to the Internet Intro to Connecting to the Internet Various Internet connection technologies. Wans and wireless and Cellular networking. POTS and Dial-up Dial-up, Modems and Point-to-Point Protocols Public switched telephone network (PSTN): This is also refered to as Plain old telephone service (POTS). The system is called USENET and still in use today. In the past, different organizations used the primitive form of Dial-up connection to exchange info...

Google crash course Networking Service Name Resolution DNS(Domain Name System): A global and highly distributed network service that resolves strings of letters into IP addresses for you. Domain Name: The term we use for something that can be resolved by DNS. Eg: Domian Name: www.weather.com IP address: 186.192.1.1 If the company wants to shift their original data center to another place, by using DNS, it can change what IP the domain resolves to and users will not know. DNS is of global st...