Problem Detail: I am student of CS. Problem is, I feel that I don’t have enough math knowledge to solve mathematical problems. When some programming problems arises which needs some math skills to solve then despite of the fact that I Read More …
Category: Uncategorized
[Solved]: Are there hardware lock implementations without test-and-set or swap?
Problem Detail: Locks are usually implemented thru test-and-set and swap machine-level instructions. Are there other implementations that do not use these? Also, can we say that all hardware level solutions to the critical section problem can be categorized into just three, Read More …
[Solved]: The most efficient way of finding/storing neighbourhood info during octree creation
Problem Detail: Currently I have a program which at some point creates an octree and AFTER the creation loops through all the nodes, for every node (O(n2/2)) and thus finds the neighbours, by a brute-force box-box intersection check. Since that is Read More …
[Solved]: Travelling Salesman which can repeat cities
Problem Detail: In the TSP problem, we usually assume a complete graph. If we can only visit each city once, we need a complete graph to ensure that there will be a path from every city to every other city. This Read More …
[Solved]: Is there a TM that halts on all inputs but that property is not provable?
Problem Detail: Does there exist a Turing machine that halts on all inputs but that property is not provable for some reason? I am wondering if this question has been studied. Note, “unprovable” could mean a “limited” proof system (which Read More …
[Solved]: Identifying events related to dates in a paragraph
Problem Detail: Is there an algorithmic approach to identify that dates given in a paragraph correlate to particular events (phrases) in the paragraph? Example, consider the following paragraph: In June 1970, the great leader took the oath. But it was only Read More …
[Solved]: Is language equality for linear context-free grammars decidable?
Problem Detail: Let’s consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent? In general, this problem is undecidable. However, if both $G_1$ and $G_2$ are left-linear (or Read More …
[Solved]: Difference between time complexity and computational complexity
Problem Detail: For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them? I used to calculate the maximum (worst) count of basic (most costing) operation in the algorithm. Asked By : Median Read More …
[Solved]: Speed-up of two-tape Turing machine
Problem Detail: I try to figure out linear speed-up of Turing machine. Prove that any problem that can be solved by a two-tape Turing machine that has time complexity t can be solved by another two-tape Turing machine having time complexity Read More …
[Solved]: NP-hardness of covering with rectangular pieces (Google Hash Code 2015 Test Round)
Problem Detail: The Google Hash Code 2015 Test Round (problem statement) asked about the following problem: input: a grid $M$ with some marked squares, a threshold $T in mathbb{N}$, a maximal area $A in mathbb{N}$ output: the largest possible total area Read More …
