# All Questions

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 ...
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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}$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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. ...
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. ...
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 ...
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? ...
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, ...
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?
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?
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.
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?
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 ...
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.
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 ...
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 ...
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, ...
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 ...
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} ... ...
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}$, ...
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. ...
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 ...
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: ...
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. ...
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? ...
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 ...
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 ...
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
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 ...
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 ...
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 ...
### 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$.