TeaPort

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

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

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

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

Google crash course Transport and Application Layers Intro Transport layer: Allows traffic to be directed to specific network applications. Application layer: Allows these applications to communicate in a way they understand. The Transport Layer Multiplex and Demultiplex Processes Multiplexer IP IP Demultiplexer Processes The transport layer handles this multiplexing and demultiplexing through Ports. Port: A 16-bit number used to direct traffic to specific services running on a netwo ...

This is going to be a completely new part of my study in CS. This part won’t last long because I haven’t finished DataStructure and I’m going to learn assembly language. I learn this simply because my server was banned by the GFW and I need some extra knowledge to prevent this from happening again. Good Luck! Google Crash Course The Network Layer Describing the IP addressing scheme and subnetingworks. The Network Layer MAC addresses are useful in a small scale. But they are not ordered. Addres ...

Zhejiang University Understanding of the Puzzle We simply regard the trees as the same as long as they have the same children for every node. Divide and Conquer The representation of a binary tree Build a Binary Tree Judge whether they are Isomers. Representing a Binary Tree Static Linked List: A Special Array. Structure of the Program 12345678BinTree Build();bool Judge();int main(){ Build tree1; Build tree2; Judge isomers; return 0;} Design the Functions 12345678#define ...

Zhejiang University DFS(Depth First Search) 1234567void DFS(Vertex V){ visited[V] = true; for(each adjacent vertex w){ if(!visited[w]) DFS(w); }} Complexity Adjacent List: O(N+E)O(N+E)O(N+E) Adjacent Matrix: O(N2)O(N^2)O(N2) BFS(Breadth First Search) 1234567891011void BFS(Vertex V){ visited[V] = true; Enqueue(V, Q); while(!IsEmpty(Q)){ V = Dequeue(Q); for(each adjacent vertex W of V) if(!visited[V]){ ...