0
votes
0answers
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 ...
-1
votes
0answers
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 ...
2
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
-3
votes
0answers
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 ...
0
votes
2answers
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$
3
votes
0answers
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 ...
0
votes
0answers
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, ...
5
votes
1answer
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$ ...
5
votes
0answers
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 ...
0
votes
1answer
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 ...
-1
votes
1answer
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.
-1
votes
0answers
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?
-2
votes
1answer
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?
2
votes
1answer
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 ?
1
vote
1answer
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.
1
vote
1answer
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 ...
-1
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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] < ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
-2
votes
0answers
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: ...
0
votes
0answers
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 ...
3
votes
1answer
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|)$ ...
6
votes
1answer
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. ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
5
votes
0answers
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 ...
3
votes
1answer
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 ...
-1
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
2answers
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 ...
1
vote
0answers
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. ...
2
votes
2answers
73 views

Spatial Locality in Cache - Which addresses are loaded?

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 ...
0
votes
0answers
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?
0
votes
0answers
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 ...
2
votes
2answers
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 ...
-5
votes
0answers
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. ...
8
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
3
votes
0answers
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 ...
0
votes
1answer
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