Problem Detail: How can I sort a list of 5 integers such that in the worst case it takes 7 compares? I don’t care about how many other operations are performed. I don’t know anything particular about the integers. I’ve tried Read More …
Author: ignougroup
[Solved]: Possible to connect arbitrary number of dots without intersections?
Problem Detail: A (now closed) question on SO made me think about the following problem: Given an arbirtary number of points (2D), draw a path that consists of straight lines between points, visits each point exactly once and does not intersect Read More …
[Solved]: Linear-time algorithm to find an odd-length cycle in a directed graph
Problem Detail: Problem: Give a linear-time algorithm to find an odd-length (directed) cycle in a directed graph. (Exercise 3.21 of Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.) The related [email protected] asks for the existence of an odd-length directed Read More …
[Solved]: Undecidability of telling if a program returns true or false
Problem Detail: Consider the problem of taking an input Turing machine and determining if the final cell is a $0$ or $1$ after computation halts. On cases where it writes something else or does not halt, you are allowed to give Read More …
[Solved]: Generating inputs for random-testing graph algorithms?
Problem Detail: When testing algorithms, a common approach is random testing: generate a significant number of inputs according to some distribution (usually uniform), run the algorithm on them and verify correctness. Modern testing frameworks can generate inputs automatically given the algorithms Read More …
[Solved]: Does the DFS algorithm differentiate between an ancestor and a parent while computing back edges?
Problem Detail: Below is the general code for DFS with logic for marking back edges and tree edges. My doubt is that back edges from a vertex go back and point to an ancestor and those which point to the parent Read More …
[Solved]: Why does the state remain unchanged in the small-step operational semantics of a while loop?
Problem Detail: Usually I see that in the structural operational semantics representation for the while loop, the program state don’t change: $(while > B > do >S, sigma) rightarrow (if >B > then >S; (while > B > do >S) > Read More …
[Solved]: How does ‘deforestation’ remove ‘trees’ from a program?
Problem Detail: I think understand how deforestation consumes and produces a list at the same time (from a fold and an unfold function — see this good answer on CodeReview here), but when I compared that with the wikipedia entry on Read More …
[Solved]: What is Simultaneous Multithreading
Problem Detail: I come from an electronics background. I know that there are three types of implementations of multithreading (see Computer Architecture: A Quantitative Approach, 5th Edition): Fine-grain multithreading issues instructions for different threads after every cycle. Coarse-grain multithreading only switches Read More …
[Solved]: Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?
Problem Detail: On wikipedia, there is a proof for the cycle property of the Minimum Spanning Tree as follows: Cycle Property: For any cycle C in the graph, if the weight of an edge e of C is larger than the Read More …
