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

3
votes
1answer
52 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
23 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
28 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') ...
17
votes
3answers
941 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
47 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
48 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
38 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
32 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
35 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
36 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
68 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
0answers
45 views

Interstellar's Gargantua (Black Hole) Equation [closed]

I don't really know if this is a physics, computer science or mathematics question so kindly excuse me if I posted it at the wrong place. I want to know what was maths/equations that were used to ...
0
votes
1answer
39 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
100 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
36 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).
1
vote
0answers
61 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
28 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
21 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
109 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 ...
-1
votes
0answers
24 views

Algorithm for vector space transformation [closed]

In my text book I've got an example which is as follows: Create an algorithm which calculates coordinates of a point after a space transformation took place. Transformations may be scaling or ...
0
votes
1answer
14 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??
0
votes
0answers
16 views

Interpolating transformation matrices

I read not to interpolate transformation matrices by linearly interpolating. Can someone explain to me why interpolating transformation matrices by linearly interpolating the matrix components is a ...
2
votes
1answer
54 views

What format is this?

I was given a snippet and can't seem to parse it myself, what's the name of this format and is there a tool that will render it like latex or mathML like this site does? ...
0
votes
0answers
49 views

What is the highest number that could be written down in principle using all computers in the world?

I read somewhere in the internet, that the capacity of all computers in the world would be about $10^{18}$ bytes. Does this mean, that in principle, a number with $10^{18}$ digits could be written ...
2
votes
0answers
50 views

How can we find the elements?

I want to describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set ...
1
vote
1answer
55 views

How does the function work? [closed]

Could you explain me the function of the following two algorithms? ...
1
vote
1answer
53 views

Expected time of Quicksort

I am reading the proof of the theorem: The Algorithm Quicksort sorts a sequence of $n$ elements in $O(n \log n)$ expected time. The proof is this: For simplicity in the timing analysis assume ...
0
votes
3answers
53 views

How to find upper and lower bound without using formula?

I am studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything usefull. Prove the following sum is theta(n^2) (we have to find ...
0
votes
1answer
19 views

A language $L$ is polynomially transformable to $L_0$

Could someone explain to me the following definition?? A language $L$ is polynomially transformable to $L_0$ if there is a deterministic polynomial-time-bounded Turing machine $M$ which will convert ...
1
vote
1answer
15 views

Prove that $L=\{a^nb^nc^md^m \mid m,n >=0\}$ is context free language

I'm trying to write the grammar of this language, in order to prove that it is CFL but I'm stuck because m or n could be 0. The language is: $L=\{a^nb^nc^md^m \mid m,n >=0\}$ . If they were ...
0
votes
0answers
37 views

AoPS Intermediate Algebra vs. Higher Algebra by Hall and Knight? And some more questions about learning math.

Ok. I'm learning algebra at the level of AoPS algebra 2, and I want to quickly progress through math. Allow me to explain the situation. I am highly interested in artificial intelligence/computer ...
1
vote
0answers
34 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
1
vote
1answer
22 views

Why the only binary MDS codes are trivial ones?

Why the only binary MDS codes are trivial ones? I have been thinking how to draw a contradiction by assuming the MDS code is not trivial. Thank you very much!
2
votes
2answers
17 views

Proving that median of list $[x_1,x_2,…,x_n]$ minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $m$ is some number

The problem is in the title. Here is a detailed description: Let's say we have list $[x_i]_{i=1}^{i=n}$ where $x_i\in\Bbb{N}$. I want to pick such $m\in\Bbb{N}$ which minimises the sum ...
3
votes
1answer
99 views

What kind of edge do we have?

In order to find the kind of the edges of a graph, at which we applied the Depth-first search algorithm, we could use this: $$\begin{bmatrix} \text{ tree edges: } x \to y & [d[y],f[y]] \subset ...
1
vote
1answer
49 views

Trying to find formula for max number of nodes in a non-Binary tree.

I'm trying to find the max number of nodes in a tree that is defined as follows: The root can have at most $2$ children. Each subtree on the left can have at most $L$ children. Each subtree on the ...
0
votes
0answers
20 views

Is there a universal constant for size of disjoint clauses in 3-CNF

We are given a 3-CNF formula $\Phi$ on n variables, and a guarantee that at least 1% of $2^n$ possible assignments satisfy all clauses in $\Phi$. Now construct set $S$ of disjoint clauses so that no ...
2
votes
0answers
29 views

Linear Algebra Book Recommendation [duplicate]

I am taking an undergraduate course in computer science an is in the first year of my college. I like mathematics and am willing to learn Linear Algebra first and then move on to Abstract Algebra and ...
1
vote
1answer
40 views

How do I solve for the zeros of a Chebyshev polynomical? (on a computer)

I am working on a computer program and have a method that returns a number for a given $x$, $y$. So $f(x, y) = z$, where $f$ is my method. if I know $y$ and $z$, can I find what $x$ will be, without ...
1
vote
1answer
21 views

Discreet Math - Given n>= 5 how many times does fib(4) occur?

I have been trying to solve the below problem (and similar problems) but I have no clue how to tackle it. Can please help me tackle this particular problem, and how to attack similar problems? The ...
1
vote
1answer
15 views

Urn Probability Combination Problem

I am in my first year of Comp Sci and I am reviewing for my Math Final. There are two Urns $U_1$ and $U_2$. $U_1$ has $10$ red balls and $8$ blue balls. $U_2$ has $16$ red and $4$ blue. Suppose you ...
0
votes
0answers
19 views

What does it mean for an equivalence class to straddle a set of states?

In the following question, what does it mean for an equivalence class to straddle a set of states? Assume you currently have two equivalence classes Φ and Ψ. In addition you have a set of ...
2
votes
1answer
23 views

Special Binary Relations/ Empty Relation, Universal Relation And identity Relation?

The universal relation U = A × A. (Correct me if I'm Wrong). I believe that the Universal Relation is an Equivalence Relation The empty relation E = ∅. From my understanding, a Empty relation on a non ...
0
votes
0answers
21 views

Gram matrix of Gaussian kernel is not positive definite

I am developing a machine learning software, where I am trying to apply kernel methods. I have N uniformly sampled scalar values, $\{x_1,\dots,x_N\}$ from a given interval $[a,b]$. My aim is to ...
3
votes
3answers
72 views

Can a Turing Machine process an infinite string?

I read in a text book once that a finite state acceptor machine cannot be an acceptor for an infinite language. My question is does this apply to Turing Machines? The implication, it seems to me, ...
1
vote
2answers
31 views

c(n,k) equals subdivisions

To compare n files, the total comparison count is: $$ {{n}\choose{k}} = C^k_n = \dfrac{n!}{k! ( n - k )!} $$ with k = 2. Input space is composed by all pairs of files to compare. I want to split ...
1
vote
0answers
26 views

How to check homeomorphic embedding relation programmatically?

This is a follow up to this question and Deedlit's answer. I'm looking for a precise definition of the "hem?" (tree A homeomorphically embeddable in tree B?) relation, preferably in terms of a ...
1
vote
2answers
39 views

The expected time to sort $n$ elements is bounded below

Prove that the expected time to sort $n$ elements is bounded below by $cn \log n$ for some constant $c$. Could you give me some hints how I could do that?
0
votes
1answer
28 views

Is my Turing Machine (Transition Function) correct for finding if a string is of even or odd length?

I've been asked to create a formal Turing Machine (by means of a transition function) to which takes a string $a^n \in$ {a}* and decides whether it is an even or odd length. What I have made is the ...