Problem Detail: From low OS-level function calls, to memory allocated to an application, all will primarily take a stack to perform LIFO operations. Why don’t we use queues and FIFO operations? It’s just a matter of moving pointers anyway. Asked By Read More …
Author: ignougroup
[Solved]: Calculating Binet’s formula for Fibonacci numbers with arbitrary precision
Problem Detail: Binet’s formula for the nth Fibonacci numbers is remarkable because the equation “converts” via a few arithmetic operations an irrational number $phi$ into an integer sequence. However, using finite precision arithmetic, one would always have some (small) roundoff error. Read More …
[Solved]: IDDFS explained
Problem Detail: I am trying to understand how IDDFS works by reading a wikipedia article on it. (If someone has a better literature on the subject, don’t hesitate to post). Pseudocode is as follows: IDDFS(root, goal) { depth = 0 for(i=1, 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 …
[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]: 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]: 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]: 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]: 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]: 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 …
