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

What exactly does this inequality do?

I this paper which is titled "KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation", in the section about "kmeans algorithm for vector quantization", there is the ...
0
votes
0answers
31 views

Writing regular expressions

So here's the problem: Let $Σ =\{a, b, c\}$. Write a regular expression for the set of all strings in $Σ^∗$ such that the sum of the number of $a$’s and $b$’s in the string is at most two. Thus the ...
0
votes
1answer
38 views

Give some examples of strings in, and not in, these sets, where Σ = {a,b}

Here's the set: {w : for some u ∈ Σ*, www = uu} From what I understand, it's saying "w (which is a string) such that for some u (which is another string) is an element of the possible combinations ...
1
vote
0answers
37 views

Rewriting regular expressions

For the following two regular expressions, how would I rewrite them as a simpler expression representing the same set? $b^* \cup a^* \cup (a \cup b)^*$ $\Big((a^*b^*)^*(b^* \cup a^*)^*\Big)^*$ I ...
0
votes
0answers
19 views

Big $O$ question for While and For loops [on hold]

I have to find the exact $O(N)$ for these instructions, not just the order of magnitude. I'm not getting any of the answers provided for me. I know the first loop is $O(3N+2)$. The declaration of ...
-1
votes
1answer
23 views

What are good techniques for creating a DFA state diagram given a set of accepted/rejected strings?

I am in a Discrete Structures class and my teacher is pretty big on proving his intellect to the class and getting an average of about 60% for his test questions. Right now we are working with ...
-5
votes
0answers
22 views

Python Read and write program [on hold]

Write a program to prompt for a file name, and then read through the file and look for lines of the form: X-DSPAM-Confidence: 0.8475 When you encounter a line that starts with “X-DSPAM-Confidence:” ...
-7
votes
0answers
32 views

Python Read A finle and returen capital letters program [on hold]

Exercise 1 Write a program to read through a file and print the contents of the file (line by line) all in upper case. Executing the program will look as follows:python shout.py Enter a file name: ...
2
votes
1answer
20 views

For a finite character set $\Sigma$, what would be a formal proof that $\Sigma^{+} = \Sigma^{*}\Sigma$?

Let there be a finite character set $\Sigma$, as in computer science convention. $\Sigma^{*}$ is defined as in Kleene star notation (https://en.wikipedia.org/wiki/Kleene_star) with $\Sigma^{+}$ ...
0
votes
0answers
35 views

P vs NP: Is there a “mathematical” way to state it?

If I wanted a statement of the Riemann Hypothesis, I could say the prime counting function pi(x) satisfies such and such an analytical approximation. If I wanted a statement of the P vs NP problem, ...
1
vote
1answer
15 views

Calculating some probability of buying different cards

This problem was recently featured in an ICPC contest. The problem stated, without taking the story into account and as well as I recall: Peter likes a fad card game. This game has various cards, and ...
1
vote
0answers
11 views

Is there a Little law for a network of two connected queues?

From Patterson et al' Computer Organization and Design: Throughput and Response Time Do the following changes to a computer system increase throughput, decrease response time, or both? ...
0
votes
2answers
39 views

Diagonalization Principle

Diagonalization principle has been used to prove stuff like set of all real numbers in the interval [0,1] is uncountable. How is this principle used in different areas of maths and computer science ...
0
votes
1answer
36 views

Purpose of Loop invariant

I have some small fairly easy questions regarding following procedure. My teacher has post some answers which I fairly understand but also have questions about. Note: I have taken a screenshot of the ...
-4
votes
1answer
27 views

Binary word addition; error pattern

If a word $a = a_1,a_2,...,a_n$ is sent is sent (this is in regards to coding/IT/etc.-I'm trying not to include any extraneous information) and a word $b= b_1,b_2,...,b_n$ is received (where the ...
1
vote
2answers
30 views

expected value of final x using the following algorithm

It has a bit of pseudo code so i'll try to explain x = 0 for i from 1 to n: if random() > 1/4: x = x + 5 else: x = x - 1 the probability ...
1
vote
0answers
24 views

Chaining integer division operations

In an assembler program I am writing, I need to (quickly) calculate $a\text{ mod }n$. Now, in the language I am using there is a division instruction that takes two numbers $x$ and $y$ and returns ...
1
vote
1answer
35 views

Computably enumerable closed under inverse image

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a computable function and let $A \subseteq \mathbb{N}$ be computably enumerable. I'm trying to find a reason why the inverse image $f^{-1}(A)$ is also ...
0
votes
1answer
32 views

Find a recurrence to count paths in a directed graph

Suppose we have an unweighted directed graph with vertices numbered as $1...n$ From each vertex $i$ there are edges to $i+1$, $i+2$ and $i+7$. My task is to find a recurrence $f(i,j)$ to compute the ...
3
votes
2answers
60 views

Proving the rules of a complicated game are well defined

What strategy could one use to formally model a game and prove that the rules do not lead to any self contradiction? A major example that comes to mind is Magic the Gathering. The card ...
0
votes
0answers
6 views

Example of weighted max cut taking exponential time iwth local search

In the Coursera algorithms course, the instructor mentions some graphs with weighted edges take exponential time to solve in the worst case with local search the max cut problem. The search algorithm ...
0
votes
1answer
96 views

Finding number of subarrays not including certain pairs

How many contiguous subarrays of an array exist such that they do not contain certain pairs of positions of the array? For eg. if array ={11,22,33,45} and if we do not want to include say position ...
0
votes
1answer
43 views

Proof that there isn't a graph search algorithm that is complete with finite memory

Is there a proof that any graph-search algorithm capable of exploring any graph (where there is a upper bound on the degree of each node and there is an ordering of the edges at each node-i.e left to ...
0
votes
0answers
15 views

Why $H_{V^* \cup W^*} > H_{V \cup W}$ if $H_V$ denotes entropy of language

Let $W \subseteq X^*$ be an infinite language over a finite alphabet $X$, and define ($|w|$ denotes the length of $w \in W$) $$ H_W := \limsup_{n\to \infty} \frac{\log_{|X|} | \{ w \in w \in W, |w| = ...
0
votes
0answers
52 views

Standard notation for the transform that turns a function $A \rightarrow (B \rightarrow C)$ into a function $B \rightarrow (A \rightarrow C).$

Suppose we're given sets $A,B$ and $C$. Then to each function $f : A \rightarrow (B \rightarrow C)$, we can assign another function $F : B \rightarrow (A \rightarrow C)$ by defining: $$F(b)(a) = ...
2
votes
0answers
13 views

Is cubic graph decomposition into claws NP-complete?

I am aware that deciding the existence of decomposition of a cubic graph into edge-disjoint claws is polynomial time solvable. What is the complexity of deciding the existence of decomposition of ...
2
votes
1answer
66 views

How is this equation evaluated $\binom {n}2 = \frac{n^2}{2}$?

I would like to know how $\binom {n}2 = \dfrac{n^2}{2}$ works out while I'm reading a proof on this page. I have tried several ways, but I couldn't. i.e. we knew that combinatorics formula that ...
0
votes
0answers
23 views

Inequality for the set of factors of length $n$ of some regular language

If $W \subseteq X^*$ is some language denote by $$T(W) := \{ u \in X^* : \mbox{there exists }x, y \mbox{ such that } xuy \in W \}$$ the set of factors (infixes) of $W$. If $W$ is regular, then ...
2
votes
2answers
27 views

Set of all factors of regular language regular?

If $L$ is a regular language (i.e. acceptable by a finite automata), is the the set of its factors (infixes) also regular?
3
votes
2answers
37 views

Computational Complexity of Primality Checking

"PRIMES in P" proved that primality checking is in $P$. However, the CS 101 prime checking algorithm is to divide a number $n$ through all integers up to ${\sqrt n}$ , and if no results are whole ...
5
votes
1answer
63 views

Counting the expected number of strings with a given contiguous substring.

Question: Let a random bit string $x$ of length $n$ be given. What is the expected number of bit strings $w$ of length $2n$ that contain $x$ as a contiguous substring? What I know: For any bit ...
0
votes
0answers
9 views

Identify arbitrer policy of a network component

I would like to identify the formula of the service rate of a network component ARB based on input and output rates of flows crossing it. For instance, I have several flows which cross several ...
-4
votes
1answer
56 views

Why is it that if one NP complete problem is solved, all NP problems are solved?

I get NP completeness, but I don't understand why it's said that by solving one NP complete problem, all of them are solved. Is it saying that solving one NP complete problem proves that all of them ...
0
votes
1answer
42 views

Prove $K_4-Cover$ is NP-Complete

I'm studying for a computational theory exam, and as part of my studying I'm trying to solve previous years' exams. I have come across this problem and I'm having some difficulty with it: Let $ G ...
1
vote
1answer
57 views

What is the context-free grammar for $0^{n}1^{2n+1}0^{n}$

context free grammar for $0^{n}1^{2n+1}0^{n}$ I've tried several different methods to find it but I can't figure out how to make both sides opposite to each other...please help I've been working on ...
1
vote
1answer
30 views

What is a transfer function?

If: $N$ is a set of nodes in a program dependence graph, which is a graph with two type of edge $L$ is a lattice of security levels What does the following mean: "For every $x\in N$, a so-called ...
0
votes
2answers
45 views

Fast multipole method: help on tutorial

I have some hard time with the FMM (Fast multipole method). I try to understand the basics with: "http://www.umiacs.umd.edu/labs/cvl/pirl/vikas/publications/FMM_tutorial.pdf". So here are my ...
-1
votes
0answers
54 views

Learning Math for Computer Science

Apologies if this has been already asked. I have gone through a lot of different questions but they don't adapt to my personal situation. I have a 2 years diploma in software development and I am ...
6
votes
1answer
120 views

FRACTRAN for natural numbers

Is there a simple analogue of FRACTRAN that maps a natural number to a natural number, instead of mapping a list of fractions to a natural number? One could use Gödel encoding to translate FRACTRAN ...
0
votes
2answers
27 views

Unique Aggregation of Numbers

Suppose I have 5 numbers: 1,7,13,5,6. I want to perform some kind of algorithm that allows me to derive a number such that if any of those numbers changed in value or switched in order that I would ...
1
vote
0answers
28 views

Calculus book for computer science students

I'm going to teach calculus I and II to undergraduate computer science students and I would like to know if someone here knows some book or site with easy calculus applications in computer science. ...
0
votes
1answer
24 views

Adding color components with transparency

If we define a color with transparency as $(r,g,b,a)$, with $r,g,b,a\in[0,1]$, how do we define $(r_1,g_1,b_1,a_1)+(r_2,g_2,b_2,a_2)$? The definition must be closed, and must represent the computer ...
1
vote
0answers
14 views

Each recursive approximating sequence for Kolmogorov complexity is not uniform

Denote the plain Kolmogorov complexity by $C(x)$. Let $\phi(t,x)$ be a recursive function and $\lim_{t\to\infty} \phi(t,x) = C(x)$ for all $x$. For each $t$ define $\psi_t(x) := \phi(t,x)$ for all ...
0
votes
0answers
20 views

Closest Triplets (Advanced form of Closest pair algorithm)?

So I was trying to solve for the closest triplets from the given number of points(closest in terms of sums of their Euclidean Distances i.e. D(P1,P2)+D(P2,P3)+D(P3,P1) ) ! I thought of proceeding in ...
2
votes
0answers
15 views

Kolmogorov complexity of substring if string is divided according to rule

Denote the plain Kolmogorov complexity of a string $u$ by $C(u)$. Now let $u$ be a string of length $n$ with $C(u) \ge n - O(1)$ and suppose $u = u_1 \cdots u_{\log n}$, a subdivision of the ...
0
votes
1answer
27 views

Length of substring if we just consider a subdivision in $\log n$ substrings

Let $u$ be a string of length $n$ and consider a subdivision in $\log n$ substrings $u = u_1 u_2 \cdots u_{\log n}$. Is it true that there exists a constant $C$ such that for each $1 \le i \le \log n$ ...
1
vote
5answers
193 views

explanation of notation in programming problem

I am trying to attempt to solve this problem but I am unsure what this equation means: $$\frac{n!}{ r!(n-r)!}$$ What do the exclamation marks mean in the above?
1
vote
0answers
31 views

On Kolmogorov complexity of first and last half of a string

Denote by $C(x)$ the plain Kolmogorov complexity of $x$ and let $x$ satisfy $C(x) \ge n - O(1)$ with $n = |x|$. If $x = yz$ with $|y| = |z|$ show that $C(y), C(z) \ge n/2 - O(1)$. Any ideas how to ...
2
votes
1answer
54 views

Implication in linear logic

Linear logic abandons the structural rules of weakening and contraction. I wanted to know whether we have $p ⊸ p$ in linear logic. Can anyone help?
1
vote
1answer
74 views

Ignoring the workspace in quantum computation

In his book Quantum Computer Science, Mermin says that, although we'll need lots of "workspace" qubits in addition to those in the input and output registers, we can essentially ignore these in our ...