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

algorithm for generating a random non-degenerate matrix over $[0,1 ]$?

I want to generate a random matrix $V\in [0,1]^{(n+1)\times n}$(not necessarily being binary ), such that for each row of $V$, there is at least one component is $1,$ and at least one component is ...
0
votes
1answer
19 views

Demonstrating Strassen's method using domain transformation: $T(n)=7T(n/2)+an^2$

I want to solve the recurrence for Strassen's method (for multiplying square matrices) with domain transformation and get a closed form. The equation is given below: $T(n)=b$, at $n=2$ ...
1
vote
2answers
41 views

The “Smooth Factor” in a number sequence

I'm trying to figure out a programming problem that has mathematical foundations. The problem says: For an array $$a = a_1, a_2, ..., a_n$$ of values, the smooth factor of $$a$$ is the length of a ...
0
votes
1answer
24 views

Explanation of Distance of binary vectors formula

So, here's once again this article from topcoder about combinatorics. After the article successfully describes what theory it will use: Combinations/Permutations, it goes into an application for it, ...
0
votes
1answer
29 views

Getting rid of exponents with n when solving with annihilators: $a_n=a_{n-1}+2a_{n-2}+2^n+n^2$

To solve the following with annihilators: $a_n=a_{n-1}+2a_{n-2}+2^n+n^2$, for $n\ge2$, with initial conditions $a_1=0$ and $a_0=0$ we would have to get rid of the $2^n$ term at least, otherwise any ...
1
vote
1answer
33 views

Solving $\scriptsize a_n=\sqrt{a_{n-1}+\sqrt{a_{n-2}+\sqrt{a_{n-3}+\ldots}}}$ with range transformation

This is a practice problem provided by a textbook on recurrences. Solve using range transformation: $a_n=\sqrt{a_{n-1}+\sqrt{a_{n-2}+\sqrt{a_{n-3}+...}}}$, where $a_0$ =4 The hint is to view the ...
1
vote
0answers
35 views

A combinatorial way to understand $\sum \log^2 n $

Stirling's formula has many derivations using the factorial function: $$ \log N! = \sum_{n=1}^N \log n = \sum_{n=1}^N \sum_{m=1}^n \bigg( \log m - \log (m-1) \bigg) = \sum_{n=1}^N \sum_{m=1}^n - ...
0
votes
1answer
23 views

Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

This problem is from Algorithms, problem 2 The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($\log n$) time algorithm to find the median of the 2$n$ ...
1
vote
3answers
33 views

Solving $a_n=5a(n/3)-6a(n/9)+2log_3n$ using domain transformation

$a_n=5a(n/3)-6a(n/9)+2log_3n$, For $n\ge9$ and n is a power of 3. $a_3=1$, and $a_1=0$ Transforming the first two terms is straightforward, but I'm not sure what to do with the log term. Should I ...
0
votes
2answers
26 views

Getting rid of $2^n$ when solving $a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ by characteristic roots

$a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ For $n\ge3$, With initial conditions $a_2=1$, $a_1=1$, and $a_0=1$ I'd like the find the particular solution with characteristic roots. However when generating ...
3
votes
1answer
24 views

Computational Theory: Proof, Chomsky normal form

Prove or disprove: If $G$ is a CFG in Chomsky normal form, then for any string $w \in L(G)$ of length $n\geq 1$ then exactly $2n-1$ steps are required for any derivation of $w$. I'm stuck at where to ...
0
votes
2answers
32 views

Help with Recurrence relations forward substitution and progression

I have seen a few questions regarding this topic. I have been unable to find one that could help me with analyzing the progression. My question :solve by recurrence relation using forward ...
3
votes
0answers
53 views

Complexity of finding set of sets with maximum cardinality and constrained coverage.

Given a set of sets $S = \{S_1, S_2, \dots, S_n$}, let $S^{'} \subset S$ be the largest subset of S that obeys $\left| \bigcup_{S_i \in S^{'}}{S_i} \right| \leq k$. What is the complexity of finding ...
0
votes
1answer
23 views

Context free language false proof

What is wrong with the following proof? Show whether $L$ is context-free or not, where $L = \left\{ a^nb^{2n}a^n | n \geq 0\right\}$ We know $\left\{a^nb^n | n \geq 0 \right\} $ and $\left\{b^na^n | ...
0
votes
1answer
14 views

Minimum sum of products expression from k map

I am just looking for confirmation that I have done this correctly. Here is the truth table. and here is the answer that I got.
0
votes
0answers
16 views

Proof for Kolmogorov complexity is uncomputable using Turing reductions

I am looking for a proof that Kolmogorov complexity is uncomputable using a reduction from another uncomputable problem. The common proof is a formalization of Berry's paradox rather than a reduction, ...
2
votes
1answer
57 views

The output spanning tree of Kruskal's algorithm is a minimum spanning tree

I want to show that the output spanning tree $S$ of Kruskal's algorithm is a minimum spanning tree, so it is of minimum weight, by contradiction. We suppose that $S$ is not a minimum spanning tree. ...
1
vote
0answers
20 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...
0
votes
1answer
20 views

What is $h^{-1}(L)$, for $L$ a regular language and $h$ a homomorphism?

Let $L = L((00 + 1)∗)$ and $h : \{a, b\}^* \to \{0, 1\}^*$ be defined by $h(a) = 01$ and $h(b) = 10$. What is $h^{−1}(L)$? In this context "$+$" means "$\cup$". So the language $L$ is all the ...
2
votes
1answer
74 views

The output of Kruskal's algorithm is a spanning tree

I want to show that the output of Kruskal's algorithm is a spanning tree. Let $G$ be a connected, weighted graph and let $S$ be the subgraph of $G$ which is the output of the algorithm. $S$ cannot ...
2
votes
2answers
80 views

How to find a function that is the upper bound of this sum?

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$ A. Express ...
5
votes
1answer
86 views

Is there an algorithm that probably solves the Halting problem?

Such an algorithm takes as input any program and returns a probability that it halts. In the limit of many programs, it must answer on average in the correct proportion. But im interested in other ...
2
votes
1answer
42 views

How to show that recurrence $T(n) \in \Omega(n^{0.5})$ using proof by induction?

This is recurrence $T(n)$ $ T(n) = \begin{cases} c, & \text{if $n$ is 1} \\ 2T(\lfloor(n/4)\rfloor) + 16, & \text{if $n$ is > 1} \end{cases}$ This is my attempt to show that $T(n) \in ...
0
votes
2answers
25 views

Does this recurrence relation run in $ \Theta(n) $?

This is the recurrence relation I am trying to solve: \begin{align} T(n) & = 2 \cdot T \left( \frac{n}{4} \right) + 16, \\ T(1) & = c. \end{align} I broke this down (i.e., solved this ...
4
votes
1answer
134 views

The graph has an Euler tour iff in-degree($v$)=out-degree($v$)

I am looking at the proof that $G$ has an Euler tour iff in-degree($v$)=out-degree($v$), that I found at this site: www.cs.duke.edu/courses/fall09/cps230/hws/hw3/headsol.pdf (Problem 2) A simple ...
2
votes
1answer
54 views

Prove that sets don't intersect

I am trying to solve a computer algorithm problem that boils down to solving the following. I would appreciate some mathematician assistance on the proof. So here goes: Having: Set $S$ - rational ...
0
votes
1answer
41 views

Solving Recurrence Relations with Geometric Series

If given the following problem... $$4T \left(\frac n2\right) + c$$ after getting the pattern down you see the following $$4^k T\left(\frac {n}{2^k}\right) + 3^{k-1}c + 3^{k-2} c + \cdots + 3c + c$$ ...
0
votes
0answers
14 views

Questions regarding notation (multiple variables, rounding)

I am calculating the coordinates of the Center of Gravity for a 3D volume using the following pseudocode (where A denotes the dimension length and cogA denotes the COG for that dimension) ...
2
votes
1answer
98 views

Given the graph below, use Dijkstra’s algorithm to find the shortest path (More details included)

So I've found out a few things and was wondering if someone could verify if I'm doing this correctly. So here is an example I've been given: Here is the solution to that example: Now here is the ...
2
votes
0answers
81 views

Tree decomposition by hand for understanding

I am implementing "algorithm 2" from the paper "Treewidth computations I. Upper bounds" by Bodlander and Koster[1,page5] and I am not sure if I understand it or not. As I understand, the algoritm ...
2
votes
0answers
14 views

Determining the sequence that yields a balanced search tree in the form of a recurrence / sequence

Let's say I have a sequence of (distinct) monotonically increasing numbers S. I'll want to add them sequentially to a Binary Search Tree (BST) but as the numbers ...
0
votes
1answer
21 views

Prove a language isn't regular using Myhill-Nerode thm.

Let $L$, a language above $\Sigma = \{x,y, (,),+,* \}$. $L$ can be defined recursively as follows: Basis Clause: $x$ and $y$ are in $L$. Inductive Clause: If $\alpha$ and $\beta$ are in $L$, then ...
1
vote
2answers
25 views

Computability: is there an alternative method to decide this language?

For my computability revision I am trying to decide the language, $$L = \{ \text{all binary strings containing the pattern 001 (not necessarily in consecutive places)} \}.$$ I believe that I can do ...
1
vote
0answers
51 views

Construct Context Free Grammar for $\{0,1\}^*-\{www~|~w\in\{0,1\}^*\}$

I'm working on the exercises in "Problem Solving in Automata, Languages, and Complexity" and I've run into the below problem. The question asks to construct a CFG for the language , and I just can't ...
0
votes
0answers
19 views

Time complexity of a recursive function on a given set

I am computing a function $fun$ which is defined as follows. $fun(m,s)=\sum_{\sigma_{p}\subset s;|\sigma_p|=m}\left [\prod_{i}i\in \sigma_p \sum_{j=1}^{|s-\sigma_p|}\sum_{\gamma_p\subset ...
0
votes
2answers
29 views

Why can any values of C and N be chosen for the proof of Big-Oh?

In my CS course, they have taught us that, when proving Big-Oh, you can choose any positive integers to be C and k, following the definition. Based on that, they have taught us two different ways of ...
1
vote
2answers
57 views

Given a complete graph of n vertices Kn (has all possible edges – one edge between pair of vertices).

Given a complete graph of n vertices $K_n$ (has all possible edges – one edge between pair of vertices). Use counting to find a formula in $n$ for the number of edges in the graph. I know that the ...
1
vote
0answers
17 views

A doubly infinite tape Turing machine can simulate a ordinary Turing machine, a rigorous proof.

Let $M$ be a ordinary Turing machine. Intuitively, we can say that $M$ can be transformed to a machine $M_D$ with doubly infinite tape, by placing to the left on every input $w = w_1, \dots , w_n$ ...
0
votes
0answers
22 views

(a) Given the graph below, for each pair of vertices given in (i) and (ii) gi

so I think I've figured out part a) but I'm not sure.. my solution is: a) part i) $v_1 \rightarrow v_3 \rightarrow v_7 \rightarrow v_5 \rightarrow v_8 \rightarrow v_4 \rightarrow v_2 \rightarrow ...
1
vote
1answer
31 views

Graphing digraphs with the following vertex set

Just want to make sure I did this correctly.. I think I did part a) correctly? Here is my solution for part a) Not sure how to do b) and c) though. Any advice would be great. Thanks in advance
1
vote
1answer
32 views

Is $L = \{0^{i}1^{i}0^{j}1^{i} | i, j > 0\}$ a context free language?

Is the following argument correct? $L = (A \circ B) \cap C$ where, $A = \{0^{i}1^{i}$ $|$ $i > 0\}$ $B = \{0^{j}1^{i}$ $|$ $i, j > 0\}$ $C = \{0^{i}1^{j}0^{k}1^{i}$ $|$ $i, j, k > 0\}$ We ...
0
votes
1answer
29 views

Elaboration needed on a section of a published paper about dictionary learning

I will be doing my master thesis on dictionary learning, and I am trying to understand basic concepts of the subject reading the following paper: K-SVD: An Algorithm for Designing Overcomplete ...
5
votes
0answers
57 views

Where can I learn more about the “else” operation / “else monoid”?

(The set of natural numbers $\mathbb{N}$ starts at $0$ for me.) Let $X$ denote a set, and define $X_\bot = X \uplus \{\bot\}.$ Let $\mathbf{else}$ denote the binary operation on $X_\bot$ defined as ...
1
vote
1answer
28 views

Representing Several IF statements inside a FOR loop in Math Notation

I wish to correctly represent several IF statements within a for loop in math notation. The FOR loop can be represented as: ...
0
votes
2answers
58 views

P vs NP and Countable vs Uncountable Decision Space

I have noticed that whenever the scope of a problem is pushed to infinity, problems in NP have an uncountably infinite decision space whereas problems in P seem to have a countably infinite decision ...
1
vote
1answer
47 views

Formal language: Proving the reverse operation on a word through induction

I'm practicing proofs and given the following statement: Let $\Sigma$ be an alphabet, $\epsilon$ the empty word and $\sigma:\Sigma^{*}\rightarrow\Sigma^{*}$ an operation which for $a\in\Sigma$ and ...
2
votes
0answers
21 views

Optimality of lower bounds for Max-cut on specific graphs

The Max-Cut problem asks to find a subset $S$ of the vertices of a graph (with $m$ edges) such that the number of edges from $S$ to it's complement is as large as possible. The size $|M|$ of a max cut ...
1
vote
1answer
30 views

validity of isbns in catching jump transposition errors

Does the isbn detect jump transpositions? $$a_1+2a_2+3a_3+\cdots+10a_{10}=0\pmod{11}$$ I think it does because the specific formula multiplying 1 times 1st digit, 2 times 2nd digit... will give you ...
1
vote
1answer
51 views

Finding the time for an epidemic/computer virus to infect a population

Question: "Suppose a computer worm makes 2 copies of itself on another computer in one millisecond. Estimate the time that is needed to spread to a population of 1,000,000 computers" How would I ...
0
votes
1answer
30 views

Finding error control capability of Hamming distance

I have known how to calculate the Hamming distance between two message codes. But I don't know how to get the error control capability. In one case I have hamming distance of: $$ d = 8 $$ Errors ...