Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computer-science]

All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

0
votes
0answers
8 views

boolean logic minimization

Two level boolean logic minimization(AND, OR, NOT) for big number of variables,(say n) is time-consuming. I want to minimize an n variable sum of Product form boolean expression efficiently where n ...
0
votes
0answers
20 views

Graph-cut and pairwise MRF

I try to use graph-cut method but I got some trouble with it. I want to segment an image into foreground and background. For each pixel $x$, I got the probability that it belongs to the background $p(...
0
votes
0answers
9 views

How to show that the Nearest Neighbour Algorithm given an instance of the metric travelling salesman problem has a logarithmic approximation ratio?

I would like to understand why the Nearest Neighbour Algorithm has a logarithmic approximation ratio when given an instance of the metric travelling salesman problem. I have come across the paper of ...
2
votes
1answer
30 views

regular language equality prove by induction

let $L\subseteq\{0,1\}^*$ be declared by the following conditions: a. $0, 01\in L$. b. if $w_1,w_2\in L$ so $w_1\cdot w_2\in L$. c. if $w\cdot 0\in L$ so $w \in L$. prove that $L=\{w| w=\epsilon\: ...
1
vote
1answer
35 views

Can you have indirect memory addressing in primitive recursive functions?

Douglas Hofstadter describes a programming language called BlooP in his book, "Gödel, Escher, Bach: An Eternal Golden Braid". I'm unclear whether cell variables require constant indices or whether ...
0
votes
2answers
27 views

What does this relation represents ?

so i have a hard time understanding what would this relation looks like, we aren't given any precise function so it's hard to know what this would look like. We have to establish the relation and then ...
1
vote
1answer
23 views

How to create sets of nodes on a colored graph while cutting as few edges as possible

I'm a programmer not a mathematician so my jargon is terrible and I apologize. My problem: I have a graph (relatively sparse) and I've colored all its nodes. There are no edges between nodes of ...
-1
votes
1answer
24 views

Approximation bounds on the Nearest Neighbour Algorithm for the TSP.

I am currently studying about the Nearest Neighbour Algorithm applied to the TSP, and I want to check if there are any performance bounds on it. I have came across the following paper on the ...
2
votes
0answers
15 views

Is there a context-free but non regular language, which still meets the requirements of the regular pumping lemma?

Is there a context-free but non regular language, which still meets the requirements of the regular pumping lemma? Regular Pumping Lemma: $\exists n\in \mathbb{N}:\forall w \in L:{\mid w \mid} \geq ...
0
votes
1answer
29 views

building a DFA from equivalence classes of $R_L$(tricky)

i've encoutered an interesting question from an old exam with no solution and i was wondering: how do you build a dfa(deterministic finite automata) from given equivalence classes? this is the ...
1
vote
1answer
33 views

Activity Selection Algorithm

I have an activity selection problem where I am given a number of rides at an amusement park and their start and finish times. My goal is to create a program which maximize the amount of time spent on ...
0
votes
1answer
32 views

How to prove that height of a rooted tree is an invariant under isomorphism?

Intuitively, if we're restricted to mapping the root of $T_1$ to the root of $T_2$ that makes the structure of the two trees rigid. And since under isomorphism the number of vertices are equal, height ...
0
votes
0answers
21 views

finding equivalence classes of $R_L$ in automata(Nerode)

i am having trouble understanding this concept. would really appreciate your corrections so i could learn and improve. 1)$L=\left\{w\:\in \Sigma^* |\:w\:begins\:and\:ends\:with\:aa\right\}$ 2)$L=\...
0
votes
0answers
7 views

Prove that a CFG expresses all the strings expressed by the language L

How can I prove that the CFG: S → A | B A → ɛ | 0A0 | B B → ɛ | 1B0 Expresses all the strings from $L = \{0^m1^n0^{m+n} \mid m, n \geqslant 0\}$? (I'm sure this is simple but for some reason I ...
1
vote
0answers
11 views

Verification of the Cocke-Younger-Kasami (CYK) Algorithm

I've got to test if the string "abba" belongs to the following grammar in CNF: S → CD | CF | CG | CH A → DC | DE B → AC | BC | BE | DC | DE | a C → a D → b E → AC F → DB G → DA H → DI ...
0
votes
1answer
47 views

Cardinality bounds on set algebra

Assume two sets $A$ and $B$. Consider the following set of inequalities: $\max \left(\lvert A \rvert, \lvert B\rvert \right) \le \lvert A \cup B\rvert \le \lvert A \rvert + \lvert B \rvert $ $\lvert ...
0
votes
1answer
53 views

which of the following languages over $\Sigma \{0,1,\$\}$ are regular?

i saw this nice exercise in some old summary and i was wondering if i got it correctly. basically i have to decide whether a language is regular or not and give a short explanation. (languages over $\...
0
votes
1answer
32 views

proving that $a^6 \in L$ (tricky) (pumping lemma)

i've encountered a quite tricky question that i don't understand, and would appreciate your help with: it is said that by the pumping lemma, for a certain L there exists(guarenteed) n=2. also known ...
0
votes
1answer
36 views

Binary Tree mathematical equation for number of internal nodes [closed]

I was wondering how does this equation: $$\frac n2 + \frac n4 + \frac n8 + \dots + 1$$ go to: $$1 + 2 + 4 + \dots + \frac n2$$ and then to: $$\sum_{i=0}^{h-1} 2^i,\; \text{where $h$ is the height ...
1
vote
1answer
32 views

How can I prove given language is not regular?

My first post here, so glad I found this great place. Hoping I could improve and learn a lot from you and contribute in the future if I can. I have a problem with the following scenario: Given $\...
4
votes
0answers
156 views

How many Nerode equivalence classes does the language $x\neq y$ have?

I have a language $L_k$ over the alphabet $\Sigma=\{0,1,\#\}$ defined as follows: \begin{equation} L_k=\{x\#y|x\in\{0,1\}^k,y\in \{0,1\}^*\wedge x\neq y\} \end{equation} I would like to find all the ...
0
votes
1answer
50 views

Given a regular language L, prove or disprove L' is regular

Given $NFA$ $N$ , $L(N)$ regular language and two words $w1$,$w2$ $\in$ $\sum^*$ such that $w1$ $\neq$ $w2$. I have to prove or disprove that $L'=$ {$z\in \sum^*|\exists$ $w1,w2$ :$w1z$ $\in$ $L(N)$ ...
0
votes
0answers
17 views

Generalizing $n \cdot m = O(n^2) \iff m = O(n)$ to any two-variable function

I came across the following statement in my Computer Science high-school textbook (I translated it to English). There was some for loop that runs $m$ times nested inside a for loop that runs $n$ ...
0
votes
1answer
32 views

Infimum and Supremum (of sets) - Formal Concept Analysis

I am taking a course of Introduction to Formal Concept Analysis and I have an uncertainty about the definition of supremum (least comum superconcept) and infimum (greatest comum subconcept) of formal ...
0
votes
0answers
32 views

What is a formal statement of the Dining Philosopher's Problem?

(The dining philosopher's problem is described here.) I'm having trouble understanding whether or not the philosopher's act simultaneously. Do they all take one action simultaneously, then take their ...
0
votes
0answers
14 views

(Worst and average case) Arithmetic and time complexity of a quadratic programming problem by interior point method

My understanding of complexity measures are at basic level. So, please excuse me for asking basic question, if it sounds like. I am trying to understand the arithmetic and time complexity of a ...
0
votes
0answers
28 views

Questions about database representaiton

Recently I am reading a paper, and here the author gives the way of database representation. I feel confused. Could someone give me an example of the so-called universe and histograms? My thought is ...
4
votes
2answers
38 views

Help understand beta reduction example

I am currently reading a text book on distributed computing systems that includes a short introduction to $\lambda$-calculus. There is an example of evaluating the sequence $(((if \space \space true) ...
1
vote
1answer
23 views

Growth of Functions proof

How would you prove $n! ∈ Ω(n^{n/2})$ ? This example was given to us in school, but I don't know how to prove it. What I'am trying to prove: \begin{align} n! ∈ Ω(n^{n/2}) ⇔ ∃ c ∈ ℝ^+,\ ∃ n_0 ∈ ℕ^+,\ ∀...
3
votes
1answer
44 views

Given an n by n matrix of 0s and 1s, find the maximum number of 1s you can remove if you can only remove 1s with another 1 in the same row or column

This is a computer science interview question I heard from a friend and we can't seem to figure it out. Basically, given a square matrix of 0s and 1s, you can remove any 1 one at a time, but only if ...
1
vote
1answer
43 views

PDA: Symbol in first half

How do I construct a PDA where: $L = \{w \in \{0, 1\} ∗ : |w| \text{ is even and } w \text{ contains at least one 1-Symbol in the first Half}\}$ To me it seems impossible to know when I reached the ...
0
votes
0answers
26 views

Proving program correctness

I want to prove the correctness of iterative method for square root of "a" as given below: s,m := 0, a while m > ε/2 if (s+m)^2 <= a s := s + m m := m /2 I have ...
1
vote
0answers
32 views

Big Oh Notation: Proving that $n! \in \Omega(7^n)$

Problem I've got the following statement which I'm looking to prove: $\log_2(n!) \in \mathcal{O}(n \cdot \log_3(n))$ The question is: how to do it? Steps taken so far My approach so far was to ...
0
votes
0answers
31 views

How to convert binary floating point to decimal scientific notation?

Let me be clear, by this I don't just mean convert 1.01 * 2 ^ 010 to "5". I'm talking about the exponent as well. This is the true challenge. The mantissa is fairly easy to convert, just find the ...
0
votes
0answers
11 views

A relation of Kolomogrov complexity

Given a positive strictly monotonically increasing infinite sequence $n_1, n_2, \dots$ with Kolmogorov complexity $$K(n_i)\geq\lceil\log_2 n_i\rceil/2\,.$$ If $q_i$ is the greatest prime number that ...
0
votes
0answers
19 views

Matrix of a graph and computational complexity

Given a simple undirected graph with no self-loops, $G = (V,E)$, where $V = {1,2,...,n}$, an $n × n$ matrix $A$ is said to be the adjacency matrix of $G$ if $A_{i,j}$ is $1$ if $(i, j) ∈ E$ and $0$ ...
1
vote
1answer
32 views

'$L$ almost' is regular

Given a regular language $L$, I have to prove that '$L$ almost' is regular where '$L$ almost' is all the words which differ from the words of $L$ by one char. for example, if $L = \{aab,aaa\}$, so $...
3
votes
1answer
45 views

Sort an array given the number of inversions

Given an array $A$ with $n$ integers in it, one way of measuring the distance of the array from a sorted array is by counting inversions. A pair of indices $i,j ∈ {0,...,n−1}$ is called an inversion ...
1
vote
2answers
105 views

Using the recursion theorem to implement the Sieve of Eratosthenes.

Update: I provided an answer here that shows how to define a mathematical function using the recursion theorem. This function can be reconfigured to compute the prime-counting function, $\pi(x)$. ...
0
votes
0answers
11 views

Probability - Similarity Rate in the random Signal

I have a random signal (vector) that consists of random variables varying between -2 and 2. I want to know how many similar patterns do I have in this random signal. In order to achieve this, I select ...
2
votes
2answers
80 views

Evaluate this alpha substitution $[(zx)/x] \, \lambda z.xyz$

I am having difficulty with the following problem: Calculate the result of this substitution, renaming the bound variables as needed, so that substitution is defined $[(zx)/x] \, \lambda z.xyz$ ...
0
votes
1answer
47 views

what is the similar triangles argument?

I’m reading a textbook on 3D graphics math. It’s describing how to model a pinhole camera, using a film plane at z = 1. However, the book then says this: Given a point p in the scene with eye ...
1
vote
1answer
58 views

What is the probability that the first bin is empty? [closed]

Suppose that n balls are tossed, one at a time, into n bins such that each ball is equally likely to fall into any bin and that the tosses are independent. What is the probability that the first bin ...
0
votes
0answers
17 views

Designing a PDA to accept $wa^{n_a(w)}$ where $w$ is over $\{a,b\}$ and does not contain the string $bbb$.

I'm very new to this topic! I see that the PDA must push $a$ on the stack until after the last $b$ when it must pop $a$'s after that. I know that I'm looking to make sure the $a$ stack is empty at the ...
1
vote
1answer
41 views

Let $L_1$ be the language over alphabet $\{0, 1\}$ defined by $L_1 = \{x : \#_{01}(x) \bmod 3 = 0\}$. Give a regular expression that denotes $L_1$

Let $L_1$ be the language over alphabet $\{0, 1\}$ defined by $L_1 = \{x : \#_{01}(x) \bmod 3 = 0\}$. Give a regular expression that denotes $L_1$, and justify its correctness attempt Need 010101 ...
0
votes
0answers
10 views

Why transpose the weight vector in Perceptron Convergence Theorem

We have a training set D with a bunch of input vectors x and desired output of y. We are aiming to make a perceptron that can separate the input vectors x in accordance with their desired output y. ...
1
vote
2answers
77 views

How shall I understand what the GNU utilities “comm” and “diff” do in terms of ordered sets?

I am looking for some help to understand two GNU utility programs in terms of ordered sets. If you happen to know their usages, you might be able to understand what I am asking here. In mathematics, ...
2
votes
1answer
17 views

Analyzing a special case of the Big O notation for N->R and g(n) =/= 0

It's my first post here so be gentle ^^ My problem formulates like this: Given the functions $f,g:\mathbb {N} \to \mathbb {R_0^+}$ with the property $g(n) \not = 0 \ \ \ \forall n\in \mathbb {N}$, ...
5
votes
1answer
35 views

Beta reduction for expression

I'm given the following where: TRUE = λxy.x FALSE = λxy.y IF = λbtf. b t f OR = λxy. IF x TRUE y and I'm trying to evaluate: ...
0
votes
1answer
19 views

Drawing a dfsa where L is a set of strings that contains at most 4 zeros

For each of the following languages over alphabet $Σ = \{0, 1\}$, construct a DFSA that accepts it and a regular expression that denotes it. Prove that your automata and regular expressions are ...