1
vote
0answers
4 views

Specialized Algorithm for Set-Cover with $k=3$

I know that the Set-cover problem with $n$ elements and a universe of size $N$ is NP complete. Also, the problem is Fixed-parameter tractable regarding the number of sets $k$ that should cover the ...
-1
votes
0answers
2 views

What would be the most efficient alghorithm to use in the case of a “expanding pixel” on a 2d field

You have a 2d field of size X, every point on that field can be treated as a pixel so it has a color, at the start all pixels are white. You then select a point on the field with a different color ...
-1
votes
0answers
12 views

Is $\frac{n}{\text{log}n}$ sublinear in n?

Is $\frac{n}{\text{log}n}$ $=\text{o}(n)$ ?
0
votes
0answers
10 views

C++ Different output on different compiler versions [on hold]

When executing this program on c++14 (clang4.0) I get the expected result but other versions I get the wrong result why so? ...
0
votes
0answers
17 views

Algorithm to determine how fuel efficiently a driver is driving

I need to define an algorithm for how fuel efficiently a driver is driving, but I'm a total novice in the area of computational models so I'm not sure if I'm doing this right. I have formulated the ...
-1
votes
0answers
13 views

Is there any audio series focused on CS papers?

I know of 2 Minute Papers and Papers We Love, but is there anything similar in audio format? PS: Is there a better place to ask this question?
0
votes
1answer
15 views

Modify max value multiple times of a list

I have two lists say A and B, each consisting of n positive integers. I make a list C such that each element of C i.e., Ci=Ai*Bi for each element Ai in A and Bi in B. Now I have to update the value of ...
-2
votes
0answers
8 views

Object Oriented Analysis and Design [on hold]

I have to develop a simple e-commerce application , with Only 3 classes User , Shopping cart and Product. I am not quite sure about the relationship between these classes the requirement says ...
0
votes
0answers
5 views

What is the meaning of “linear projections onto rows of some matrix”?

I was reading through a research paper on compressive particle filtering for target tracking, and I came across the following: Let $z \in d_{z}$ denote a vectorized image with $d_{z}$ pixels. Assume ...
0
votes
0answers
10 views

Solving range updates and point queries for a special case

Initially we have an array of size N, all set to 0. We have operations of two kinds: $Increment$ the range $[L, R]$ by 1. $Get$ the current value at $idx$. If these queries were interspersed with ...
0
votes
1answer
19 views

Floating point number fractions excercise

During my preparation for an exam, I've come across an exercise that was focused on precision calculation with floating point numbers. It goes like this: Consider the expression : $$\frac{1}{1-x}-\...
1
vote
0answers
15 views

Is there a model of computation based on discrete event dynamic systems?

I asked a question here about discrete event dynamic systems. They are systems whose state evolution depends on asynchronous events. It can be combined with flow to produce a hybrid system. There ...
0
votes
0answers
9 views

calculate the throughput during the simulated time interval?

I am using a network simulator called ns and I got this network and its corresponding graph: and I am supposed to calculate the throughput during the simulated time interval, I was told that sequence ...
0
votes
1answer
22 views

Which Peterson’s Solution is right?

I have seen two different Peterson’s Solution to mutual exclusion, one is from Modern Operating Systems: ...
3
votes
0answers
15 views

Eke a better compression ratio out of Huffman coding by mixing 1-grams and 2-grams

Huffman coding is already doing a great job at compressing ascii bytes for data with a distribution like the following ...
0
votes
1answer
16 views

PDA, L = {a, b} Accepts the same number of groups of “aa” and “bb”

PDA that accepts by final state, the language in the alphabet {a,b} where the number of groups 'aa' equals the number of groups 'bb'. To accept: aababababb aaababbb bbbaaaabbb Rejected aaabbabb ...
1
vote
3answers
36 views

Is there a reason to NOT wrap preprocessor macros in parens?

I'm writing a design document for a macro expansion language that is specifically intended for arithmetic operations on integers. I've already determined that not wrapping macros with parens can lead ...
1
vote
1answer
19 views

Prove: Every decidable set is Turing reducible to the empty set

Question- Prove: Every decidable set is Turing reducible to the empty set. Can anyone help me with this please? All reductions tutorials I've seen use practical examples of reduction such as sipser'...
0
votes
0answers
30 views

Convert right linear grammar to left

Are there any (for example in literature) rules for converting right linear grammar to left? I found the algorithm from right to left, but not the opposite. Thanks for help
1
vote
2answers
46 views

Solving T(n)=T(n−1)+2T(n−2) using substitution

I am trying to solve the following Recurrence relation using substitution method and I am stuck almost half way. I know the answer is 2^n but I can't reach it. At first, my question is: Who decicdes ...
0
votes
0answers
15 views

How to prove the following: Every set is Turing reducible to itself

Question: Prove the following: Every set is Turing reducible to itself. If anyone can provide a solution that would be great, I've just been introduced to computation theory so be as descriptive as ...
1
vote
3answers
55 views

Determining number of elements divisible by at least one prime of set

I have an array ($|A|\leq 10^6$) of numbers ($A_i\leq10^6$) and a set of prime numbers. I have to find the count of the elements in the array that are divisible by at least one of the numbers in the ...
0
votes
0answers
10 views

How to convert a binary variable and a function to it into matrix in R

How to convert a binary variable and a function to it into matrix in R? x ~ a binary variable, where Prob(x=1) = 0.2 (20% are 1s) w ~ U[0,1] + d*x, where d = 3 (uniformly distributed between 0 and 1 ...
1
vote
0answers
23 views

Minimizing cost of shortest paths to a group of vertices by adding minimal edges to an unconnected vertex

Let $G=(V,E)$ be directed graph, where the weights of the edges are non-negative. The graph might have cycles, but without parallel edges. Consider a $T \subset V$, and $u \notin V$. I'm trying to ...
-1
votes
0answers
22 views

How to convert if else to map a array?

I have a variable Int a to set variable String b. ...
1
vote
1answer
30 views

When is the concatenation of a language $L$ with $\Sigma^*$ regular?

I've been looking at questions about the regular concatenation of two languages; one question said that the concatenation of $\{0^n1^n|n\geq 0\}$ and $\Sigma^*$ was regular (over the alphabet $\Sigma =...
0
votes
1answer
16 views

Convert grammar to Greibach form

The grammar is $S \rightarrow AA|a$$A \rightarrow SA|ab$The actual question is to find an NPDA accepting the language generated by this grammar but for that i firstly need to convert it into Greibach ...
0
votes
1answer
16 views

Is the complement of a semidecidable (r.e.) language always a semidecidable (r.e.) language?

Is the complement of every semi-decidable language a semi-decidable language?
0
votes
1answer
11 views

Loading a word from byte-addressable cache

I have asked a similar question at stack-overflow, but then I found this question here, and figured it should go here instead.. So, my question is pretty much the same as the one in the question I ...
0
votes
1answer
22 views

All the possible inputs for a given AVL tree

Given an AVL tree,what are the possible inputs so that the same given tree is formed(please dont mention brute force technique)?
1
vote
1answer
27 views

Decidability of $E_{TM}$ and $A_{TM}$ for “erasing” Turing machines

Why is the $A_{ETM}$ for a variant of a Turing machine (an erasing Turing machine), where changing a tape symbol to a nonblank symbol is prohibited, decidable? Why does the following diagonalization ...
1
vote
1answer
35 views

Algorithm to organize a tournament where the team componentes change each round

So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...
1
vote
1answer
24 views

Is this an $NP$-complete problem: Product-2-Partition

I want to prove the NP-hardness of my problem P in scheduling. I was trying with Partition, 3-Partition and Subset product, But neither was successful. Now, I can reduce a problem, say PRODUCT-2-...
1
vote
1answer
16 views

Big-Oh vs Theta in recurrence tree method

I am solving this problem from here. The given relation is $$T(n) = 2 T(\frac{n}{2}) + n^2, \, T(1) = 1$$ The solution via recurrence tree method is given as: The zeroth level has a single node ...
4
votes
3answers
60 views

Sum of unique elements in all sub-arrays of an array

Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$. Subarrays: ...
0
votes
1answer
23 views

Robustness of non-context-free proof against trivial manipulation

First, we state here a theorem that is well-known in computability theory: $L=\{xx\mid x\in\Sigma^*\}\notin CFL$ for every fixed $|\Sigma|\geq2$ And, the standard proof is using pumping lemma. At ...
1
vote
2answers
35 views

DFA for words with $a$s not a multiple of 3 and at least one $c$

Consider this language: $$L = \{w \in \{a,c\}^* \mid 3\nmid\#a(w)\land\#c(w)>0\}$$. Here is an automaton for the first part of language, but I do not know how to devise and attach the second part ...
0
votes
0answers
7 views

Alternative technologies/theories for a “Git for Structured Graph Databases”

Along the lines of detect differences between tree structures, I'm wondering if there are any general techniques or tools (e.g. the techniques behind the tools) that can essentially do what Git does ...
2
votes
0answers
8 views

Distributed Computing: Persistent Data Structures in Functional Programming versus Wait-Free Data Structures

Persistent (aka immutable) data structures in functional programming sidestep issues of shared memory mutual exclusion, and thus also issues such as data races that arise and which may be difficult to ...
1
vote
1answer
21 views

Lamport logical clock: why event occurs in a process with smaller pid is treated earlier?

In lamport's paper1, he define global local timestamp, which is composed of process id and local lamport timestamp. This timestamp is used to order all the events in a distributed system. The rule ...
2
votes
0answers
21 views

Weighted Sorting Algorithm

Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation. Is there any ...
1
vote
1answer
25 views

Lamport logical clock: what does partial mean in the concept of `Partial ordering`?

In lamport's paper[1], he define two concept The partial ordering and The totally ordering. What does partial mean in ...
-3
votes
0answers
29 views

Write a C program which has a function COM that take two strings (character array) A,B [on hold]

Write a C program which has a function COM that take two strings (character array) A,B and output "A is smaller" or "B is smaller" if string A is smaller than string B. We say A is smaller than B if ...
0
votes
0answers
8 views

Where can I find technical historic information about the facebook? [on hold]

I mean, in which language/s it was programmed in the beginning, and which program components it contained, and how it changed over the years from a technical point of view and the reason for these ...
-1
votes
0answers
13 views
1
vote
1answer
24 views

Robot swarm, Maximum area coverage

I have a swarm ofN robots to place on a plane area. Each robot would control a sub part of the area (navigating in it). What algorithm could I use to deploy my ...
-2
votes
0answers
26 views

Computer acts weird after closing and updating [on hold]

so I have a bit longer question. So I have bought a new computer a week ago and it runs super smoothly when it turns on and in general I am happy with it. After 2-3 days i had a required update where ...
0
votes
0answers
51 views

Markov's Inequality and Hashing

Let H be a universal family of hash functions from U = {0, 1, . . . , u − 1} into a table of size m. Let S ⊆ U be a set of m elements we wish to hash. Prove that with probability at least 3/4, no list ...
0
votes
0answers
41 views

Expected Number of Collision Pairs

I have been attempting to solve this problem for hours, but cannot seem to comprehend how to come to the solution. Let $H$ be a universal family of hash functions from $U = \{0,1,\ldots, u − 1\}$ ...
1
vote
1answer
45 views

Asymptotic behavior of $n\sqrt n + n \log n$ & $\log_{100} n$ [duplicate]

I have the following two functions $f(n) = n\sqrt n + n \log n$ $\log_{100} n$ And I need to classify them into the followings: $O(n)$, and/or $O(n^2)$, and/or $O(n^3)$, and/or $O(n^{1.5})$, and/or ...

15 30 50 per page