Didn’t do anything meaningful today.
One Interesting Problem
https://leetcode.cn/problems/count-paths-that-can-form-a-palindrome-in-a-tree/description/
Since parity of the palindrome, we only need to use a binary digit to record the existing of each character. Where we can map all the situations into integers under $2^{26}$. And we do XOR for each new added binary digit. The point is, the characters appear in the edge. Which means it path = i to root XOR j to root. lca(i,j) to root is cancelled due to the rule of XOR.
What if, say, the characters are in node rather than edges. We can then use Rerooting DP. However, we have to set up blocking to maintain the value.
CS371
Today we taught about using KNN, and the mothod of measuring the performance of KNN. Also a special method used to do NN, the vononoi diagram. The algorithm looks quite like “半平面交”, but I quite don’t know how to really implement it. Hopefully we don’t required to learn the algorithm.
CS521D
One interesting thing is an example in non-triangle graph. The hypercube graphs, we learned to measure $diag(G(d=i))$, if we ordered them in a binary way, say, the graph of $G(d=i+1)$ simply made of doubling with $G(d=i)$ and connecting them symmetricly. Each index, made out of binary, is said to become adjacency if there is only one digit difference in binary.
Neighbor, Local neighbor. We learned to evaluate ceartain features of the graph applying certain measurements. $\rho(G(V,E)=\frac{|E|}{\binom{|V|}{2}}$
Also why the triangle adjacent to a node can be measured by the edges in local neighbor graphs.
However, the quiz is quite tricky for a learner with poor english.
