Problem Detail: I am stuck and having a hard time with this question. I want to construct a CFG for the language $$L = {{a^lb^mc^n | l,min N, n=|l-m|}}$$ I know that the language consists of strings where: 1. number of Read More …
Author: ignougroup
[Solved]: How to fool the plot inspection heuristic?
Problem Detail: Over here, Dave Clarke proposed that in order to compare asymptotic growth you should plot the functions at hand. As a theoretically inclined computer scientist, I call(ed) this vodoo as a plot is never proof. On second thought, I Read More …
[Solved]: Min-max selection sort
Problem Detail: Is there already modified version of selection sort that works like this pseudocode: a // the array, index starts at 1 (not zero-based) n = len(a) for x in 1 to n big = x small = x last Read More …
[Solved]: Why separate lexing and parsing?
Problem Detail: It’s possible to parse a document using a single pass from a state machine. What is the benefit of having two passes, ie. having a lexer to convert text to tokens, and having a parser to test production rules Read More …
[Solved]: circle packing algorithm used by Percolator
Problem Detail: I was admiring this rendition of the Mona Lisa from quasimondo‘s Flickr account. He says: Combining circle packing with data visualization. The pie charts show the distribution of the dominant colors under the circle area. The circle packing technique Read More …
[Solved]: Data Structure For Closest Pair Problem
Problem Detail: Suppose I have a list of distinct integers. I’m looking for a data structure that will support the operations search, insert, delete and closest_pair in $O(log n)$ time. I know that a sorted array supports search, insert and delete Read More …
[Solved]: Minimize the maximum component of a sum of vectors
Problem Detail: I’d like to learn something about this optimization problem: For given non-negative whole numbers $a_{i,j,k}$, find a function $f$ minimizing the expression $$max_k sum_i a_{i,f(i),k}$$ An example using a different formulation might make it clearer: You’re given a set Read More …
[Solved]: Difference between 1* + 0* and (1 + 0)*
Problem Detail: I know that (1 + 0)* is the set of all bit strings; but isn’t 1* + 0* the same thing? Asked By : O.A. Answered By : Yuval Filmus The set $1^*+0^*$ is composed of two parts: $1^*$ and $0^*$. Read More …
[Solved]: Polynomial time reducibility
Problem Detail: $L_1$ and $L_2$ are two languages defined on the alphabet $sum$. $L_1$ is reducible to $L_2$ in polynomial time. Which of the following cannot be true? $L_1 in P$ and $L_2$ is finite $L_1 in NP$ and $L_2 Read More …
[Solved]: What is meant by Category theory doesn’t yet know how to deal with higher-order functions?
Problem Detail: In reading Uday Reddy’s answer to What is the relation between functors in SML and Category theory? Uday states Category theory doesn’t yet know how to deal with higher-order functions. Some day, it will. As I thought Category theory Read More …
