Problem Detail: Here’s a conjecture for regular expressions: For regular expression $R$, let the length $|R|$ be the number of symbols in it, ignoring parentheses and operators. E.g. $|0 cup 1| = |(0 cup 1)^*| = 2$ Conjecture: If $|R| > Read More …
Author: ignougroup
[Solved]: What’s harder: Shuffling a sorted deck or sorting a shuffled one?
Problem Detail: You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits (a Read More …
[Solved]: Why does backtracking work the way it does?
Problem Detail: I just recently started learning in a CS context (as opposed to a programming context) about simple recursive functions, along with the combinatorial applications, and techniques such as Backtracking and Divide et Impera. The example problem that I chose Read More …
[Solved]: Turing-recognizable languages closed under star operation
Problem Detail: I’m tasked with demonstrating that the class of Turing-recognizable languages is closed under the operation of star, but I’m confused about how this is true. For example, I have a TM to recognize a language A = { a2n: Read More …
[Solved]: Draw a graph of DFA for a regular language
Problem Detail: I’m trying to draw a DFA graph for the regular language where every chain: * consists of symbols from the set {1,a,b}. * starts with the subchain ‘1a’. * includes at least one subchain ‘aa’. Output chains: $1aa, 1abaa, Read More …
[Solved]: Linearizability and Serializability in context of Software Transactional Memory
Problem Detail: I’ve been trying to grasp serializability and linearizability in the context of software transactional memory. However, I think both notions can be applied to transactional memory in general. At this point, the following is my understanding of both subjects. Read More …
[Solved]: What is the difference between Abstract Data Types and objects?
Problem Detail: An answer on Programmers.SE characterizes an essay by Cook (Objects are not ADTs) as saying Objects behave like a characteristic function over the values of a type, rather than as an algebra. Objects use procedural abstraction rather than type Read More …
[Solved]: What is the worst case running time for an algorithm that combines insertionsort and mergesort?
Problem Detail: Suppose that we have an algorithm “combination” that uses insertionsort for $n < 100$ and mergesort for $n geq 100$. Is the worst case running time of “combination” then $n^2$ or $nlog n$? I was thinking that it’s simply Read More …
[Solved]: Sandwiching Languages
Problem Detail: I am studying for my algorithms final and came across the following problem: Find three languages $L_1 subset L_2 subset L_3$ over the same alphabet such that $L_2 in P$ and $L_1,L_3$ are undecidable. I am having trouble coming Read More …
[Solved]: Minimising height of a 2-3-4 tree
Problem Detail: I’m wondering how a set of keys could be assigned to nodes in a 2-3-4 tree in order to minimize the height of the tree? Does the sequence of insertion matter with 2-3-4 trees? Asked By : Jack Answered By Read More …
