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
8 views

How to calculate recurrence $F(n) = F(n/u) + \Theta(n^k)$ where $u,k \in \mathbb{N}$

$\Theta$ is used as in Bachmann-Landau notation (often called as Big-O notation convention). How does one in general the recurrence relation of the following from: $$F(n) = F(n/u) + \Theta(n^k) ...
0
votes
0answers
7 views

Create a list with elements from an other list with specific display order

Consider a singly-linked list $L$ each element of which is a struct with two fields, an integer num and a pointer next to the ...
0
votes
1answer
23 views

Construct an automata for this language

Let $\mathcal{L}_1$ be the language over alphabet $\{0,1\}^*$. Define language $\mathcal{L}_2$, call even-$\mathcal{L}_1$, as: $$\mathcal{L}_2 = \{ w_2 w_4 \ldots w_{k} ~:~ w_1 w_2 w_3 w_4 \ldots ...
0
votes
1answer
20 views

Draw a 2-3 tree, insert and delete a key

Assume that at the nodes of a 2-3 tree, the following keys are saved (in an increasing order): $3,6,9,15,18,21,24, 27, 30, 33, 36$. It is also given that the root is a 2-node that contains the number ...
2
votes
0answers
17 views

Decidability of given languages

Given are the following languages: $L_1 = \{0\}\\ L_2 = \{w \in \{0,1\}^{*} | L(M_w) = \{0\}\}\\ L_3 = \{w \in \{0,1\}^{*} | M_w \text{ stops at all entries }\} \\ L_4 = \{w \in \{0,1\}^{*} | ...
0
votes
2answers
51 views

Can someone verify my assertion from this english sentence? [duplicate]

This is from Discrete Mathematics and its Applications This is the book means when mentions a list of common ways to express conditional statements After going through the list, I immediately ...
0
votes
0answers
42 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 ...
2
votes
0answers
50 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
1answer
20 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 ...
2
votes
0answers
45 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 ...
1
vote
1answer
16 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 ...
2
votes
0answers
34 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 ...
4
votes
0answers
34 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
25 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 ...
-1
votes
1answer
28 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))$.
2
votes
3answers
74 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?
0
votes
2answers
49 views

Regular vs Nonregular language [closed]

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
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 ...
0
votes
2answers
48 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?
0
votes
1answer
20 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 ...
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 ...
0
votes
1answer
20 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
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
20 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 ...
4
votes
1answer
47 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 ...
2
votes
1answer
103 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
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 ...
1
vote
0answers
45 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
31 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 ...
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
2answers
50 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 ...
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
98 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
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
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
32 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
43 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
29 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
33 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 ...