# All Questions

7 views

### examples of strings that is not in the set [on hold]

I'm kind of struggling with finding a string that is not in this set {w: for some u ∈ Σ*, www = uu} where Σ = {a,b} from what I understand, the set of Σ* is, {E, a, b,aa, ab, ba, bb, aaa, ...} if w ...
6 views

### What is GeForce GT755m SLI good for? Bitcoin minnig? rendering? [on hold]

I bought the Y510P gt755m SLI notebook PC. Now I see that working with a single graphics card or both, I don't see much difference in a games' frame rate, witch means that having to GPU for gaming is ...
11 views

### Equivalences between a calculus and an automaton model [on hold]

Lambda calculus has the same strength as a Turing machine. I somehow see this as functional programming (LC) vs imperative programming; but as I don't trust my intuition here, I want to explore this ...
21 views

### Prove that the language is not regular without using Pumping Lemma

I am practising problems on Regular Languages and I came across this question: Prove that the language $$\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\}$$ is not regular. (Using the pumping lemma for this ...
12 views

### change all bit of a integer [on hold]

lets say I have 5(101) how can I change it to?: 2(010) If I use ~ I get -6 Is there an easy way using bitwise? I don't ...
12 views

### Assuming finite optimal cost of a specific LP, find an optimal solution directly

Minimize $\sum^n_{i=1} c_i x_i$ subject to $\sum^n_{i=1} a_i x_i = b$ (a single constraint), $x_i \ge 0$. Derive a simple test for feasibility of this problem Assuming the optimal cost is ...
13 views

### analyzing moving pseudorandom sieve algorithm

the following is a rough simpification or "toy" version/ abstraction/ model (but still quite nontrivial) for/ inspired by a famous open math problem (which for now will remain nameless & may be ...
34 views

### Creating a grammar from the language

L = { a^n b^2n a^(n+2) : n>=1 } So I'm trying to construct the grammar and I'm getting stuck.Some example strings would be these (spaced out to help demonstrate the patterns): a bb aaa aa bbbb aaaa ...
18 views

### Use structural induction to prove the following binary tree [on hold]

Recursive def for Set X (there are two): (1)a single node is in X and (2) if x1 and x2 are in X, then the bigger tree with root r connected to the roots of x1 and x2 is in X use struc induction to ...
59 views

### How to show whether $n2^n = 2^{O(n)}$?

show whether $n2^n = 2^{O(n)}$ is true or not. In my opinion, it's false because O(n) can be n and thus the equality will be wrong, because $n2^n$ grows much faster than $2^n$
11 views

### Simplify closed-path points without intruding into the inside of the path

I want to: Simplify a set of points that outlines a closed opaque image on a transparent background. The simplified set of points should not intrude into the closed opaque image. I use a ...
17 views

### upper bound and lower bound? [on hold]

Given the recurrence relation $$a_n = 2 \cdot 3^{n−1} − \frac{1}{2} − (−1)^{n/2}.$$ Without solving it, would a good guess for an upper bound be $O(3^n)$? Considering that is the largest term, ...
51 views

### Proving optimality of a dynamic programming algorithm

We have a string $s$ containing $n \leq 100$ bits. The move we can make on it is erasing from $s$ some substring $x$, but only if $x$ is directly preceded by $x^R$, where $x^R$ means string $x$ ...
35 views

### Exponential analogue of NC?

Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors. I want to know about the exponential analogue, which would cover problems that ...
46 views

### Computation is effectively computable in theory and in practice

My big question is the following: What is the meaning of a computation being "effectively computable" (EC) in theory and in practice? In trying to understand these concepts further, I have a couple ...
20 views

### c compiler source code for compiler construction [on hold]

Could anyone tell me from where could I get the c compiler source code.In particular the lexical analyzer for c.I searched the web but no links show how a compiler is defined.
14 views

### What is Software Transactional Memory and when is it used? [on hold]

I came across the term 'Software Transactional Memory' today and was wondering what it is, and when it is typically used?
35 views

### What is a forwarding pointer?

I heard this terminology used today and haven't come across it before, could someone please explain? Are there any other terms/names that describe this concept?
124 views

### Are there more partially recursive functions than and recursive functions?

Is the cardinality of the set of partially recursive functions greater than the cardinality of the set of recursive functions ?
53 views

### Prove any binary tree with $n$ nodes has at least $1+\log_2 n$ levels

Prove that any binary tree with $n$ nodes has at least $1+\log_2 n$ levels. I tried setting $n=8$ and plugging in $8\geq\log_2 8 = 8\geq 3$. But I'm not sure how I can prove this by induction.
40 views

### Determining on whether topology is a tree or a hypercube

Assume that the nodes know that the topology G is either a hypercube or a tree. Assuming a unique initiator, design an algorithm to discover the topology. In other words, you would like a node to ...
9 views

### What level of the computer hierarchy does the processor fall under? [on hold]

So I'm going through my homework for Computer Organization, and I'm not entirely sure what level that a computer processor (the example in the homework is the Qualcomm Snapdragon Processor) falls ...
20 views

### How does the Vertex Cover algorithm by Chen et al find its tuples?

I'm still fighting with the aforementioned paper "Improved upper bounds for vertex cover" by Chen, Kanj, Xia (PDF kindly provided by Yuval Filmus). My current problem is that it's specified that the ...
31 views

### Please Explain The Flow of This Algorithm and How does it work?(Knuth Topological Sorting) [on hold]

Given a relation ~ on {1....n} with the property that x~y implies x < y, this algorithm generates all permutations a[1]....a[n] and their inverses a'[1].....a'[n] with the property that a'[j] < ...
23 views

### How to prove strict space lower bounds using crossing sequences in Turing machines?

I understand the notion of crossing sequences when talking about time, however how are they used to actually prove strict lower bounds for some decision/search problems? For example, suppose that you ...
13 views

### Is the “data path cycle” the same thing of the “fetch-decode-execute cycle”?

I am reading the book Structured Computer Organization (5th edition) by Tanenbaum and at a certain point, in the second chapter, he talks about ...
34 views

### Maximum value a variable can hold without documentation [on hold]

Suppose we work with some particular programming language (like C++) on some particular computer. Furthermore, we want to know which values are minimum and maximum for some particular numeric data ...
11 views

### Breaking an octal number, converting to binary and re-converting to octal

What are the octal values of the four 8-bit bytes in the 32-bit number with octal representation 12345670123? Here's my solution. It would be helpful if you could check my working. Octal number: ...
11 views

### Relationship between #of cores and Dynamic Power

The book I'm currently reading specifies that Dynamic Power = (1/2) * Capacitive Load * (V^2) * frequency However, that is assuming it's a single-core system. I ...
27 views

### Finding vertices for which there either exists a path to all other vertices or other vertices have a path to them

Or in other words, find all $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ or $w \rightarrow v$. This is for a directed acyclic graph. I need to find an $O(|E| + |V|)$ ...
52 views

### Etymology of time and space “complexity”

The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. ...
40 views

### Is there a difference between the Bulk Synchronous Parallel Computing model and the Turing Machine

The Turing model of computing is widely accepted, as a Tape, Head, State register, and a finite state Table to manage transitions. The Bulk Synchronous Parallel Machine model has for its part ...
34 views

### NFA state complexity for the complement of EPAL restricted to a fixed length

I've been having trouble proving the next statement: Let $L_n=\{ww, |w|=n\}$ (the set of equal-length palindromes (EPAL) restricted to length $2n$). Prove that $L^c_n$ can be accepted by an NFA ...
36 views

### K -> 2 tape reduction for nondeterministic Turing machines

How to I show that any language in NTIME(T(n)) can be accepted by a non-deterministic 2-tape O(T(n)) time-bounded Turing machine, with modifiable input tape? I've seen the k to 2 tape reduction for ...
41 views

### Is There a Complete Problem for the Class of Turing Decidable Problems?

Languages such as $\text{HALT}_{TM}$ are $\textsf{RE-complete}$ under many-one reductions. It is trivial to see that $\text{co-RE}$ has complete problems, too. S. Schmitz [1] considers some classes ...
18 views

### Converting truth table to algebraic normal form

Is there any efficient algorithm to convert a given truth table of a Boolean function to its equivalent algebraic normal form (ANF)? I have seen that Sage has one implementation (official ...
29 views

### Data fetching in Virtual System [on hold]

I just finished reading Memory Management and Virtual Memory from book and few internet resources. I am trying to understand the whole flow of Virtual Address to Physical Address translation and how ...
50 views

### Is an algorithm in pseudocode a reasonable way to establish complexity?

We define the language $$L = \{a^nb^n : n\geq0 \}$$ and we want to prove the following $$L = \mathrm{DSPACE}(\log n)\,.$$ So we have to prove that by using $\log n$ space on the work tape of ...
69 views

### Algorithms which are both deterministic and non-deterministic

I'm just starting my second year in computer science and one of my classes briefly touched upon deterministic vs. non-deterministic algorithms. This got me thinking - is there any use for algorithms ...
27 views

### Algorithm to generate graph of specific known form

I am trying to generate a graph (the structure with edges and nodes), that as a structure like an Order-7 triangular tiling of specified diameter around a central node. ...
73 views

I don't quite understand the concept of spatial locality in cacheing. I understand that on a cache miss, not only the specific address we want is loaded into the cache, but also "nearby addresses" are ...
10 views

### Number of instructions in instruction set of popular processors [on hold]

Where can I get information about number of instructions in instruction set.of popular processors?
69 views

### Computer Architecture: DFS and DVFS problem

The question: You have a large inventory of Intel processors that run at 3 GHz and 1 Volt, and consume 100 W (of which, 20 W is leakage) when running a given CPU-bound application. This application ...
66 views

### BNF and Simultaneous Parsing

Let's say we have the following grammar expr1 ::= ... // Actual definition doesn't matter expr2 ::= ... // expr3 ;:= ... // foo ::= expr1 | expr2 | expr3 ...
18 views

### Proving the correctness of Fibonacci by induction when using arrays [on hold]

f(n): A = [0, 1] for i in range(2,n+1): # from 2 to n A.append( A[i-1]+L[i-2] ) // invariant: last element of A is A[i] return A[i] prove the invariant. ...
86 views

### Are regex crosswords NP-hard?

I was fooling around the other day on this website: http://regexcrossword.com/ and it got me wondering what the best way to solve it was. Can you solve the following problem in polynomial time or is ...
18 views

### Are there other unsupervised techniques than clustering to partition data into classes [on hold]

I have a dataset of $N$ elements; each are $n$-dimensional vectors. I want to partition them into different classes. Classification requires training data. Is clustering the only unsupervised ...
56 views

### Why do Θ-bounds not survive taking differences?

$f_1$, $f_2$, $g_1$, and $g_2$ are functions such that: $$f_1 = \Theta(f_2)$$ $$g_1 = \Theta(g_2)$$ I was able to prove that: $$\frac{f_1}{g_1} = \Theta\biggl(\frac{f_2}{g_2}\biggr)$$ But I can't ...
19 views

### Term for index-like data structures

There's a class of data structures where you preprocess some other data structure in order to answer queries about it more efficiently. That includes trivial things like sorting/hashing, less trivial ...
15 views

### Understanding when to count key comparisons

I understand that for something like Linear search, this would be the key comparison: if(itemToFind == a[i]) return i; If I put this method into another ...

15 30 50 per page