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

1
vote
3answers
64 views

How to solve $5000 n \log(n) \leq 2^{n/2}$

I'm trying to solve the following problem: What is the smallest value of n so that an algorithm with a runtime of $5000 n \log(n)$ runs faster than an algorithm with a runtime of $2^{2/n}$ on the ...
4
votes
2answers
101 views

Abstract Algebra in analyzing computer science

I would like to know of some uses of algebraic structures to study computer science. Parallels of what I am looking for would be stuff like the fundamental group/homology/cohomology in topology and ...
1
vote
1answer
44 views

proof DFA defines same language as minimal DFA

Given a $DFA = (Q, \Sigma, \delta, q_s, F)$ and a minimal $DFA_{MIN} = (Q_{MIN}, \Sigma, \delta_{MIN}, q_{s_{MIN}}, F_{MIN})$ where $Q_{MIN} = \{Q_i \in \mathcal{P}(Q) \mid \forall p,q \in Q_i:p ...
1
vote
2answers
23 views

How to prove $\omega$ bound without using limit?

How to show $n^{3.4} - 2015n^{2} + 3$ $\in$ $\omega(n^{3})$ without using limit? According to the definition of $\omega$, $f(n)$ $\in$ $\omega(g(n))$ if and only if $\forall c > 0$, $\exists n_0$ ...
0
votes
0answers
28 views

Trying to prove Equivalency using Boolean Algebra

The question presented was to use boolean algebra to show that XY’Z + X’Y’Z’ + XY’Z’ + X’YZ’ ≡ XYZ’ + XY’Z + XY’Z’ + XYZ’ I've tried using various laws of Boolean algebra, but the answer that I ...
1
vote
2answers
37 views

How to iterate through all the possibilities in with this quantifier?

This is a problem from Discrete Mathematics and its Applications My question is on 9g. Here is my work so far I am struggling with the exactly one person part. The one person whom everybody loves ...
0
votes
1answer
27 views

Computing $\mathrm{erfi}(\theta)\exp(-\theta^2)$:

I'm looking to compute $f(\theta):= \mathrm{erfi}(\theta)\exp(-\theta^2)$ as efficiently as possible, to double precision, with a fairly wide radius of converge. Computing $\mathrm{erfi}(\theta)$ ...
3
votes
1answer
73 views

Applications of computer science to mathematics

I have been introduced to algorithms, computability and computational complexity (as part of my minor in CS). What are some mathematical topics that I can tackle with the new perspectives I ...
0
votes
1answer
86 views

Set which has a finite bounded string length

I am trying to work on a proof. I know that using diagonalization argument, we can prove that set of languages over an alphabet is countable. But I am trying to prove that set of all languages over ...
0
votes
1answer
31 views

Finding the time complexity

Can someone please help me to solve this problem. Find a $\theta$ notation for the number of times $x=x+1$ is executed ...
2
votes
1answer
44 views

Next step to take in direct proof or a workaround around current dilemma?

This is a problem from Discrete Math and Its Applications I used a direct proof to do this proof. I understand the process/idea behind the direct proof, mainly (from ...
1
vote
0answers
24 views

If syntax with Backus-Naur form [closed]

I'm doing a "parser" with the BNF syntax. My program should get as input the condition of an "if" statement, where, if the user enters the following condition: ...
0
votes
1answer
32 views

How to express exact quantifier in this situation?

This is a problem from Discrete Mathematics and its Applications My question is on 10g. Here is my work so far. My logic behind this is to first iterate over all peoples in the world, for each ...
1
vote
1answer
34 views

Would including the outside quantifier make more sense/be logically correct?

This is a question from Discrete Mathematics and Its Applications. My focus/question is 1b. What I got was for this question was (English translation) There is a student in your class who has sent ...
0
votes
1answer
27 views

Is my inference based on previous assumptions correct?

This is to check my work on a problem from Discrete Math and Its Applications. Here is the problem. My question is on part d. I would say that c does not follow from a and b because it is true that ...
5
votes
1answer
73 views

Structural Induction vs Normal (Mathematical) Induction

In computer science and semantics I have come across structural induction many times. In that context, it is often presented as something different from but similar to mathematical induction, ...
24
votes
5answers
2k views

Can mathematics get from other sciences what it got from physics?

Throughout history, physics has been an unparalleled source of '' inspiration'' for discovering/inventing mathematical ideas, which is due to its ability to describe the physical world. But can this ...
1
vote
0answers
21 views

Is there any efficient progam or software to calculate the fractional chromatic number?

The fractional chromatic number $\chi_f(G)$ is a generation of the chromatic number of a graph $G$. It can be formulated as a linear programming question: Let $\mathcal{I}(G)$ be the set of all ...
0
votes
1answer
25 views

Currying syntax clarification - how to work through an example of currying?

I understand currying from a computer science background, so I'm happy explaining currying with a before and after example in specific languages, eg, in Java ...
0
votes
1answer
99 views

Data Storage Question Help

Apologies if this question is in the wrong area, I'm fairly new here! I'm currently studying a Computer Science degree and I'm so bad at Maths I should probably be ashamed. I'm learning, but since ...
2
votes
2answers
38 views

Mathematical Relations in Computing - Unary

I have this question that's bugging my mind: "Discuss by giving suitable examples the role of mathematical relations (Unary, binary and ternary) in computing." I'm sure it's a very simple question, ...
4
votes
2answers
89 views

Applications (“in everyday life”) of graph theory

EDIT another idea someone gave me was to consider flows in a network that would not only depend on the node at the beginning and at the end of a vertice but also about the vertice itself, like a ...
0
votes
1answer
36 views

AND, OR, NOT, and creating turing complete programming languages

Suppose I have an arbitrary computing language, and the following holds: Let all constants be finite, and assume we are computing in binary. An arbitrary number of inputs, A, and outputs, B, can be ...
-1
votes
1answer
35 views

The existence of concatenation functions in Godel Numbering?

I know that there are many schema of Gödel Numbering, and each has its own method of Concatenation, n★m. But is there a general proof that shows 'For every Gödel Numbering scheme there exists a ...
1
vote
1answer
33 views

Asymptotic Growth: little o(n) versus $O(n^\alpha)$

Let $f(n) \geq 0$ be defined for all $n \in \mathbb{N}$. Suppose $f(n)$ is $o(n)$ and at the same time $f(n)$ is not $O(n^\alpha)$ for all $0 \leq \alpha < 1$. Is this necessarily a contradiction? ...
1
vote
0answers
50 views

Computability and continuous real functions

I have found somewhere the following statement: "Every computable real function has to be continuous," but I'm not able to prove it and the "proofs" that I found in some blog posts don't seem ...
1
vote
1answer
39 views

two way infinite turing machine?

A Single tape turing machine is generally unbounded to right and starts from left. Read/write head moves to right from left after consuming a symbol. But what if we make left side unbounded too and ...
0
votes
2answers
31 views

Scan line algorithm for intersecting polygons

Given two sets of polygons $P_1 = \{s_1,...,s_m\}$ and $P_2=\{s_m+1,...,s_n\}$ with total number of $n$ segments, the previous and next segment on it's polygon can be determined in $O(1)$. Describe a ...
0
votes
0answers
54 views

Implementation of disjoint sets with union

I am looking at disjoint sets that support the function of the Union. The technique of height reduction of a tree: We always merge the smaller tree to the greater one, i.e. we make the root of the ...
1
vote
1answer
22 views

Getting tight asymptotic upper and lower bounds of product logs

Consider $$ E(n)=\log_2\left(\log_2 (4)\right) +\log_2\left(\log_2 (5)\right) ... \log_2\left(\log_2 (n)\right) $$ This is equal to $$E(n)= \log_2\left(\log_2 (4)*\log_2(5)*\log_2(6) ... ...
0
votes
1answer
29 views

Notation from predicate transformer semantics textbook

I'm reading my professor's text book on predicate transformer semantics (an extension of Floyd-Hoare logic) and I stumbled upon the following notation, in this case describing a solution to the ...
3
votes
1answer
69 views

Would this be an acceptable translation of the English statement as well?

This is an except from my textbook (Discrete Mathematics and Its Applications 7th Edition) This was my initial stab at the problem (with domain of both variables being all real numbers) Would it ...
1
vote
1answer
36 views

Would these two statements be logically equivalent?

This is an excerpt from my textbook(Discrete Mathematics and Its Applications 7th edition) When I tried doing this example on my own, my answer was "There is a student x in this class and that ...
0
votes
0answers
49 views

Converting boolean expression - POS to SOP

Convert the following to sum of products form: (a' + c)(a' + b + c')(a + b') I did the following: multiply out the first two expressions: = (a'a' + a'b + a'c' + ca' + cb + cc')(a + b') ...
18
votes
3answers
1k views

What do bitwise operators look like in 3d?

The hypothetical relation is $z = \mathrm{xor}\left(x,y\right)$ where xor is any bitwise operator such as AND, OR, NAND, etc. I see that these operations may be defined for integers trivially using ...
1
vote
3answers
53 views

On finding the $n$-th term of an arithmetic progression

Given the common difference $d$, and first term $a$ (say). It is very easy to find the $n$th term of an arithmetic progression. My question is if we are given two common differences say $d_1$ and ...
0
votes
2answers
58 views

Connections of theory of computability and Turing machines to other areas of mathematics

The question is quite straightforward: Could you point out some reference papers that highlight (in a way that is fairly accessible) the connections between (1) theory of computability, algorithms, ...
2
votes
3answers
45 views

Finding a ratio from a set of discrete values

For x = p/q, where x is a known value between 0.000 and 1.000 rounded to the thousandths place, p is an integer value between 0 and 127, and q is an integer value between 0 and 255: what is p and q? ...
1
vote
3answers
38 views

Is there a 5-regular graph of order 7?

How can I decide if there is a 5-regular graph of order 7? Some hints or tips would be appreciated. This question arises in studying for a graph theory course.
1
vote
1answer
50 views

The traveling salesman problem is NP-complete Reduction

The traveling salesman problem is NP-complete. Proof: First, we have to prove that TSP belongs to NP. If we want to check a tour for credibility, we check that the tour contains each vertex once. Then ...
2
votes
1answer
46 views

What is a simple proof that something is np complete that does not use np completeness of something else?

What is a simple proof that something is NP complete that does not use NP completeness of something else? Every proof seems to reduce to something else being NP complete.
1
vote
1answer
75 views

Proof regarding notations

I tried to solve the following question: Let $f,g$ be non-negative functions such that $f(n)=g(n)\left[1+o(1)\right]$. Prove that $f(n)=\Theta(g(n))$. I looked on two cases: ...
0
votes
1answer
41 views

Quicksort-How did we get the relation?

At the proof of the theorem that the expected time of Quicksort is $O(n \log n)$, there is the following sentence: We suppose that the partitions are equally likely, so the possibility that the sizes ...
2
votes
3answers
117 views

A mathematically mature introduction to Turing Machines and Computability [reference-request]

In the computer science course for mathematicians held at my university Turing Machines have been presented very briefly. So much so that I didn't quite get why they are relevant to mathematics. I did ...
0
votes
1answer
44 views

Existence of a maximum matching containing a vertex $v$ in a graph

Let $v$ be a vertex of a graph $G$, which is not isolated. Prove the existence of a maximum matching in which $v$ is saturated (matched).
2
votes
0answers
87 views

Traveling salesman neighborhood

I am solving some TSP problems and i got this one and i am not pretty sure about my answer. By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined ...
3
votes
1answer
33 views

Number of edges in a graph with n vertices and k connected components

Let $m$ be te number of edges, $n$ the number of vertices and $k$ the number of connected components of a graph G. Prove that: $m$ $\leq$ $\frac{(n-k+1)*(n-k)}{2}$ Thanks!
1
vote
0answers
22 views

The optimization problem of soft margin Support Vector Machine: How to interpret?

I try to understand what exactly we are trying to optimize in the case of Support Vector Machine problem, which supports soft margins. The original problem is posed first as, without soft margins ...
2
votes
2answers
124 views

Knapsack problem NP-complete

Show that the knapsack problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete. Hint:Use the exact ...
0
votes
1answer
20 views

Tree Traversal-Is the order ascending?

I have a question about the traversal of a tree. When we print the values of a binary search tree using in order traversal are the values printed in an ascending order??