Problem Detail: Wikipedia says: fun factorial n = if n = 0 then 1 else n * factorial (n-1) A Standard ML compiler is required to infer the static type int -> int of this function without user-supplied type annotations. I.e., Read More …
Blog
[Solved]: Convergence of Simulated Annealing Based Algorithms
Problem Detail: I designed a simulated annealing-based optimization algorithm. My simulation shows that it converge fast. I am looking for some sort of proof to show that simulation annealing-based algorithm converge fast (based on satisfying some properties) to global/local optimal point Read More …
[Solved]: Design a DFA which accepts words with sorted letters
Problem Detail: I have just started learning Theory of Computation and have come across a question which I am not able to solve. The question is as follows: Design a DFA that reads a word (character strings) and decides whether the Read More …
[Solved]: How to analyze the lower bound of the horse racing problem using adversary argument?
Problem Detail: Consider the following problem: Give an algorithm to find the $1^{st}, 2^{nd}, 3^{th}$ fastest horses from 25 horses. In each round, at most 5 horses can race and you can get the exact position of these horses. Analyze the Read More …
[Solved]: Selling blocks of time slots
Problem Detail: Given $n$ time slots that $k$ people want to buy. Person $i$ has a value $h(i,j)geq 0$ for each time slot $j$. Each person can only buy one consecutive block of time slots, which could be empty. Is there Read More …
[Solved]: Computing binomial coefficients and factorials modulo a composite number
Problem Detail: Does anyone know of a fast algorithm to compute factorials and/or binomial coefficients in general or modulo a composite number in particular (for composite moduli I am interested in the case where the factorization is not necessarily known) I Read More …
[Solved]: Correctness of splitting an undirected tree into a forest of trees with even number of children
Problem Detail: Given an undirected tree (i.e. a tree without any designated root) of even number of nodes. The task is to remove as many edges from the tree as possible to obtain a forest of trees, where each such tree Read More …
[Solved]: What is the bitwise xor of an interval?
Problem Detail: Let $oplus$ be bitwise xor. Let $k,a,b$ be non-negative integers. $[a..b]={xmid aleq x, xleq b}$, it is called a integer interval. What is a fast algorithm to find ${ koplus xmid xin [a..b]}$ as a union of set of Read More …
[Solved]: Finding a pair of non-overlapping bit vectors
Problem Detail: I give you a list of $n$ bitvectors of width $k$. Your goal is to return two bitvectors from the list that have no 1s in common, or else to report that no such pair exists. For example, if Read More …
[Solved]: Construct a digraph given its in-degree and out-degree distribution
Problem Detail: Could anyone help me with this algorithmic problem: Given the in and out degrees of a set of vertices, is it possible to determine if there exist a valid graph respecting this constraint? The graph can allow self loops Read More …
