# All Questions

1 views

### What are the present research areas in computer science that have good future prospects?

I am a student of Computer Science and Technology presently in my second year. I want to go for higher studies and thereafter research. So I want to know the trending fields in Computer Science that ...
3 views

### Accessing variable in tree c++

I am looking at this code online and am not sure how to access a particular variable stored inside the tree. For example, the offset.x is being pushed into the vector children, so how would I access ...
2 views

### Origin of tFAW (Four Activation Window) in DRAM timing constraint

In DRAM timing constraints, tFAW means length of a rolling window that allows up to four row activations in same Rank. This constraint is mainly due to power budget of each rank. However, I am ...
9 views

### When is counting coins NP-complete?

having a bit of an issue with this question and deciding which of these situations requires dynamic programming and which are NP-complete: All three (except the last one) ask how much goes to person ...
7 views

### How to identify statistically distinct features of different sets?

I have two non-overlapping sets of items, with feature counts for each. What standard algorithms can I use to extract the most statistically distinct features of each set? For example: Items served ...
7 views

### Order of storage of pointers for a linked list of length n

I have a linked list in which I have kept the elements in order (increasing/decreasing). I want to be able to perform a binary search on this linked list. For this I am keeping pointers to the middle ...
9 views

### Write a Special Code on C# [on hold]

I want to a Monitoring software for my user in one company. how i can wrote a program such a way non user be able to stop it in client? i.e, without any technique couldent stop my program or service? ...
16 views

### Efficient algorithm for regular expression matching

To find out all the occurrences of texts matching a regular expression(R), e.g. 1*01* against a large chunk of text(T), what can the most efficient algorithm be? Had R been a fixed pattern, ...
13 views

### Operating Systems Qualifying Exam Visual Study Aids

I have read the Operating System Concepts book, watched a lot of videos on YouTube, practiced with past qualifying exam questions and several exams from other CS departments around the world. ...
17 views

### Natural language processing complexity

Which natural language processing problems are NP-Complete or NP-Hard? I've searched the [natural-lang-processing] and [complexity-theory] tags (and related complexity tags), but have not turned up ...
19 views

### Operating System Paging concept

I am quoting a paragraph from the book "Operating System Principles" by Galvin. Usually, each page-table entry is 4 bytes long, but that size can vary as well. A 32-bit entry can point to one of ...
17 views

### Co NP problem correponding to SAT

I've been reading lately about SAT problem, NP and co-NP. Many sources say that the SAT problem is co NP, though, I can't find a co-NP problem equivalent to SAT. Does anyone have any idea about ...
638 views

### What is the Big O of T(n)?

I have a homework that I should find the formula and the order of $T(n)$ given by $$T(1) = 1 \qquad\qquad T(n) = \frac{T(n-1)}{T(n-1) + 1}\,.$$ I've established that $T(n) = \frac{1}{n}$ but now ...
23 views

### Need help to derive the Complexity!

Please help me regarding this one! What will be the communication and computation complexity of this code?? ...
59 views

### Why do we need “Bloom Filters” if we can use hash tables?

A Bloom filter is a probabilistic data structure designed to tell, rapidly and memory-efficiently, whether an element is in the set or no. If we can use hash tables where we have O(1) in best time, ...
19 views

### Finding approximately collinear points

my issue comes from image processing. The image below is for a better understanding of the problem. I have to detect three dots (shown in black, marked with red arrows). The other points I get from my ...
26 views

### Converting DFA to regular expression

I have the following DFA. (Yellow stated are accepting states.) I want to eliminate states step by step to find the regular expression of it. In my steps, I think there is a bug because I do not know ...
30 views

### The meaning of $*$ in regular expressions

I'm designing a Turing machine that decides a language denoted by a regular expression. Let's say this expression is $a^*bbc^*$. Does this machine accept the string $bb$ since $a^*$ and $c^*$ can have ...
32 views

### How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? (where n is a power of 3) I was told it takes: $$2(n-2) + 1 = 2n-3$$ However, I can't seem to figure out ...
33 views

### Algorithms on Fibonacci Numbers

I want to know if there exists algorithms that: Finds if number is Fibonacci number (not using golden mean) in $O(1)$. If we use golden mean, will it be logarithmic or constant, and why? Finds ...
31 views

### how to prove a language is decidable

Hopefully this is not a duplicate How do I prove a Language L={a,b,c} is decidable or not I read somewhere that if a turing machine accepts a language and halts on every input string then the ...
17 views

### Lamport Timestamps: When to Update Counters

In the timepiece (excuse the pun) that is Time, Clocks and the Ordering of Events, Lamport describes the logical clock algorithm as the following: Each process $Pi$ increments $Ci$ between any two ...
39 views

### Dynamic scoping in each evaluation direction

Given the following [arbitrary language, although I think this is ALGOL] program: ...
167 views

### Undecidability in the context of modern programming languages

Imagine a program, executed by an interpreter to be a Turing Machine. Consider this code: x = read_input print x Does undecidability mean that there may possibly ...
13 views

### Solving a Uva problem

I want to solved the problem in the link : http://uva.onlinejudge.org/external/100/10090.html Someone Solved this in the following way. but I can't understand how he fixed up the value of t. My ...
16 views

### Can every recursively enumerable language be defined with regular expression?

Can every recursively enumerable language be defined with regular expression? I came across this question, when studying for my test: Prove that for any finite language $L$, there is a Turing machine ...
29 views

### Is this problem decidable? (computation of $M_1$ longer than $M_2$ on every input)

Is this problem decidable? Given two representations of Turing machines $R(M_1), R(M_2)$, is the length of the computation of $M_1$ longer than the length of the computation of $M_2$ on every input? ...
16 views

### What does $C$-complete problem membership in different class imply?

I am currently studying for an exam and I came over a question I do not fully understand. Could you please clarify? Question: What does it imply if a $C$-complete problem is in a class $D$ with ...
145 views

### How to proof that a language is not recursively enumerable

How does one prove that some arbitrary language $L$ is not recursively enumerable. I know I can proof that language $L$ is recursively enumerable by constructing a Turing machine $M$ that accepts all ...
14 views

### Domains in Evolutionary Algorithms where solution is a set of individuals

Can someone help me find domains in field of Evolutionary Algorithms where desired solution is a set of individuals(perhaps even whole population) and not single best solution. For example i want to ...
28 views

### Understanding the flaw in a proof attempt of the Communication Complexity of Equality

I'm new to communication theory and I've been wondering where the following simple argument fails: Equality Problem We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob ...
46 views

### When problem A reduces to problem B, which problem is more complex?

When discussing complexity classes, when we say that problem $A$ reduces to problem $B$, are we saying that problem $A$ is at least as complex as problem $B$, or the other way around?
60 views

### k-center algorithm in one-dimensional space

I'm aware of the general k-center approximation algorithm, but my professor (this is a question from a CS class) says that in a one-dimensional space, the problem can be solved (optimal solution ...
46 views

### How CPU know which process generated an interrupt?

When a computer OS supports multi-program, it needs to have a scheduling algorithm to handle which process will be run by the cpu. If a process is in state 'blocked' waiting for IO, the scheduling ...
41 views

### Pumping Lemma for $L=\{a^{2k} b^n b^k \mid k\ge0, n\ge0\}$

$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 ...
35 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 ...
50 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 language is not regular. I don't understand how I go about proving through contradiction that the language ...
30 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 ...
11 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.
23 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 ...
19 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 ...
10 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 ...
30 views

### Number of all possible sequences [on hold]

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}$ ...
29 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 ...
38 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 ...
12 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 ...
17 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 ...
16 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 ...