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

Learning Booth's Algorithm, I Can't Find the Issue on Final Result

I am practicing using Booth's Algorithm to multiply a positive number and a negative number (specifically the problem is $-12 \times 4$). I have included my attempt, but I can't find the issue. If ...
0
votes
0answers
9 views

Musa-Okumoto Growth Model

Suppose I have data like this (day of test and defect(s) were found) Day | Defect(s) ...
0
votes
0answers
8 views

How do I input this Boolean Expression into a K map?

Determine the minimum SOP, sum of products expression using K-Map F(A,B,C,D,E) = (A’ + B + C’ + D + E’)(A’ + C’ + D + E )(A’ + C’ + E )AC’ Do i have to actually simplify it first by multiplying ...
1
vote
2answers
28 views

How to apply Master theorem to this relation?

This is the definition of master theorem I am using(from Master Theorem) I am trying to use that master theorem to find the tight bound for this relation $T(n) = 9T(\frac{n}{3}) + n^3*log_2(n)$ ...
-3
votes
0answers
48 views

What areas of mathematics are not related to computer science?

I'm taking a Bachelor's in Computer Science, and I love Mathematics, so I want to know what I'm missing out on!
0
votes
0answers
9 views

Torelli Shanks Algorithm - Repeated Squarring Method

This algorithm is using when you want to find a square root of a number in a given moduli. I can't see the idea behind this algorithm, so can someone explain it in a simple way?
1
vote
3answers
36 views

How to find the solution of $T(n,m) = T((n-1),m) + T(n,(m-1))$ in terms of big $O$ notation?

I would like to solve the recurrence $T(n,m) = T((n-1),m) + T(n,(m-1))$. I think the solution is $$O(2^{n+m})$$ because in every step you can reduce either $n$ or $m$ by one or not, but I can not ...
2
votes
1answer
19 views

Proving a language $L$ is in $\mathrm{co\text{-}NP}$ if $| L \cap \{0,1\}^n | \in \operatorname{poly}(n)$ for all $n$

Let $L \in NP$ such that $|L \cap \{0,1\}^n|=\operatorname{poly}(n)$ for all $n$. Prove that $L \in \mathrm{co\text{-}NP}$. If I understand the problem correctly, in words this says that "for any ...
1
vote
1answer
16 views

How to simplify Boolean Expression b+ (a &(~ c))

I trying to figure out how (notB) + (notC)(B+A) simplifies to (NOTC) + (NOTB). original expression: ~b+ ~C(B+A) Reduced expression : ~C + ~ B
3
votes
2answers
54 views

What is a good book for reviewing high school math, and preparing for university?

I'm signing up for University soon (Compsci program) as a mature student. It's been a long time since I've done any math, and I went as far as grade 11 in high school. So, I'm looking for a book that ...
1
vote
0answers
20 views

Can boosting be thought of as a genetic algorithm? [migrated]

Can boosting be classified as a genetic algorithm or as an instance of simulated annealing? Or, is it a completely different paradigm? Essentially, I'm trying to rectify discrete optimization ...
1
vote
0answers
15 views

Changed matrix dimensions - now formula doesnt work. Related to computer science

I'm writing a computer code to solve a problem, and I ran into some difficulties. This is not a coding question, my problem is purely mathematical, I will explain. We have a matrix $M\in Mat(\mathbb ...
1
vote
1answer
20 views

Entropy Calculation and derivation of logarithm

I have probabilities as $$p_1 = 0.4,\ p_2 = 0.3,\ p_3=0.2,\ p_4=0.1$$ hence entropy is given by: $$H(x) = -\big(0.4\cdot \log_2(0.4) + 0.3\cdot \log_2(0.3) + 0.2\cdot \log_2(0.2) + 0.1\cdot ...
0
votes
1answer
17 views

NDFSM Transition State Network

My coursework question asks me to "Draw a State Transition for the nondeterministic finite state machine (NDFSM)" from a state transition table. By following the examples in our lecture materials, ...
4
votes
1answer
46 views

Why do we divide or multiply by 2 when converting binary?

Trying to understand the fundamentals of binary rather than just following steps, I wanted to know why do we multiply by 2 to convert a decimal (0.5, 0.25) to a binary and why do we divide by 2 when ...
0
votes
1answer
14 views

Context Free Grammer (CFG) for a language

Consider the language above $\Sigma = \{a,b,\$\}$: $$L = \left\{ x$y : x,y\in\{a,b\}^* \land \left|x\right| \ne \left|y\right| \right\}$$ I need define a CFG for this language. I've tried couple of ...
1
vote
1answer
28 views

Language of grammar 4 tuple

A grammar $G$ is a 4-tuple $G=G(V,T,P,Z)$, where $V$ is an alphabet $T$ is an alphabet of terminal symbols $P$ is a finite set of rewriting rules, $Z$, the distinguished symbol, is a member of ...
0
votes
0answers
29 views

What is an example of an NL-complete context free language? [on hold]

Setting Exactly as the title stated: please give an example of an NL-complete context free language? Current Solution Recall in the past we proved that $E_{DFA}$ is regular, so it is also context ...
-1
votes
1answer
22 views

4 - Tuple Grammar [on hold]

A grammar $G$ is a $4$-tuple $G=G(V,T,P,Z)$, where $V$ is an alphabet $T$ is an alphabet of terminal symbols $P$ is a finite set of rewriting rules, and $Z$, the distinguished symbol, is a ...
0
votes
0answers
37 views

Which areas of computer science most directly influence mathematics? [on hold]

Instead of the usual "Which areas of math are most relevant to computer science?," I'm asking which areas of computer science are most directly related to math. The reason is that I want to do a PhD ...
1
vote
1answer
72 views

Inverting a map from a finite 3D grid to 1D

I need help with this mathematics question. I have made a program on the computer that flattens a 3D array into a 1D array. A 3D array needs an x, y and z but by using this formula (max x * max y * ...
1
vote
2answers
36 views

Quick solution check for the TSP

Given a solution for the Boolean satisfiability or the Hamilton cycle problem it's obvious whether it's true or not, but how does one quickly check whether a solution for the TSP (travelling salesman ...
1
vote
1answer
22 views

$2^n=na_n+na_{n-1}-a_{n-1}$ by range transformation

I want to range transform $2^n=na_n+na_{n-1}-a_{n-1}$ to get rid of the $2^n$ term and then solve it with any other method (seems like telescoping will work once it's reduced). I've tried ...
0
votes
0answers
12 views

Problem with DES Encryption

If the input string to a round of DES is 11001100 · · · 1100 = ‘1100 × 16′ and if the round key is 1111 . . . 111 (‘1 × 48′), Then how can I calculate the 20th and 33rd output bits ? This was an ...
0
votes
1answer
17 views

Proving $1+2CZ+3C^2Z^2+…=1/(1-CZ)^2$, considering $\sum\limits_{i=1}^{\infty}c^iZ^i=(1-CZ)(1+2CZ+3C^2Z^2+…)$

I'm told that we can prove this common identity for solving generating functions: $1+2CZ+3C^2Z^2+....=1/(1-CZ)^2$ Using only the property ...
0
votes
0answers
33 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
34 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
19 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
28 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
28 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
32 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
21 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
17 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
24 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 ...
0
votes
0answers
21 views

ID3 algorithm and binary trees

You have a sample set of 8. You need to make a table such that if you run ID3 on it you get a binary tree with 5 leaf nodes. I'm stuck. I did lots of trial and error.
3
votes
0answers
49 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
21 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
8 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
12 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
31 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
15 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
53 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
60 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
77 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
35 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
21 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 ...