0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-2
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
-1
votes
0answers
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? ...
0
votes
0answers
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, ...
0
votes
0answers
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. ...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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 ...
6
votes
1answer
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 ...
0
votes
1answer
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?? ...
4
votes
1answer
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, ...
1
vote
1answer
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 ...
-2
votes
1answer
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 ...
-3
votes
1answer
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 ...
2
votes
1answer
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 ...
-2
votes
1answer
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
0answers
39 views

Dynamic scoping in each evaluation direction

Given the following [arbitrary language, although I think this is ALGOL] program: ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
-2
votes
1answer
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 ...
2
votes
1answer
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? ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
3
votes
3answers
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?
0
votes
1answer
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
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.
-2
votes
0answers
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
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}$ ...
0
votes
1answer
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 ...
-1
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
3
votes
0answers
13 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
227 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 ...

15 30 50 per page