TeaPort

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

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

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

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]){...

Zhejiang University Graph It is used to represent a many-to-many relationship. It is so powerful because it includes both linear lists(one to one) and trees(one to many). Components Vertex(V): the set of all vertexes. Edge: the set of all sides. (v, w). Double directions. . From v to w (single direction). No multiple edges or multiple loops. A Quick Review: Definition of Abstract Data Type Name: Graph DataSet: G(V, E). V is Nonempty E is limited. Operation Set Graph Create() Graph Ins...

Zhejiang University Set Operations There are some basic operations about sets. Eg: Union, Intersection, Set Difference… Union-Find Set Problem: There are n nodes. Some of them are connected. How do we know whether arbitrary 2 of them are connected? Answer: Make n sets to include n nodes. Then union those connected. Find whether 2 given nodes are in the same set. Creating Union-Find Set How to Store a Set? Tree. The root will be a set. Each node will be an element. Parental Representation: T...

Zhejiang University Huffman Tree Question: How can we fit a 100 mark test into a 5 standards judging system? We need to carefully arrange our if clauses in accordance with the frequency of the actual result. (Decision Tree) Cost: ∑ratio×layers\sum\rm ratio\times layers∑ratio×layers Definition Weighed Path Length: A binary tree with n nodes with weight w. The distance between root and each leaf is l. Then the WPL for each leaf node will be WPL=∑i=1nwklkWPL = \sum_{i=1}^nw_kl_k WPL=i=1∑n​wk​l...

Zhejiang University Heap What is heap? When a computer is doing many things at the same time, different tasks will have different priorities. Thus we have a special data structure: Priority Queue. Creating a heap We need 2 functions: insert and delete Array difficult to delete a element linked list Ordered Array difficult to insert Ordered linked list Tree Tree Tree has some great characteristics in realizing heap. The insert process is related to the height of a tree while the delete pro...

Zhejiang University Binary Search Tree (BST) Properties Left subTrees’s values are smaller than their roots Right subTrees’s values are larger than their roots Left and Right subTrees are all BSTs API Position Find(ElementType X, BinTree BST) Position FindMin(BinTree BST) Position FindMax(BinTree BST) BinTree Insert(ElementType X, BinTree BST) BinTree Delete(ElementType X, BinTree BST) Find Recursion Loop 123456789while(BST){ if(X > BST->Data) BST = BST->Right; ...

Zhejiang University Binary Tree Properties Degree = 2. L and R are different. Layer i has a maximum number of nodes 2^(i-1) Degree = K, node sum = 2^(k-1) For any not-null binary tree, n0 = leaf, n2 = nodes which have 2 non-leaf nodes, then n0 = n2+1 Operation Set Boolean IsEmpty(BinTree BT) void Traversal(BinTree BT) PreOrderTraversal:rLR InOrderTraversal:LrR PostOrderTraversal:LRr LevelOrderTraversal:UD,LR BinTree CreatBinTree() Special Binary Tree Skewed Binary Tree Perfect Binar...