Problem Detail: I am in High School (P.R.) and I am a regular person in math. Should I try computer science? Asked By : Lean Answered By : Yuval Filmus This is a very subjective question, but generally speaking, a computer science degree Read More …
Blog
Is the language that accepts strings concatenated with their reverse regular?
Problem Detail: If the set of regular languages is closed under the concatenation operation and is also closed under the reverse operation ($x^R$ is the reverse of $x$) then is the language generated by $${ww^R|winSigma^*}$$ for some input alphabet $Sigma$, also Read More …
Intro to Martin-Löf type theory
Problem Detail: What would be the best introduction to Per Martin-Löfs ideas about type theory? I’ve looked at some lectures from the Oregon PL summer school, but I’m still sort of puzzled by the following question: What is a type? I Read More …
Understanding DPLL algorithm
Problem Detail: I’m trying to understand DPLL algorithm for solving SAT problem. And here it is: Algorithm DPLL Input: A set of clauses Φ. Output: A Truth Value. function DPLL(Φ) if Φ is a consistent set of literals then return true; Read More …
Converting a digraph to an undirected graph in a reversible way
Problem Detail: I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I understand that this will come Read More …
Why can the alphabet be represented in numbers in base 256
Problem Detail: This is in context of hashing of strings. I’m not sure why a string like, CS, could be represented as CS = ‘c’*256 + ‘s’ Does anyone know about this? Asked By : John Swoon Answered By : David Richerby A Read More …
How long does the Collatz recursion run?
Problem Detail: I have the following Python code. def collatz(n): if n <= 1: return True elif (n%2==0): return collatz(n/2) else: return collatz(3*n+1) What is the running-time of this algorithm? Try: If $T(n)$ denotes the running time of the function collatz(n). Read More …
Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent?
Problem Detail: I fail to understand why cut off value would be system dependent, and not a constant. From Princeton University website Cutoff to insertion sort. As with mergesort, it pays to switch to insertion sort for tiny arrays. The optimum Read More …
When are two simulations not a bisimulation?
Problem Detail: Given a labelled transition system $(S,Lambda,to)$, where $S$ is a set of states, $Lambda$ is a set of labels, and $tosubseteq StimesLambdatimes S$ is a ternary relation. As usual, write $p stackrelalpharightarrow q$ for $(p,alpha,q)into$. The labelled transition $pstackrelalphato Read More …
Why is ‘Manhattan distance’ a better heuristic for 15 puzzle than ‘number of tiles misplaced’?
Problem Detail: Consider two heuristics $h_1$ and $h_2$ defined for the 15 puzzle problem as: $h_1(n)$ = number of misplaced tiles $h_2(n)$ = total Manhatten distance Could anyone tell why $h_2$ is a better heuristic than $h_1$? I would like to Read More …
