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
0answers
27 views

What is the name of a graph structure with 'ports'?

I am wondering what the name of the following structure is. I might call it the madeup name "graph with ports" but most likely it already has a name that i am not aware of. The interesting thing to me ...
1
vote
0answers
37 views

Is a “network topology'” a topological space?

Is there any connection between the computer science phrase "network topology" and the mathematical notion of a topological space (or, is there any other way to connect "network topologies" with ...
1
vote
0answers
10 views

Rotations after inserting element in AVL-tree

We want to insert $58$ at the following AVL-tree and then we have to make rotations so that the tree is balanced. According to my notes, we are at the case RL (The first edge leads to the right and ...
1
vote
1answer
23 views

Turing machine recognizing language $L=\{a^ib^{i-j}c^j|i>j\ge1\}$

I am having some trouble with designing a Turing machine that recognizes the language: $L=\{a^ib^{i-j}c^j\big|i>j\ge1\}$ For example, word accepted by TM: $w=aaaaabbccc$ To be more precise, I ...
1
vote
1answer
13 views

Show that: $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\sum^m\} $ is not regular.

$\ \sum= \{a,b\} $ Show that: $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\sum^m\} $ is not regular. I'm trying to proof this with the Pumping Lemma, but I'm kind of confused because of the ...
0
votes
2answers
46 views

Proving L is a regular language?

I am having tough with problems like this. Can someone help me. Let L be the set of all strings that are not in the English language. Is L regular?
2
votes
0answers
32 views

Delete nodes that satisfy a property

I want to write a function that takes as argument a pointer A to the root of a binary tree that simulates a (not necessarily binary) ordered tree. We consider that each node of the tree saves apart ...
2
votes
0answers
33 views

What computations would advance math knowledge a lot?

Suppose we where given a super computer that would be capable of computing anything, but only for one day. We could for instance compute many of the Ramsey numbers. What would be some computations ...
0
votes
1answer
35 views

Proving language as regular

Suppose that A and B are languages such that A o B is regular. Suppose that B is regular. Prove or disprove that A is regular. I am having a tough time with questions relating to proving a language ...
3
votes
0answers
31 views

Elementary proof of compact space = exhaustible space?

(This is a repost of a question I asked last year on cs.stackexchange.) The work of Martín Escardó has demonstrated close parallels between classical topology on one hand and computability on the ...
0
votes
1answer
20 views

Context free grammar for AN

I need to write Context free grammar for describing moves in a game of chess using the Algebric Notation. Can anyone help me get started. f.ex. how do I write this for this move: Bb5 Bd7.
0
votes
2answers
26 views

Big-O math Question

I'm having trouble with this question: Suppose that $f(x), g(x)$ and $h(x)$ are functions such that $f(x)$ is $O(g(x))$ and $g(x)$ is $O(h(x))$. Prove that $f(x)$ is $O(h(x))$. I have tried ...
2
votes
3answers
70 views

Proving with Big O Notations

Is there a way I can prove that $O(3^{2n})$ does NOT equal $10^n$? How would that be done? Also, is it okay to simplify $O(3^{2n})$ to $O(9^n)$ to do so?
-1
votes
1answer
27 views

Big-O Math Problem [on hold]

I'm having trouble with a hard question, so, say that $f(x)$, $g(x)$ and $h(x)$ are functions such that $f(x)$ is $O(g(x))$ and $g(x)$ is $O(h(x))$. Prove that $f(x)$ is $O(h(x))$.
1
vote
1answer
346 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
0
votes
0answers
146 views

Terminology, mapping a tree to a tree

I have stumbled upon a problem; unfortunately, I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the ...
0
votes
2answers
49 views

Regular vs Nonregular language [on hold]

Let S be a language that is not regular? Suppose that T is a language such that T C S. Is T nonregular? This question is from textbook, can someone help me?
0
votes
1answer
41 views

Determining if language is regular?

Let $R$ be a regular language and $R_e := \{w\ |\ w \in R \text{ and the length of } w \text{ is even}\}$ Question: Is $R_e$ regular? Prove your answer. I am having trouble with these type of ...
0
votes
1answer
19 views

Using exchange argument in proving greedy algorithm

Here's a problem solvable by greedy algorithm: You are a company and you have list of tasks that still need to be done (but you're late with them already). For a given task we have information about ...
2
votes
1answer
102 views

An endless loop in a program that search for mathematical theorems and proofs − a milestone? [closed]

I don't know if there exist computer programs working on its own, trying to find and prove theorems, delivering proofs and go on searching for new theorems. But if (when) there are such programs, ...
0
votes
1answer
19 views

Computing time-complexity of DP recursion

I've written an algorithm which uses 3-dimensional DP table and it goes as follows: $DP[i][j][0]$ can be computed in $O(1)$ for any $i,j$ and $DP[i][j][k]=\max(DP[i][m][0]+DP[m+1][j][k-1]) $ for all ...
0
votes
0answers
31 views

I'm needing help understanding this coding theory assignment

I'm needing help understanding how to approach this assignment. Create a code consisting of binary codewords. The code must meet three requirements -- Contain at least 20 codewords -- Have a minimum ...
4
votes
1answer
46 views

How could we prove the correctness of the algorithm?

Consider two sets $D=\{ d_1, d_2, \dots, d_n\}$ and $E=\{ e_1, e_2, \dots, e_m \}$ and consider an other variable $K \geq 0$. Show that we can answer in time $O((n+m) \lg (n+m))$ the following ...
0
votes
0answers
16 views

Topological sort of a graph- how can we find a contradiction?

The topological sort of a graph can be considered as an order of its nodes along a horizontal line so that all the directed edges go from the left to the right. How could we show that all the ...
-1
votes
0answers
19 views

Show that the Dijkstra's algorithm computes correctly the shortest paths

Suppose that we are given a weighted, directed graph $G=(V,E)$ at which the edges that begin from the initial node $s$ could also have negative weights, but the weights of all the ther edges are ...
0
votes
1answer
23 views

Proving or demonstrating that an adjacency matrix of a directed graph represents a cycle(s)

I'm currently struggling with this concept for my master's thesis in a computing discipline. If we have an adjacency matrix for a directed graph, $G$, where $A[i, j] = 1$ indicates a directed edge ...
0
votes
2answers
3k views

Time complexity of the travelling salesman problem?

The dynamic programming approach breaks the problem into $2^n n$ subproblems. Each subproblem takes $n$ time resulting in a time complexity of $\mathcal{O} (2^n n^2)$. How are there $2^n n$ ...
1
vote
1answer
489 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
4
votes
1answer
87 views

How to define percentage values in terms of scalar values

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 ...
1
vote
1answer
121 views
+50

Prove correctness of algorithm using induction

Bubblesort(A) int i, j; for i from 1 to n { for j from n-1 downto i { if (A[j] > A[j+1]) swap(A[j], A[j+1]) } } Could ...
1
vote
0answers
44 views

Proving a greedy algorithm - find minimum number of terms in expression $n=a_1!+\cdots+a_k!$

Given a number $n$ (integer) I should find $a_1,\ldots,a_k$ such that $k$ is minimal and $n=a_1!+\cdots+a_k!$. I think that the following greedy algorithm should give the solution - iterating over ...
1
vote
1answer
29 views

Prove that $\{ww^R\#ww^R\}$ is not context free

I need to prove that $L = \{ww^R\#ww^R \; | \; w \text{ is in } \{a,b\}^*\}$ is not context free. I have tried using the pumping lemma for this. For $w=a^pb^pb^pa^p\#a^pb^pb^pa^p$. I have two cases ...
3
votes
2answers
2k views

Solve the Relation $T(n)=T(n/4)+T(3n/4)+n$

Solve the recurrence relation: $T(n)=T(n/4)+T(3n/4)+n$. Also, specify an asymptotic bound. Clearly $T(n)\in \Omega(n)$ because of the constant factor. The recursive nature hints at a possibly ...
4
votes
1answer
4k views

fastest method to determine if two numbers are coprime

I am working on a mathematical problem that involves coprime integers. I wrote a computer program that allows me to search for the numbers I am looking for. However I am looking at a large set of ...
1
vote
2answers
49 views

turing machine with exactly 42 states / state that is visited at least 42 times

I am trying to solve the following problems: Proof wether the following problems are decidable/undecidable: Given turing machine M: Does M have exactly 42 states? Given turing machine M: Does M ...
4
votes
2answers
88 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
36 views

Determining the coefficient of $x^n$ in $\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$

I looking for an algorithm to efficiently find the value$\mod p$ of the coefficient of $x^n$ in a generating function of this form: $$\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$$ where $p$ is some prime ...
1
vote
1answer
26 views

Would there be no input or input does not exist?

This problem is from Discrete Mathematics and Its Applications. And the definition of inverse from the book: For part 43 (c), would the inverse not exist? For the floor function, in terms of $f(a) ...
0
votes
0answers
28 views

Evaluating GCD, LCM expression plugging different numbers to get a certain number - where should I stop?

Here's a computer science problem I'm trying to solve: Given an expression tree: type expr = | GCD of expr * expr | LCM of expr * expr | Number of int ...
1
vote
1answer
43 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
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 ...
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
27 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
31 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 ...
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 ...
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, ...
0
votes
1answer
26 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)$ ...
0
votes
2answers
1k views

problem simplifying boolean algebra expression using consensus theorem

Please simplify this logic expression for me with helping boolean algebra : A'C'D + A'BD + BCD + ABC + ACD' I know that must use consensus theorem . my solve : STEP 1 : Terms 1 & 3 ...
5
votes
1answer
70 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, ...
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 ...