Pratik Deoghare
  • Member for 11 years, 5 months
  • Last seen more than a month ago
Paths and Probabilities for a Random Walk on a Graph
1 votes

You can make a state machine from this as follows. Let the set of points generated be $V$. Add extra dummy start node $s$. Add edges $(s, v)$ for all $v \in V$. And add edge from $(u, v)$ where $...

View answer
Great algorithms, machine learning and no linear algebra
4 votes

This algorithm uses graph minimum cuts to classify large amount of unlabeled samples using only small amount of labelled samples. Its undergrad friendly. I have explained this to a few randomly ...

View answer
Hard-looking algorithmic problems made easy by theorems
9 votes

Theorem: Every planar graph has a vertex with degree at most 5. Problem: Design an $O(n)$ representation of planar graphs where we can check if $(u, v)$ is an edge in $O(1)$ time. We can remove the ...

View answer
Hard-looking algorithmic problems made easy by theorems
20 votes

This afternoon I was reading Stringology -- the "Real" string theory. Problem: If $x$ and $y$ are two strings over some alphabet when are there some positive integers $m, n$ such that $x^m = y^n$. ...

View answer
What is this notation style called?
Accepted answer
4 votes

It is notation for Formal Proofs and specification of language grammar in Backus-Naur Form.

View answer
How to Create Mission Critical Software?
0 votes

Certifying algorithms can be useful when building mission critical software. A certifying algorithm is an algorithm that produces, with each output, a certificate or witness (easy-to-verify proof)...

View answer
Application of calculus in computer science
1 votes

Oh hell yes! Lagrange Multipliers (Entropy example) Relation between crossing numbers of complete and complete bipartite graphs Simpler version of Stirling’s approximation It is impossible to write ...

View answer
Concepts in theoretical CS that would be approachable ages 8-14
21 votes

Fun way to learn $\lambda$-calculus: ...This game represents the untyped lambda calculus. A hungry alligator is a lambda abstraction, an old alligator is parentheses, and eggs are variables. The ...

View answer
Efficient encoding of integers with constant digit sum
1 votes

$X = \{\{0,5\}, \{1,4\}, \{1,1,3\}, \{1,1,1,2\}, \{1,1,1,1,1\}, \{2,3\}, \{2,2,1\} \}$ $X$ is partition of 5 where only single digit numbers are allowed. Observation: Any number with digit sum 5 can ...

View answer
Joining lists with some common elements in average case
-1 votes

def F(a,b): M = max(max(a),max(b)) C = BitArray of size M FOR x in a: C[x] = 1 FOR y in b: C[y] = 1 FOR z in range(0,M): IF C[z] == 1: c.append(...

View answer
Genetic Algorithm to Draw a Graph? Position assignment problem
2 votes

TimGA - A Genetic Algorithm for Drawing Undirected Graphs A Numerical Optimization Approach to General Graph Drawing I was given task similar to yours on my job. I used two things given above. Both ...

View answer
Reducing redundant edges from a dependency graph
Accepted answer
13 votes

The Transitive Reduction of a Directed Graph A. V. Aho, M. R. Garey, and J. D. Ullman According to wikipedia, this algorithm is used by tred which is tool for transitive reduction available in ...

View answer
Quantum Bell-Type Inequalities
4 votes

I haven't read the paper you linked to but a must must read paper on Bell Inequalities is Hidden variables and the two theorems of John Bell by N. David Mermin. He has written a lot on Bell ...

View answer
Is there a local variant of TSP?
0 votes

You can sell for $n$ days. Suppose your average speed is $S$ km/day. Then you can only travel $nS$ km (that too if you can sell things in 0 seconds). Let $EP(c)$ be estimated profit for city $c$. ...

View answer
Selecting papers to read
6 votes

Take 100 papers. Sort by number of citations. Take top 50. Go to the list references at the end of each paper. Make a big list using all those references. Sort by number of times some paper appears ...

View answer
Construction of graph embeddings with non-intersecting edges
Accepted answer
4 votes

The problem of finding the graph genus is NP-hard (the problem of determining whether an n-vertex graph has genus g is NP-complete). In this case you already know the genus. At the same time, the ...

View answer
Software for Graph Analysis
Accepted answer
4 votes

SAGE supports interactive graph drawing. You can easily create customized software for your own use. Graph editor

View answer
What math courses should I take to prepare for a CS masters or PhD?
Accepted answer
11 votes

There is a course at MIT OCW called Mathematics for Computer Science, it lists some topics you MUST cover. Learning some Abstract algebra will be a big plus. Because I see too many references to ...

View answer
Circle graph visualisation
3 votes

cr(G) - Crossing Number is minimum number of crossings with which a graph can be drawn. If you are using only straight line edges then its called Rectilinear Crossing Number. Determining cr(G) is NP-...

View answer
Explain P = NP problem to 10 year old
21 votes

In this talk Scott Aaronson addresses the question. TEDxCaltech - Scott Aaronson - Physics in the 21st Century: Toiling in Feynman's Shadow Warning: Please, do NOT show this talk directly to your ...

View answer
Generation of unlabeled acyclic digraphs
3 votes

Counting unlabeled acyclic digraphs -- R. W. Robinson

View answer
Research data organization
2 votes

Zotero Firefox plug-in

View answer
Testing/Identifying a Topological Sorting
0 votes

Trivial Method: GS = {G1,G2...G3} for v in (v1,v2,...vm) remove all graphs from GS where indegree(v) != 0 remove v and attached edges from remaining GS It is not as fast as you want. But ...

View answer
Special Properties Of DAWGs with Unique Elements
0 votes

DAWGs are most probably posets and close relatives of Finite Automata. So special properties of posets and FA should apply to DAWGs too.

View answer
Searching for matching queries
1 votes

Create a new table with only one object i.e. object X Execute all the queries on it. Discard those which return nothing. Remaining queries are the queries that match your object X. This will be ...

View answer
Finding twin vertices in graphs
1 votes

Some observations that might help For $a,b \in V$ if $a$ is not twin of $b$ then $c$ and $d$ can't be twins where $c \in N(a)$ and $d \in N(b)$. $|N(a)| \neq |N(b)|$ then $a$ and $b$ can't be twins. ...

View answer
Formal notion for energy complexity of computational problems
-3 votes

Time and space complexities are device independent. I don't see a way to make energy-complexity device independent. If $W$ is work done by a Turing machine to perform one basic step. Then energy ...

View answer
Where do I turn for help with research/publishing?
1 votes

You can write your ideas down in standard paper format. Publish it on ArXiv. Share source code on github. Spend some time learning run time analysis and update your paper when you are done. e.g. ...

View answer
Is there a polynomial-time algorithm to solve graph isomorphism for Delaunay graphs of (finite) hexagonal tessellations?
Accepted answer
15 votes

I guess all those subgraphs will be planer graphs. And I think that there is efficient algorithm for isomorphism of planer graphs. ref: Linear time algorithm for isomorphism of planar graphs by J. ...

View answer
Computing the Levenshtein distance quickly
2 votes

You can use Did you mean? And then find the Levenshtein distance between the answer returned by "Did you mean"" and input string using Dynamic Programming.

View answer