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 ...

learn more… | top users | synonyms

0
votes
2answers
37 views

Increase by one, Shortest path, changes the edges or not?

as i read the following text : "Let P be a shortest path from some vertex s to some other vertex t in a graph. If the weight of each edge in the graph is increased by one, P will still be a shortest ...
2
votes
1answer
34 views

How much RAM is needed for $2^{14}$ square grid of double numbers?

How is calculated the memory that is needed for matrix of $2^{14}$ by $2^{24}$ double precision real numbers ? Matlab stops responding with 32Gb ram.
0
votes
1answer
38 views

Big O - arithmetic rules

I need to prove the following statement: $O(f(n)g(n))=f(n)O(g(n))$ At first I thought the statement is false but apparently it is true. How can I prove it?
2
votes
1answer
25 views

Entropy determination regarding lossless data compression

Suppose I had many computer data files to compress losslessly and wanted to know what is the theoretical limit to each one as far as minimum filesize possible. How would a math person go about doing ...
4
votes
2answers
102 views

Computers can't deal with limit of $\Delta x \to 0$

While I was studying about finite differences I came across an article that says "computers can't deal with limit of $\Delta x \to 0$ " in finite differences.But if computers can't deal with these ...
5
votes
1answer
120 views

Good resource/exercises for learning asymptotic analysis?

I am studying asymptotic methods right now; things such as mellin transform, inverse mellin transform, saddle point method, laplaces method, etc... and I get very frustrated because I can't get very ...
0
votes
0answers
11 views

Amortized analysis: Understanding the potential formula

The potential formula is: $$\overset{\wedge}{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1})$$ $\overset{\wedge}{c_i}$ the amortized time of operation $i$ is the actual time $c_i$ plus the change of the ...
1
vote
0answers
50 views

Pumping Lemma for Context Free Languages: Is this language CFL?

I am learning for the first time the Pumping Lemma for CFL, and I thought I understood how it works until I came across this example: "Show that $L = \{a^m b^m c^n \mid m \leq n\}$ is not a CFL." My ...
0
votes
1answer
22 views

Proof of why the partition function Z in probabilistic graphical models (PGM) is NP-complete

I was wondering if someone knew why computing the partition function for probabilistic graphical models is NP-Hard? I would like to see a full blown rigorous proof, however, I am as happy to get a ...
2
votes
1answer
18 views

Turing machine that goes left on first symbol

I have a turing machine with transitions given by the following table I'm inputting the string aaaa. So if I look at the first symbol "a" in state A, it says to replace it with an X, go into state ...
3
votes
0answers
64 views

For those wanting to study theoretical computer science, is Math a degree that worth more than Computer Science?

At my University, everyone first enrol in a Science and Technology, a very general course, and then choose the specialisation (like Computer Science, Math, some Engineering, etc). As I was finishing ...
0
votes
1answer
21 views

How to take the integral of a derivative to obtain desired result?

I am aiming for the form of derivative below computed over time that causes its differentiated variable V to go from an initial -.001 and increase to reach 10. I will explain my current calcs below ...
2
votes
0answers
78 views

Humankind knows the prime factorization of the first how many consecutive integers?

I am only looking for an approximation. I'm guessing the answer must be somewhere between $10^{20}$ and $10^{50}$. . Edit: Okay so my first initial estimation was pretty poor... I should have ...
2
votes
0answers
62 views

A Strange Algorithm on Processor [closed]

We have n processes, each with a predetermined start and end time. We want to use the ...
2
votes
1answer
34 views

The disease problem

Students are sitting in a n * n grid. There's a disease spreading among them in a particular fashion. At start, there a 'k' students infected(At random). After every time step(equal intervals), the ...
4
votes
2answers
86 views

Las Vegas algorithm to satisfy most clauses in SAT

Consider an instance of SAT with $m$ clauses, where every clause has exactly $k$ literals. Give a Las Vegas algorithm (i.e., an algorithm that always gives the correct result) that finds an assignment ...
2
votes
1answer
46 views

Most efficient mental way to convert Decimal to Hexadecimal

My question is as follows: What is the most efficient mental way to convert Decimal to Hexadecimal? I've heard of many methods. Some people divide the decimal by 16 and find the remainder. Others ...
0
votes
1answer
40 views

Prove that wheel (Wn) graph family are hamiltonian

I need to determine and prove that wheel (Wn) graph family are hamiltonian. I know that the Wn graphs are hamiltonian where it's possible to create a cycle that contains all the vertices, but How to ...
5
votes
1answer
85 views

Numbers as sum of distinct squares

Yesterday Polish Olympiad of Information Science ended, one of the questions was purely mathematical, Squares (PL). In the task, we have defined square ...
1
vote
1answer
50 views

Counting the number of complete bipartite subgraphs

I am stuck with problem and not getting much ideas. I have a graph with $N$ vertices and $M$ edges. I have to count number of ways I can choose a pair of set of vertices say $(p,q)$, such that every ...
1
vote
0answers
22 views

Two decidable languages for which a mapping reducibility does not exist?

The trivial null language might not be reduced to another language, but are there standard examples of two decidable languages $L_1$ and $L_2$ such that there is no mapping reduction possible from ...
1
vote
0answers
39 views

How to find the shortest path of a graph in a turing machine

I'm reading about Turing machine and I saw some examples as: Let $M_{1}$ a Turing Machine and the language $B = \{w\#w \vert w \in \{0,1\}^{*}\}$, We want $M_{1}$ to accept if its input is a member of ...
0
votes
0answers
40 views

How can be a conservative field constraint be efficiently implemented in a continuous optimization problem?

Suppose we have the following continuous optimization problem: $$ \underset{x}{\mathrm{minimize}}f\left(x\right) $$ subject to $$ \exists X:\nabla X=Jac\left(X\right)=x $$ where $f$ is a function ...
1
vote
2answers
21 views

How to determine the increase in the Z-Axis. Of a tessellated sphere

I have been tasked with drawing the sphere below for a programming assignment using openGL. I have the assignment mostly completed however I am having issues figuring out the math for the sphere. For ...
0
votes
1answer
18 views

What is the complexity of halving the size of an $n$-bit number every time.

I was discussing this question with my fiend the other day and was hoping to get some confirmation from someone if the logic I used is correct. Suppose that we have a number $N$ in base 2 ie ...
0
votes
0answers
15 views

Check if an axis aligned bounding box intercepts with a triangle

As the questions says I am trying to check if an AABB intersect with a triangle. I've divided the problem in 3 parts: check if any of the triangle edges intersect any of the AABB faces check if the ...
3
votes
1answer
50 views

How to find an expression for a number via a given set of math operators and constants?

Consider one gives you $n$ digits of a (possibly irrational) number and a finite set of math operators and constants, like $\{\sin(x), \ln(x),+,\times, \pi,e,7\}$. Then he asks you to build a ...
1
vote
0answers
19 views

How to define percentage values in terms of scalar

Imagine a game in which you choose many cards with different A,B,C values. Such as : Card 1 A - 4 B - 5 C - 6 Card 2 A - 2 B - 7 C - 4 ... and so on.. To ...
2
votes
2answers
74 views

Is it possible to express the idea of a number bigger than any other number ($\infty$) in programming languanges? [closed]

I'm studying graphs and algorithms, most of the algorithms we're using (such as Prim's algorithm), have the need of a table with a symbol $\infty$. Which in some contexts mean that it is the biggest ...
0
votes
1answer
18 views

Nondeterministic finite automaton understanding problem

It is probably a silly question but I have problem understanding it. Let's say I have to design a nondeterministic finite automaton that accepts the language consisting of words containing a string of ...
0
votes
1answer
29 views

Pushdown automaton design

I have to design a PDA that recognizes the language: $$L=\{w \mid \#(a,w) - 3\#(b,w) = 2\} $$ where $\#(a,w)$ means the number of letters $a$ in $w$ My idea is to count $a$'s and $b$'s. I have to ...
0
votes
1answer
22 views

Why are all singletons confluent?

A relation R of a set M is confluent, if $ \forall x \in M \forall w1,w2 \in M :((xRw1 \land xRw2 ) \to \exists z \in M (w1Rz \land w2Rz)) $ . 1. Someone told me that all singletons, no matter the ...
0
votes
1answer
48 views

What is confluence?

I got a worksheet at university last week, and the first task is: A relation R of a set M is confluent, if $ \forall x \in M \forall w1,w2 \in M :((xRw1 \land xRw2 ) \to \exists z \in M (w1Rz \land ...
0
votes
1answer
39 views

Deterministic finite automaton algorithm

I am having a little trouble understanding this question. For a DFA M = (Q, Σ, δ, q0, F), we say that a state q ∈ Q is reachable if there exists some string w ∈ Σ∗ such that q = δ∗(q0, w). Give an ...
0
votes
1answer
29 views

Evaluating math proofs by computer

Is there any way to evaluate (check) math proofs (entered in some convenient for computer form) by computer? Only thing that comes to my mind is functional programming, different logics, but I'm not ...
0
votes
2answers
55 views

How to prove Kleene star to be uncounably infinite?

Hi I have a language $L = \{a, b\}$. How can I prove that the Kleene star (set of all words over the language) of this language is uncountably infinite or countably infinite?
1
vote
2answers
24 views

Pumping Lemma proof

We have a language $$ L = \{\text{w element of } \{a,b\}^* \mid \#(a,w) = \#(b,w)^2 \} $$ where $ \#(a,w) $ means the number of letters $a$ in $w$ I would like to show that this language is not ...
0
votes
2answers
24 views

How to show if a language is infinite, then there is no upper bound on the length of words in L?

L is a language over a finite alphabet. How to show that if L is infinite, then there is no upper bound on the length of the words within L? Can someone help me prove this.
1
vote
0answers
37 views

Can you use chinese remainder theorum to convert hex to dec in your head?

At one time I was able to convert hex to decimal in my head, using a trick I learned in college. I have not used it in years, and forgot how. Does anyone remember how to use the Chinese remainder ...
-1
votes
1answer
102 views

How can I retrieve all the results in one go? [closed]

Please excuse me for posting this question here, but I'm just not sure where this question properly belongs; moreover, as I'm in search of a funded Masters or PhD in Mathematics abroad, perhaps this ...
1
vote
0answers
44 views

Algorithm to compute wether a stabbing line exists for a set of line segments

Let $S$ be a set of n segments in the plane. A line $L$ that intersects all segments of $S$ is called a traversal or stabber of $S$. Give an $\mathcal{O}(n^2)$ algorithm to decide if a stabber for $S$ ...
3
votes
1answer
50 views

FOL and Conjuctive Normal Form Conversion

I see the CNF from following firs order logic: $ \forall x [ \forall y [ \neg A(y) \vee B(x,y) \Rightarrow [ \neg \forall y B(y,x) ] ] $ is equivalent to : $ (A(f(x)) \vee \neg B(g(x),x)) \wedge ...
0
votes
1answer
31 views

How do I generate regular expression from this deterministic finite state automaton?

I want to create a regular expression from the following deterministic finite automaton: "abb" substring search How do I generate regexp from above dfa and what are the steps for doing so? ...
0
votes
1answer
23 views

The complexity of Depth First Search

Can anyone tell me what's the complexity of Depth First Search? I have no idea about what does mean by the complexity.
0
votes
4answers
66 views

Prove that $G$ has at least $q-p+c$ cycles.

I need your help with this question: Suppose that a graph $G$ has $p$ vertices, $q$ edges, and $c$ components. Prove that $G$ has at least $q-p+c$ cycles. I don't know how to prove that.
1
vote
1answer
33 views

Show that the language is not regular using Myhill-Nerode Theorem

I saw that similar questions have been answered on this site, but I've been unable to translate those answers to my problem. $$L=\{ww^R\mid w \in \{a,b\}^*\}$$ This is what I tried: BWOC, assume ...
0
votes
1answer
11 views

How to properly determine observations related to a Hidden Markov Model alike problem?

I got a an exercise problem which should be seen as a HMM scenario and argument some statements. However I'm quite confused about how to properly solve and argument my solutions. Problem tells: ...
0
votes
1answer
79 views

Graph DFS, BFS and some inference

Suppose G is a connected, undirected graph with at least 3 vertexes. we know the order or visiting the vertexes in DFS and ...
0
votes
1answer
31 views

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$?

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$? I do not think it applies because there no $n$ term and there is no $n^k$ for a $k$ which would equal $0$.
1
vote
1answer
24 views

Base conversion between base r^3 to r^2

The problem asks the following: If $(\alpha2)_{r^3} = (r3\beta)_{r^2},$ find $\alpha, \beta,$ and r. First off, I assume $r^2$ > 3 and $r^3 > 2$. I know that $(r3\beta)_{r^2}$ = (10 _ _ _ _ ...