All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
11 views

Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}

The language given is $L = \{a^i b^j c^k\mid i+j \ge 2k\}$ for which I need to construct a simplest possible Context Free Grammar. I tried understanding but I could only go as far as making sense of $...
0
votes
0answers
8 views

Advices needed to study the deep learning book of ian goodfellow?

After studying the basics of machine learning, I want to follow the deep learning book of Ian Goodfellow. To have a better understanding of the book and make clearer the points that I could not get ...
0
votes
1answer
19 views

How can we prove that a reduction exists?

PROBLEM: I have two computational problems, A and B. We know that A $\in$ Psearch and I want to prove that A$\leq_p$B for all problems B. GOAL: It is my understanding that my goal is to prove that ...
0
votes
0answers
23 views

Confused about Turing Recognizability

If Turing Recognizability means a T.M. will either halt on input w if w is in the language, or run forever if w is not in the language. How can we know the language is Turing Recognizable if we run ...
0
votes
0answers
20 views

Can I use the term pseudo-logarithmic?

Whenever an algorithm has polynomial complexity, but exponential over the encoding of the input, it is said to be pseudo-polynomial. What about logarithmic complexity? Can I state that these ...
1
vote
0answers
20 views

Uniformly random decimal numbers

Due to finite precision of number representations, we face situations like: In: 0.1+0.1+0.1==0.3 Out: False (on my ...
0
votes
0answers
13 views

Organic Chemistry Dataset with Compound name and formula

I am trying to create an app which needs access to a dataset with organuc chemistry compound names and formulas. The ones I have found don't satisfy the requirement. Does anyone else know of any ...
0
votes
0answers
27 views

Can this special case of Set Cover problem be solved in polynomial time?

Let $U$ be the set of elements and $S$ be the subset collections. There exists a tree $T$ that each node is corresponding to an element in $U$. And for every subset $s$ in $S$, $V(T) \bigcap s $ is a ...
1
vote
0answers
9 views

Recurring computations for 2-counter machines

It is known that reachability of 2-counter machines is undecidable. As far as I know, it is semi-decidable though. Now let's focus instead on the problem of deciding if a 2-counter machine has a ...
1
vote
2answers
30 views

3SAT: Get smallest number of algorithm invocations to get a satisfiable assignment? How should it be done?

My Question is, what is meant with smallest number N. Does it mean I should try every possible constellation of the n variables and put each one of them into the formula φ and then use 3Sat on that? ...
0
votes
1answer
13 views

DPDA by empty stack

Let's say we have DPDA with acceptance by empty stack, w is accepted by this DPDA. Why can't wv be accepted? I know about the prefix property but i don't see where it's coming from. Can't we just ...
1
vote
1answer
137 views

Algorithmic Problem on Trees

Given a directed, rooted tree with $n$ vertices, the height of a vertex $v$, $h[v]$ is the number of edges on the longest path from $v$ to some reachable leaf node. Give an efficient algorithm to find ...
0
votes
0answers
19 views

How many clock cycles uses to run my code?

Assume, I want to know the number of the cycles of cpu clock that uses to run a specific code written with a specific Programming language like python or others Can i do it? i mean, do you have any ...
0
votes
1answer
47 views

I want to determine if this language is non regular-any tips?

After working through some examples of proving the non-regularity of languages I encountered this language $$ L = \{(ab)^{i}a^{j} | i \geq j, i,j \in \mathbb{N}\} $$ Where $a^{k}$ = a repeated k times....
1
vote
1answer
25 views

Is there a simplistic way of describing the proof to the undecidability of David Hilbert's 10th problem?

I recently have been reading a bunch about David Hilbert's famous 10th problem, and trying to understand its proof. I am currently in the process of reading through an explanation of the proof, given ...
1
vote
1answer
19 views

Reducing one problem to another

I know this is sort of a basic question, but I don't completely understand the following. Let $A$ and $B$ be two problems. If I take one instance $a$ of $A$ and one instance $b$ of $B$, and show the ...
1
vote
1answer
16 views

Runtime analysis with multiple parameters: case study with heaps in Huffman coding

While studying a book on algorithms, I came across a question that asked about essentially $d$-ary Huffman coding, where the codeword alphabet has $d$ symbols (the usual case has $d=2$, with symbols $...
0
votes
0answers
16 views

Is this variant of Subset Product NP-hard?

Given a set $Y$ with whole number positive divisors of $N$, is there a combination of divisors that have a product equal to $N$? Does Subset Product remain NP-hard when whole number divisors are only ...
0
votes
0answers
11 views

How many code alphabets do we need in order for a Huffman Code and a Shannon-Fano Code to be the same for the same source symbols probability

For example, If we have a source with alphabet $\{x, y, z\}$ with probabilities $\{0.5, 0.3, 0.2\}$ , What is the smallest integer $\mathbf{D}$ such that the expected length of a D-ary Shannon-Fano ...
-1
votes
1answer
39 views

Is the right quotient of a regular language respect to another regular language a regular language?

Will the language $\{w\in L_1\mid \exists v, wv\in L_2\}$ be regular if $L_1$ and $L_2$ regular languages?
-1
votes
0answers
10 views

How to maintain consistency in replica in distributed system

In a distributed system using transactions between the databases of different sites, how do we control reads and writes so that the replicas remain “consistent”? What different levels of consistency ...
1
vote
0answers
27 views

Hoeffding's inequality applicability for sample complexity

I am trying to determine some bounds for sample complexity. Suppose we have a bounded loss function $\ell$ and target function $f:\mathcal{X}\to\mathcal{Y}$. Hypothesis $h$ is learned, then the ...
1
vote
0answers
21 views

Cluster 3d points with constraints

I have some 3d point cloud I wish to cluster into some number of clusters. I have the probability of two points being in the same cluster given as some function of their relative locations, with the ...
0
votes
1answer
20 views

Getting rid of "FG" in a LTL equation

i am currently struggling with a Linear temporal logic equation: $$\phi=FG( \lnot a\lor X \lnot a )$$ For my understanding, it means that starting at a certain point in the future, proposition a can ...
0
votes
1answer
14 views

Is integer multicommodity flow problem is NP-hard?

As Wikipedia states the time complexity of Integer Linear programming(ILP) is NP-hard, so this means integer multicommodity flow problem is also NP-hard?
1
vote
3answers
712 views

How exactly is the process of showing a problem to be NP-Complete a proof by contradiction?

The steps involved in proving that a problem is NP-Complete are fairly straightforward to follow, it's the logic behind why the proof is valid that's really throwing me for a loop. Okay so an easy one:...
2
votes
1answer
28 views

Is this set covering problem NP-Hard?

Consider this variant of set covering problem. Input: a collection of sets S = {s$_1$, s$_2$, ... s$_n$} and an universal set U, in which s$_k$ $\subseteq$ U. (1<=$k$<=n) The problem is, divide ...
0
votes
1answer
23 views

chromatic number is np-hard

I'm referring to a question in this book: Algorithms by Jeff Erickson, link:http://jeffe.cs.illinois.edu/teaching/algorithms/notes/J-approx.pdf, in particular, pg.21, Q11. The author mentioned that ...
-1
votes
0answers
29 views

single machine job scheduling problem maximizing the profit

So I have a single machine job scheduling problem as detailed below. I've been using multiple greedy algorithm approaches and computing the maximum profit among them to come up with the best schedule, ...
6
votes
10answers
3k views

Real life examples of *zero* weight edges in graphs

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously. Yet, when I recently read here a question on real life example ...
-1
votes
0answers
21 views

Primal and Dual problem of SVM

The primal problem of SVM is about maximizing the Lagrangian function with respect to w while the dual problem is about maximizing the Lagrangian function with respect to α Is this statement correct?
1
vote
0answers
25 views

Proof that every vertex in the same strongly connected component of a graph $G$ happen to appear in the same DFS tree

My Professor proved that every vertex in the same strongly connected component of a graph $G$ happen to appear in the same DFS tree (which is also called tree of predecessors). He proved it by ...
3
votes
1answer
160 views

Algorithmic problem on sliding windows

Given a zero-indexed, unsorted array, $a$ of integers (can be positive, negative, or zero) of size $n$. A window of size $k~(k < n)$ is defined as a subarray $a[i...i+k]$ for every $0 \leq i \leq n ...
1
vote
0answers
47 views

Decision problem solution monte carlo

I have a rather straightforward question for this community (that I am not able to solve). Assume there is a probability of Tom having a bag of candy. If Tom has a bag, he says the truth 4/5 times and ...
-1
votes
0answers
31 views

Where are the region adjacency graph algorithms?

I am interested in the Region Adjacency Graph construction problem in the context of (labelled) digital images. I am surprised to find very few resources on the topic, with the notable exception of a ...
-2
votes
0answers
24 views

How to input an unknown (within a certain limit) number of elements into an array in C using scanf? [closed]

My intention for this code is to receive an unknown number of elements into an array (with an arbitrary hard limit, N). it doesn't output the expected result, I expected it to print the same input the ...
1
vote
0answers
15 views

Computational Hardness of the $k$-Partition Problem with identical numbers/objects?

The $k$-Partition Problem is NP hard. I want to know if some slight modification of this problem makes it polynomially solvable. Now consider the set $S=\{a_1,\ldots,a_n\}$ of IDENTICAL numbers/...
1
vote
0answers
22 views

Routing in ring network topology

I want to find 2-approximation algorithm for finding path of m messages sent from m computers to m different computers in a ring topology with n nodes. I know about clockwise embedding, which takes ...
0
votes
1answer
27 views

Binary Tree- Java - Get height of tree with a node method. Given a node class and a main method only

This is probably so simple, but I am stuck. Can anyone help me to get the height of the binary tree without being able to traverse any nodes? I actually know how to do this using the nodes themselves ...
1
vote
0answers
13 views

Meaning of pulse driven sequential logic?

I am trying to understand the meaning of this scheme, providing a sort of classification of sequential logic circuits. This taken from https://www.electronics-tutorials.ws/sequential/seq_1.html Does ...
1
vote
1answer
23 views

Transforming from neighbour representation to grid representation

Assuming I have a list L of lists. Each list in L has four entries [North, Ost, South, West] which represents the neighbours of a point i on a grid. If the entry is 0, the grid neighbour is not ...
0
votes
1answer
37 views

How to design PDA for this language?

I'm having a hard time trying to build the PDA for this language: $$L=\{a^nb^m: n,m \geq 1 \land m=4n+2\}$$ I don't know how many $a's$ should I push into the stack when reading $a$, and how many $a's$...
0
votes
1answer
65 views

Bounding this probability in this Monte Carlo algorithm

Let $P$ be a YES-NO decision problem. Let $A$ be an algorithm for deciding on it such that it is correct with probability $4/5$, in both cases (YES an NO). Design an algorithm that is correct with ...
7
votes
0answers
141 views

Shortest path in directed graphs with no more than $\log \log n $ negative edges

Given a directed graph $G=(V,E)$ with $|V|=n$ vertices and some weight function $w\colon E\to \mathbb{R}$, I also know that there are at most $\log\log n$ negative weight edges in $G$, and $G$ does ...
2
votes
0answers
24 views

Why is $O(nk)$ an upper bound for the $k$-gossip problem?

I am studying the $k$-gossip problem on dynamic graphs against an adaptive adversary. Essentially, we are given a set of tokens $\mathcal{T}$ which are distributed amongst the nodes such that each ...
5
votes
0answers
52 views

Complexity of still life extentions in Game of Life

The game of life is one of the most famous cellular automata in 2D. It has a variety of objects, some of them are moving like gliders, some have an oscillating behavior and others do not change at all,...
1
vote
0answers
28 views

How the data is transferred from main memory to hard disk?

I understand that data is transferred from the main memory to the CPU and vise versa using the data bus. But, I am unable to understand, how the data is being transferred from the main memory to the ...
0
votes
0answers
18 views

The length of the formula in Monadic second-order logic

The Courcelle's theorem as following: Obviously, we need the length of the $\varphi$~(that is $||\varphi||$)~in Theorem. However, how to caculate the length of $\varphi$? For example, $$\begin{...
2
votes
1answer
70 views

Request for Good Encyclopedic works of computer science

I attempt to find a few general encyclopedic works on computer science such that looking up relevant terminologies is easily available ready to hand. I'm not familiar with the whole picture of ...
0
votes
0answers
19 views

Undecidability of a set of Turing Machines

Considering the following set, I have to say if it is undecidable, decidable or semidecidable: $$S_1 = \{y | \forall n \text{ the Turing Machine } M_y \text{ does not accept any string of length } n\}$...

15 30 50 per page
1
2 3 4 5
856