0
votes
0answers
1 views

Pumping Lemma for L={a^(2k) b^n b^k | k>=0, n>=0}

$L=\{a^{2k}b^nb^k\mid k\geq0, n\geq0\}$ over alphabet $\{a,b\}$ How do I prove that L is not regular using Pumping Lemma? All the examples I've come across had same exponents all around, and I'm a ...
0
votes
0answers
2 views

Optimizing Permutation Algorithm

I'm looking at Permutations Algorithm, the complexity of this algorithm is pretty high O(N*N!). The algorithm is based on this observations. GeneratePermutations("ABC")= [ABC; ACB; BAC ; BCA ; CBA ...
0
votes
0answers
2 views

High Level Explanation of the Pumping Lemma

I have a problem that I cannot figure out regarding using the pumping lemma to prove that a function is not regular. I don't understand how I go about proving through contradiction that the language ...
-1
votes
0answers
11 views

Can we tweak merge sort to perform better than quick sort? [on hold]

Generally We know Merge sort has complexity O(nlogn) and quicksort has worst case complexity of O(n^2) which rarely happens if we choose good pivot. I would like to know if there is some way to ...
0
votes
0answers
8 views

Prove L is regular of the language L^R [duplicate]

for L^R = {w^R|w E L} prove L is regular, then so is L^R.
0
votes
0answers
12 views

Draw out TM where 1<=n<=|w| the nth character from the left is equal to the nth character from right

We need to write TM for strings over {a,b,c} for some n, 1<=n<=|w| the nth character from the left is equal to the nth character from right. Can someone help me understand the meaning and how ...
-1
votes
0answers
12 views

Construction of a nondeterministic pushdown automation

I have a solution for the pushdown automaton that accepts the language $$\{x\#y \mid x,y\in \{0,1\}^* \text{ and } x\neq y\}\,,$$ which looks like this: I am trying to work from this in order to ...
-1
votes
0answers
6 views

k means for 2d data

I am implementing k-means for 2d data and stuck at the part where we assign centroids and later each instance to the cluster. I wanted to know the next strategy that I should go ahead with ie. how do ...
0
votes
0answers
17 views

Number of all possible sequences

If I have a list of numbers, say $L = \langle5, 10, 15, 20, 25\rangle$, how could I make a program so that I get the number of sequences for which $a_i -a_{i+1}<10$, where $a_i$ is the $i^{th}$ ...
0
votes
1answer
15 views

How to prove that $\{0^n 1^{5n} \mid n \ge 10000 \}$ is not a regular language?

I proved that $$ \{ 0^n 1^{5n} \mid n \geq 0 \}$$ is not a regular language using Pumping Lemma by following way. Solve by contradiction that $ L = \{0^n 1^{5n} \mid n \geq 0 \}$ is regular ...
-1
votes
1answer
20 views

Relative Importance in Graph Theory

I am working on an algorithm that ranks a set of nodes in a graph with respect to how relative this node is to other predefined nodes (I call them query nodes). The way how the algorithm works is ...
1
vote
1answer
7 views

A problem regarding Extended Euclidean Algorithm

Alex has some (say, n) marbles (small glass balls) and he has going to buy some boxes to store them. The boxes are of two types: Type 1: each box costs c1 Taka and can hold exactly n1 marbles Type ...
1
vote
1answer
6 views

Seletion of pair of friend and Random team

I'm given 2 numbers n and m.I have to make n with m numbers(only taking their sum).For example,if n=6,m=3,6 is formed with 3 numbers in the following way. a)1+1+4=6 b)2+2+2=6 c)1+2+3=6 For every ...
1
vote
1answer
13 views

Hardness and approximation of a problem with a parameter

Let $H$ be a decision problem, where we are given an integer $k$ and some object, say a graph or a formula. We know that $H$ is NP-complete for $k \geq c$, where $c$ is some constant like 3 ($H$ could ...
3
votes
0answers
11 views

Detecting coplanarity by given erroneous pairwise distances

This is the question I asked four months ago and took very satisfactory answers. However, I tackle a new problem now. Here, I summarize the original problem: We have points in 3D space. We do not ...
3
votes
2answers
200 views

complexity of determining whether a language given by context free grammar is empty

I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word ...
-1
votes
0answers
21 views

Amortized cost of increment counter problem

Consider the increment-counter problem, where now the counter is represented in base 10, the initial count is 0, and where the cost of an increment is the number of digits that change. (a) Show by ...
0
votes
0answers
6 views

limitation on the depth of directory tree [on hold]

"write a program that creates a directory and then changes to that directory, in a loop. Make certain that the length of the absolute pathname of the leaf of this directory is greater than your ...
0
votes
0answers
9 views

Translating object oriented programs to their procedural equivalents

I'm new to the field of program transformation. I'm looking for resources on the techniques and methods one would use to translate object oriented code to its procedural equivalent. In particular, I ...
0
votes
0answers
15 views

Difference between parallel and concurrent buffering?

In double buffering there are two terms Concurrent buffering. Parallel buffering. What is the difference between them, answer with example will be appreciated.
1
vote
1answer
19 views

Find k maximum numbers from a heap of size n in O(klog(k)) time

I have a binary heap with $n$ elements. I want to get the $k$ largest elements in this heap, in $O(k \log k)$ time. How do I do it? (Calling deletemax $k$ times yields a $O(k \log n)$ complexity. ...
-1
votes
0answers
10 views

Grammar LL parser

I have this grammar below and trying to figure out if can be parsed using the LL parser? If not, please explain. ...
1
vote
1answer
22 views

Is $K' = \{ w \in \{0,1\}^* | M_w$ Halts on $w \}$, where $M_w$ is the TM whose encoding is $w$, equivalent to the halting problem?

My professor presented the halting problem as $K' = \{ w \in \{0, 1\}^* | M_w$ Halts on $w \}$, where $M_w$ is the TM whose encoding is $w$ (i.e. $w = \langle M \rangle$), and said it was equivalent ...
0
votes
0answers
18 views

Booth's Algorithm Multiplication

When multiplying signed integers by Booth's algorithm, does the multiplicand always have to be negative? What happens if multiplier and multiplicand are both negative? Does the algorithm still work? ...
-2
votes
1answer
45 views

prove 3x+1 problem is undecidable [on hold]

Let f(x) = 3x + 1 if x is odd, or f(x) = x/2 if x is even. if you start with an integer x and iterate f, you obtain a sequence x, f(x), f(f(x)), …, stop if you ever hit 1. For example, if x =17, ...
0
votes
1answer
17 views

What is the purpose of $\epsilon$ transition?

$A = \{a^i b^j c^k\mid i = j\text{ or } j = k; i, j, k \ge 0\}$. In its push down automaton should not there be the red colored transition instead of the black colored one?
0
votes
1answer
28 views

Algorithm Introduction [on hold]

From what I have found out so far, Introduction to Algorithms by Cormen is the algorithm equivalent of the GOF Design Patterns book. However, can anyone recommend a more introductory book please?
-3
votes
0answers
14 views

Roucairal and Carvalho's Mutual Exclusion algorithm [on hold]

How to show that Roucairal and Carvalho's Mutual Exclusion algorithm is not fair. i.e. requests are not satisfied in the order that they were made.
-3
votes
0answers
15 views

Ricart and Agarwal's Mutual Exclusion algorithm [on hold]

How to show that in Ricart and Agarawal's mutual exclusion algorithm, requests are satisfied in the order of their timestamps?
-1
votes
1answer
11 views

List the edges (vertex pairs) of a minimum spanning tree for this graph in the order they would be chosen by Prim's algorithm

List the edges (vertex pairs) of a minimum spanning tree for this graph in the order they would be chosen by Prim's algorithm Please help me to understand and complete this. I would very much ...
-2
votes
0answers
14 views

How to computer the minimum operations required to perform chained matrix multiplication [on hold]

A1 x A2 x A3 x A4 Here A1 is 4x 5 , A2 is 5 x 10, A3 is 10 X 7 and A4 is 7 x 3 So far this is what i have for the matrix m [][] ) Please help me to understand and complete this problem.
2
votes
1answer
6 views

What's the difference between Adaptive Control and Hierarchical Reinforcement Learning?

After watching Travis DeWolf presentation on scaling neural computation, I'm a bit confused about the difference between Reinforcement Learning (whether hierarchical or not) and Adaptive Control. They ...
3
votes
0answers
9 views

What's the difference between adaptive control and a kalman filter?

From my basic understanding of Adaptive Control, I understand that it uses the error and the velocity of the error to approximate the error in the solution space of a problem, thus allowing for ...
0
votes
0answers
16 views

All sets of interval coverage given a fixed interval size [on hold]

Given an interval $I_n = [0,n]$ and a positive integer $m$ where $n,m \in \mathbb{N}$ and $m < n$, return all covering sets $S_m$ of $I_n$. A covering set $S_m$ of $I_n$ is a set of sub-intervals, ...
0
votes
0answers
9 views

Weighted undirected graphs, complex Laplacian, complex eigenvalues & spectral clusering

I am rather puzzled and confused, I have been trying to get a clear understanding of how would spectral clustering work for an undirected weighted graph, I have used the normalized Laplacian, but I ...
4
votes
0answers
53 views

Fixed size set to contain the maximum number of given sets

I asked this question in SO here I have about 1000 sets of size <=5 containing numbers 1 to 100. {1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ... ...
1
vote
0answers
23 views

Is “duplicate” in RPN enough for replacing variable binding in term expressions?

I try to work out some consequences of storing (or "communicating"/"transmitting") a rational number by a term expression using the following operators: $0$, $\mathsf{inc}$, $\mathsf{add}$, ...
0
votes
1answer
33 views

What are system clock and CPU clock; and what are their functions?

While reading a book, I came across a paragraph given below: In order to synchronize all of a computer’s operations, a system clock—a small quartz crystal located on the motherboard—is used. ...
2
votes
1answer
31 views

Solving a dynamic programming problem?

Alex writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down? My one friend said to me that this problem can be ...
0
votes
0answers
6 views

How to properly solve this Hidden Markov Model problem?

I got a an exercise problem which should be seen as a HMM scenario and argument some statements. However I'm quite confused about how to properly solve and argument my solutions. Problem tells: ...
4
votes
1answer
32 views

Determining Number of States in a Turing Machine

I am looking at an example Turing machine in my textbook, Automata and Computability by Dexter C. Kozen, and I'm confused as to how they determine the number of states this particular machine has. ...
0
votes
1answer
26 views

What if traversal order of two of pre-order, in-order and post-order is same?

Supposing a tree T has the identical: Pre-order traversal and in-order traversal Pre-order traversal and post-order traversal In-order traversal and post-order traversal How does T look like? ...
0
votes
1answer
6 views

Estimating the $\beta$th moment of a uniform random variable

Let $n$ be a positive integer, $\beta > 1$, and let $X$ be a random variable uniformly distributed over $\{0, \ldots , n -1\}$. Show that $\mathbb{E}[X^\beta] \leq n^\beta / (\beta + 1)$. I don't ...
0
votes
0answers
21 views

Proof of the base case of Big Theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. a and c are positive constants. $T(n)=a$, if $n=2$ $T(n)=2T(n/2)+cn$ if $n>2$ Use induction to prove that ...
-2
votes
0answers
19 views

Is master theorem applicable in this case? [on hold]

T(n) = T(n/2) I do not think it applies because there no n term there is no k such that n^k = 0 here is the definition i am using: http://gyazo.com/b9548f57b36372df1e5715d38f578403
0
votes
0answers
12 views

Can git be used to share files between multiple computers not on same lan? [on hold]

a friend and I have been working on a project and need a way to share files between computers easily. While there are other alternatives such as dropbox I'd prefer to use something else. Would git be ...
-1
votes
0answers
18 views

primitive recursive( course of values recursion)

If $f(n)$ is any function, we write $f(0)=1,f(n)=[f(0),f(1),...f(n-1)]$ if $n\ne 0$ and let $f(n)=g(n,f(n))$ for all $n$. Show that if $g$ is recursive so is $f$. I don't want anybody solve this ...
0
votes
1answer
43 views

Unique boolean functions with one input

I have an assignment where I have to write a truth table for all possible unique Boolean functions with one input , but I do not understand exactly what I have to do. By ...
3
votes
3answers
472 views

Rigorous Proof of Insertion Sort

Currently I self study CLRS book (Outside of any course, so I got no access to an instructor) And I am stuck proving Insertion Sort, The proof in CLRS book is not so formal. Here's the algorithm: ...
3
votes
1answer
45 views

What if $NP\subseteq BPP$?

I'm new to complexity and came upon the following exercise which I'm unable to solve. Prove that if $NP\subseteq BPP$ then $\Sigma_2^p=\Pi_4 ^p$.

15 30 50 per page