All mathematical questions about Computer Science, including Theoretical Computer Science, Formal Methods, Verification, Logic in Artificial Intelligence, and Numerical Analysis
0
votes
0answers
26 views
Proving that a certain operation preserves regularity of languages.
Given a language $L$. Define $G(L) = \{ w \in L : ww^R \in L\}$, where $R$ is the string reversal. Why is the following proof that $G$ preserves regularity wrong?
Given a finite state automata $(M, ...
1
vote
2answers
86 views
Finite automaton that recognizes the empty language $\emptyset$
Since the language $L = \emptyset$ is regular, there must be a finite automaton that recognizes it. However, I'm not exactly sure how one would be constructed. I feel like the answer is trivial. ...
4
votes
2answers
118 views
Push down automata problem
Informally describe the Nondeterministic PDA that generates:
$$\{x\#y\ \mid x,y\in\{a,b\}^{*}\text{and}\space x\ne y\}$$
My initial plan was to use nondeterminism to go through each character before ...
3
votes
1answer
46 views
Context free language problem
I'm trying to find an unambiguous context free language for the ambiguous language:
$$S\rightarrow AB$$
$$A\rightarrow Ba| b$$
$$B \rightarrow aA|b$$
I understand the language makes up of strings ...
0
votes
0answers
46 views
Is the choose function polynomial?
I have this problem which is described as follows:
Input:
You are given a multi-set M (a set that can contain duplicates), and two numbers P and T.
$ M = {(x_1,y_1), (x_2,y_2), ..., ...
0
votes
0answers
6 views
Optimal bisection width for a multi-dimensional mesh
I am learning about multi-dimensional meshes.
In the material I use, the statement is that a d-dimensional mesh consisting of n elements can have a bisection width of \omega$(n).
I do not understand ...
5
votes
1answer
124 views
Mathematical way of determining whether a number is an integer
I'm developing a computer program, and I've run into a mathematical problem. This isn't specific to any programming language, so it isn't really appropriate to ask on stackoverflow. Is there any way ...
0
votes
0answers
34 views
Deriving the fundamental equation relationship
I'm having a hard time understanding how a few equations are being derived. So the fundamental equation is an equation that relates corresponding points in stereo images. Anyway, that's the basic ...
5
votes
4answers
195 views
Is the set of non finitely describable real numbers closed under addition and squaring?
Is the set of non finitely describable real numbers closed under addition and squaring? If so, can someone give a proof? Thanks.
6
votes
2answers
168 views
Simplifying Catalan number recurrence relation
While solving a problem, I reduced it in the form of the following recurrence relation.
$ C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1} $
However ...
1
vote
2answers
48 views
Confusion related to P and NP problems
I have this confusion related to P and NP problems. Why is P a subset of NP? I didn't get it. P problems can be solved in polynomial time. However, NP problems cannot but only verify if a solution is ...
1
vote
1answer
58 views
Minimum number of moves to convert a list of any integers into a permutation
Given a list of integers of size n, how to find the minimum number of moves to convert it to a Permutation?
In one move, we are allowed to decrease or increase any element of the list by one.
For ...
0
votes
4answers
62 views
What algorithms are used to determine the difference of two squares?
I'm taking a discrete math class this semester. The professor said that by the end of the semester he wants us to have an understanding of RSA encryption. One thing that we have gone over in class is ...
1
vote
1answer
73 views
NP-Complete Problem
Consider the following NP problem called A: its input is a
graph G and a number k > 1. Its witness, if there is one, is a pair $S;T$ of sets of
points in $G$ such that S is an independent set of size ...
3
votes
1answer
125 views
to check the minimal self-centered property of graphs
While working out on a problem, I found that cycles $C_n$ are minimally self-centered graphs, as if we remove any edge then it is paths $P_n$ and $P_n$ are not self-centered graphs.
My question is ...
2
votes
2answers
69 views
Weird series of numbers - any logic in it?
I have the following table where the first column is an index, the second column has all the powers of 2 raised to i.
I can't understand what does the third column represent. It should be something ...
3
votes
2answers
89 views
What exactly is a FLOP?
I know that is a "FLoating-point Operation" but,what exactly mean this!? Can anyone make me a mathematical example of a FLOP?
For example, is $\sqrt{2}$ a FLOP?
2
votes
1answer
30 views
to check the self-centered property of a given graph.
Can a graph be self-centered if it contains a vertex of degree one. The simplest counter example that came to my mind is Path.
But how to prove the statement if we consider any graph with a vertex of ...
0
votes
1answer
74 views
The following Post Correspondence Problem unsolvable?
I have been trying to play around with the following Post Correspondence Problem for about one hour now with no success, which leads me to believing the following problem is unsolvable.
Is the ...
0
votes
0answers
51 views
circuits, Fredkin gates
Let's assume we have a circuit consisting of four Fredkin gates
that is able to simulate a Toffoil gate. It uses five ancilla bits and produces five garbage
bits, g1, . . . , g5. How to find the ...
2
votes
2answers
26 views
Get A⊕(B+1) from A⊕B
I have numbers A,B,C.D.
(⊕ is XOR)
C = A⊕B
D = A⊕(B+1)
Is there any way to get D from C, when I do not know A and B? How?
Thanks for help!
5
votes
2answers
47 views
Find the most vertical line in a point set in $O(n \log n)$ time
Input: a set of $n$ points in general position in $\mathbb{R}^2$.
Output: the pair of points whose slope has the largest magnitude.
Time constraint: $O(n \log n)$ or better.
Please don't spoil the ...
-1
votes
1answer
71 views
Transistor Level Design of XOR gate [closed]
What would a transistor level design of an XOR gate look like?
2
votes
2answers
41 views
finding signs of 3 numbers
This is slightly more of a coding problem than a math problem but I think it is still relevant.
So let's say I have 3 numbers A,B,C and I can only call a given function if two are negative and one ...
0
votes
1answer
78 views
Array resize problem
I need help with this problem if anyone can help.
Suppose you have an empty array of size $s$. Then you keep inserting elements in it. But before you insert an element, if the array is filled, then ...
0
votes
0answers
32 views
How to formulize this logarithmic expression?
If you have this list of numbers {$1, 2, 4, 7, 11, 16, 21, 27, 33, ...$}
Where the list starts at 1, then the next number is $1 + x + \left\lceil\log_2{x}\right\rceil$ where $x$ is the current ...
0
votes
1answer
20 views
Resizing array problem
I need some help with this problem.
Suppose you have an array of size $n$ where $n = 4^i$ for some $i \geq 0$, with initially $n$ elements in it. Let $m$ be the current number of elements in the ...
0
votes
0answers
37 views
Potential function in amortized analysis
I am trying to calculate the amortized cost of a dynamic array, that's size becomes 4 times the size when the array is filled. (when you re-size, you create a new one and copy the elements there).
...
1
vote
0answers
38 views
Mean matching size
Suppose there is a simple bipartite graph $G(X,E,Y)$, where $|X|=n_1$, $|Y|=n_2$, $|E|=m$. The edges $E$ are chosen uniformly at random.
The question is what is a mean value of the size of the ...
3
votes
1answer
39 views
Which categories correspond to the untyped and typed lambda calculus?
Simply typed lambda calculus is the internal language of Cartesian Closed Categories.
What category has its internal language the typed lambda calculus? And the untyped lambda calculus? Can we in ...
0
votes
1answer
23 views
Questions about DFA with Sigma* exiting arrow and RE
Assume Sigma* contains all english alphabet chars. Then in my DFA, I have an exiting arrow of Sigma* and another exiting arrow of "a"(symbol from the alphabet) from one state. Will this be a valid ...
0
votes
0answers
39 views
Computation efficient recursive pairing function
Cantor pairing function is really one of the better ones out there considering its simple, fast and space efficient, but there is something even better published at Wolfram by Matthew Szudzik, here.
...
0
votes
0answers
27 views
At most O(nk) inversions question
I am working through some intro algorithms problems on my own, and do not understand the explanation to problem 2-2b, lemma 8, pg. 7-8, of why the possible range of elements which can be inverted with ...
3
votes
1answer
71 views
Is the square of a self-centered graph also self-centered?
I am trying to work out a problem. Given a self-centered graph, is the square of the graph also a self-centered graph? I tried numerically on few graphs given in ...
2
votes
1answer
42 views
How is naive CLIQUE algorithm polynomial time?
I am reading Introduction to Algorithms 3rd for my CS course. Just before theorem 34.11 on pg 1087, it says the running time of the naive algorithm to try all k-subsets of $V$ is ...
0
votes
1answer
60 views
Doing research on Google Matrix and PageRank algorithm
I'm doing research on Google Matrix and PageRank algorithm. In a paper, there are terms that I'm unaware of, such as stationary distribution, stochastic matrix, convex combination, markov matrix, ...
1
vote
1answer
30 views
Specify conditions for $\alpha$ so that the iteration $x_{n+1} = x_n - \alpha f(x_n)$ converges to root of f.
Specify conditions on $\alpha$ so that the iterative process $x_{n+1} = x_n - \alpha f(x_n)$ converges to root of f if started with $x_0$ close to the root.
It is suggested that the proof should ...
3
votes
1answer
31 views
why is it necessary to show NP in order to show NPC?
I am reading Introduction to Algorithms 3rd for my CS course. Lemma 34.8 says to prove a language $L_2$ NP-complete:
If $L$ is a language such that $L_1 \le_P L_2$ for some $L_1 \in$ NPC, then $L_1$ ...
2
votes
2answers
143 views
Reference request - Any suggestion for good Abstract Algebra pdf for computer science?
I'm a computer science student and I'm starting to learn Abstract Algebra next week.
I'd like to get a suggestions for good PDF book about Abstract Algebra.
Thanks!
0
votes
3answers
70 views
Is indistinguishability an equivalence relation?
Let x and y be strings and let L be any language. We say that x and y
are distinguishable by L if some string z exists whereby exactly one
of the strings xz and yz is a member of L; otherwise, ...
4
votes
1answer
43 views
Does the following transformation preserve context-freeness?
I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always ...
1
vote
0answers
13 views
Lower bound on building heap.
A lower bound of the needed number of comparision to build a heap is given by GASTON H. GONNET and J. IAN MUNRO as following
THEOREM 4. $1.3644... n + O(lg n)$ comparisons are necessary, not only ...
3
votes
2answers
180 views
Question about regular languages and finite automata
We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the ...
9
votes
5answers
346 views
Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $.
Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $, with induction.
I get the intuition behind this question. Clearly, the given function isn’t even growing ...
1
vote
1answer
54 views
Applying substitutions in lambda calculus
For computing $2+3$, the lambda calculus goes the following: $(\lambda sz.s(sz))(\lambda wyx.y(wyx))(\lambda uv.u(u(uv)))$
I am having a hard time substituing and reaching the final form of $(\lambda ...
0
votes
0answers
32 views
Expressing functions using Karnaugh map [duplicate]
Using the Karnaugh map, express the following function:
$F(0, 1, 4, 5, 8, 10, 11, 12, 13, 15)$
would this be the answer
I'm a little confuse
($b_1=0$ and $b_0=0$) or ($b_3=0$ and $b_1=0$) or ...
1
vote
1answer
16 views
Can kCNF have less than k variables per clause?
An example given by my prof in her notes:
The following formula is in 4CNF: $(w\vee y\vee \neg z)\wedge(w\vee\neg x\vee z)\wedge(w\vee\neg x\vee \neg y\vee z)$
I originally thought that maybe ...
22
votes
12answers
2k views
How is the set of all programs countable?
I'm having a hard time seeing how the number of programs is not uncountable, since for every real number, you can create a program that's prints out that number. Doesn't that immediately establish ...
1
vote
2answers
101 views
set theory subsets and inheirtance in Java
I started reading Concepts of Modern Mathematics and naturally, I came across set theory. I was wondering if someone could clarify my understanding for subsets by way of inheritance in Java or any ...
1
vote
1answer
91 views
Basic Maths question regarding the selection sort formula.
I'm training to be a software developer and use Stack Overflow a lot, but I'm afraid some basic Maths has gotten in my way. I apologise in advance for a question that may be too easy to be posted here ...
