Problem Detail: We know that all graphs with odd cycles (odd number of vertices) are not 2-colorable. Is there a similar characterisation for 3-colorability? I am looking for undirected graphs that are not 3-colorable depending on a single graph property e.g. Read More …
Blog
[Solved]: Kruskal’s and Prim’s algorithm
Problem Detail: Does Kruskal’s and Prim’s algorithm work on directed graphs? I want the two algorithms to find a minimum spanning tree. For further enlightenment, I would like to know what other problems Kruskal’s and Prim’s can solve. So far, I Read More …
[Solved]: Why does the Count-Min Sketch require pairwise independent hash functions?
Problem Detail: The Count-Min Sketch is an awesome data structure for estimating the frequencies of different elements in a data stream. Intuitively, it works by picking a variety of hash functions, hashing each element with those hash functions, and incrementing the Read More …
[Solved]: How to prove the structured program theorem?
Problem Detail: Wikipedia: The structured program theorem […] states that […] any algorithm can be expressed using only three control structures. They are Executing one subprogram, and then another subprogram (sequence) Executing one of two subprograms according to the value of Read More …
[Solved]: Does every problem in NP have an exponential time algorithm?
Problem Detail: I am not sure that every problem in NP have an exponential time algorithm. Since NP does not mean “not polynomial.”, I think the answer is false. But I have no concrete reason about that. Asked By : Jung-Hyun Answered Read More …
[Solved]: detect closed shapes formed by points
Problem Detail: I plot several arrays containing xy-coordinates of points (using plot(x,y)) and obtain a plot with some curves. The curves form some very distinctive closed shapes (that is, the points describing the curves lie close to each other). Now I Read More …
[Solved]: Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart?
Problem Detail: Dijkstra’s algorithm (wiki) and Bellman-Ford (wiki) algorithm are two typical algorithms for the single-source shortest path problem. Both of them compute distances for all nodes from source $s$. If both source $s$ and destination $t$ are fixed, can we Read More …
[Solved]: How to reconstruct the image from a neural network output?
Problem Detail: I am trying to use the genetic algorithm to optimise a multi-layered neural network for image classification (i am using a subset of the MNIST handwritten digit data set as my initial dataset, but eventually would like to make Read More …
[Solved]: Points-in-a-plane from HackerRank
Problem Detail: I’ve been struggling with this problem for days now, making no progress: There are N points on an XY plane. In one turn, you can select a set of collinear points on the plane and remove them. Your goal Read More …
[Solved]: Difference between CRC and Hamming Code
Problem Detail: I am a bit confused on the difference between Cyclic Redundancy Check and Hamming Code. Both add a check value attached based on the some arithmetic operation of the bits in the message being transmitted. For Hamming, it can Read More …
