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
1answer
59 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
392 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 I'...
2
votes
2answers
265 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, ...
5
votes
2answers
1k 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
65 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
58 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
35 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? ...
3
votes
0answers
98 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
64 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
183 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 ...
1
vote
1answer
30 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) ... \log_2(n)...
0
votes
1answer
51 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
78 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
54 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 ...
19
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
62 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 $...
1
vote
2answers
111 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
55 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$:...
1
vote
3answers
110 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.
2
votes
1answer
6k 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
71 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
82 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
48 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
265 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
123 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
103 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 ...
6
votes
2answers
3k 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
42 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
362 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
539 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
1answer
39 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
69 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
71 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
100 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
98 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
821 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 O(...
0
votes
1answer
33 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
491 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 ...
1
vote
1answer
114 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) ...
3
votes
2answers
764 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
81 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 [duplicate]

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 $\sum_{i=1}^{i=...
3
votes
1answer
107 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 [d[...
2
votes
1answer
577 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 ...
2
votes
0answers
77 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
58 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
45 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
159 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 ...
1
vote
1answer
1k 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 ...
1
vote
0answers
600 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 ...