Problem Detail: Given weighted directed graph $G = (V,E,w)$, where $w : E to mathbb R^+$ source vertex $v in V$ vertex subset $U subset V$ how to find a shortest directed path from $v$ containing all vertices from $U$? Note Read More …
Category: Uncategorized
[Solved]: Is this method really uniformly random?
Problem Detail: I have a list and want to select a random item from the list. An algorithm which is said to be random: When you see the first item in the list, you set it as the selected item. When Read More …
[Solved]: Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?
Problem Detail: I just wrote a program that runs the Travelling Salesman Problem using the Nearest Neighbor Algorithm. Afterwards, I started looking into Minimum Spanning Trees (MST). From my understanding: The Nearest Neighbor Algorithm traverses a graph starting at one vertex, Read More …
[Solved]: TSP genetic algorithm: what mutation function for adjacency representation?
Problem Detail: When implementing TSP GA I decided for adjacency representation (i.e. $j$ value in $i$-th index means that node $j$ goes right after node $i$), as it enables interesting heuristical crossover operation (see Greffenstette, 1985). However this source, like many Read More …
[Solved]: Shannon Entropy to Min-Entropy
Problem Detail: In many papers I’ve read that it is well known that the Shannon entropy of a random variable can be converted to min-entropy (up to small statistical distance) by taking independent copies of the variable. Can anyone explain to Read More …
[Solved]: P, Q, ((P→Q)→R) ⊢ R using only modus ponens
Problem Detail: Can $R$ be inferred from $P$, $Q$, and $(P to Q) to R$ using only modus ponens? My understanding is that it can, as shown below, but I was told this was incorrect. Proof of ${P, Q, (P to Read More …
[Solved]: How to write a many-one reduction proof
Problem Detail: Writing a proof by contradiction is fairly formulaic–first you assume the opposite, then derive a contradiction. I would like to know the steps and conventions for writing a many-one reduction proof. This answer was somewhat helpful, but like other Read More …
[Solved]: Big-Endian/Little-Endian argument – paper by Danny Cohen
Problem Detail: Reading a book I was redirected to “On holy wars and a plea for peace” paper by Danny Cohen, which covers the “holy war” between big-endians and little-endians considering byte-order. Reaching the summary of the memory section I got Read More …
[Solved]: What is the difference between oblivious and non-oblivious merging, sorting etc
Problem Detail: Algorithms can either be oblivious or non-oblivious, but what is the actual difference between the two? Asked By : Summer Answered By : Evil Oblivious means that the control flow is independent of some properties of data. For example Bitonic Sort Read More …
[Solved]: Does every large enough string have repeats?
Problem Detail: Let $Sigma$ be some finite set of characters of fixed size. Let $alpha$ be some string over $Sigma$. We say that a nonempty substring $beta$ of $alpha$ is a repeat if $beta = gamma gamma$ for some string $gamma$. Read More …
