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

1
vote
0answers
100 views

Is there a proof that Encrypting and then Decrypting any data using AES 256 will result in the same data?

I use AES quite often at work (I'm a software programmer) and I trust that it "works" without understanding the maths behind it. It's a black box to me. Does a mathematical proof exist that AES 256 ...
0
votes
1answer
174 views

Public and private RSA keys, using the primes $p = 5$ and $q = 11$

Assume that $p = 5$ and $q = 11$, and all other variables are defined as per the RSA theorem (a) Suppose we consider $e = 3$. Would $(e, n)$ be a suitable public key? (b) Prove that if $d = 27$, ...
1
vote
1answer
130 views

How can I encode this?

Let say I have 7 integers: 1, 2, 3, 4, 5, 6, 7. Among the 7 integers, I choose 3 integers. For example, my choice is (1,2,3). Note1: The order of the integers in the choice doesn't matter. This means ...
0
votes
1answer
63 views

beta reduction bascis

Hi I get the basics of beta reduction e.g. $$(\lambda var.body)arg $$ you just replace the occurrences of var with arg in body. However what happens here? $$(\lambda x.xx)(\lambda x.xx) ...
1
vote
0answers
64 views

Showing particular language is NP-complete

How is FLO NP-complete? Let G be a social network where vertices correspond to people and edges are relationships between people (undirected). Some pairs of people (who are friends) get married. We ...
7
votes
0answers
218 views

Homomorphic Compression

Can there be an algorithm such that, given plaintext data P,Q, and compression function e, Such that if we treat P and Q as a number (a series of bits): $$\begin{eqnarray*}e(P + Q)& =& e(P) ...
1
vote
1answer
64 views

Amortized analysis and the potential method

To my understanding to use the potential method to get the amortized cost of an operation the following conditions need to be satisfied: $\Phi (D_{0}) = 0$ $\Phi (D_{i}) \geq 0$ for all $i \geq 0$ ...
1
vote
2answers
127 views

Books about Turing machines and undecidability

I need help with finding literature about Turing machine and undecidability. First book I was suggested is Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani and Ullman. ...
2
votes
4answers
145 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
2
votes
2answers
140 views

How to efficiently encode this?

I have 5 ring oscillators whose frequencies are f1, f2, ..., f5. Each ring oscillator (RO) has 5 inverters. For each RO, I just randomly pick 3 inverters out of 5 inverters. For example, in RO1, I ...
0
votes
2answers
59 views

Representing everywhere a camera can see as a matrix

I'm learning about Computer Graphics and there is one point really puzzling me. I understand that vertices (vectors) represent points in space and that transformation matrices represent changes that ...
0
votes
1answer
57 views

Prove that if $x$ is a real number, and $x-\lfloor x\rfloor \ge 1/2$, then $\lfloor 2x\rfloor=2\lfloor x\rfloor +1$

Prove that if $x$ is a real number, and $x-\lfloor x\rfloor \ge \frac{1}{2}$, then $\lfloor 2x\rfloor=2\lfloor x\rfloor +1$ I'm so confused because i don't completely understand the rules for floor ...
2
votes
2answers
74 views

Prove that $6^{\sqrt n} = O({n \choose n/2})$

Prove that $6^{\sqrt n} = O({n \choose n/2})$ I was able to show that prove that $6^{\sqrt n} = O({n \choose n/2})$ with defining $ n=2k$ and $ a_k= \frac {k!^26^\sqrt k} {2k!} $ and then show ...
1
vote
1answer
55 views

prove\disprove - there are functions $f(n)$ and $g(n)$ such that $g(n) = o(1)$ and $f(n-g(n)) \neq \Theta((f(n))$

there are functions $f(n)$ and $g(n)$ such that $g(n) = o(1)$ and $f(n-g(n)) \neq \Theta((f(n))$ Thought about $f(n) = |sin(n)|,\ g(n)= \frac1n$ then $f(n-g(n))= |sin(n-\frac1n)|$ and then for any ...
2
votes
0answers
73 views

Number of orderings of subset sums

In short: In how many ways can all $2^n$ subset sums of $n$ real numbers $a_1,\ldots, a_n$ be ordered? I am not concerned about the case in which different subsets sum to the same number; you may ...
1
vote
1answer
146 views

Solve linear programming given access to an oracle

This question is about designing a polynomial time algorithm for linear programming given access to an oracle outputs YES if and only if $\{\vec{x}\ |\ A\vec{x} = \vec{b}, \vec{x}\geqslant ...
1
vote
2answers
690 views

Calculate a total percentage based on individual percentages but without original values.

(I hope the question/title made sense.) Let's say I have the following list: ...
0
votes
0answers
72 views

Data structure with quick insert and search

I have a problem I'd like to code. I have a process which generates numbers 0 through n-1 and I want to stop it when it generates the first repeated element.* I'm looking for a data structure that ...
0
votes
1answer
47 views

Writing a recurrence in terms of a shift operator

This is a concept that I vaguely understand, but I'd like to get an intuitive understanding of how to write a recurrence relation of the form: $$ t_{n}-3t_{n-1}+2t_{n-2}=0 $$ subject to $$ t_0=2, ...
1
vote
1answer
716 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 ...
3
votes
1answer
71 views

How does the math in the RSA trapdoor work?

You have the candidate one-way function $$f_{n,e}(x) = x^e \mod n,$$ where $n = pq$ with $p,q$ primes with $|p| = |q|$ (same bit length) and $\gcd(e, (p-1)(q-1)) = 1$. Then the trapdoor, that is, ...
5
votes
1answer
174 views

Smallest Number of Strings to Distinguish $n$ Pairwise $L$-distinguishable Strings

This is an exercise from Introduction to Languages and the Theory of Computation, by John Martin. Suppose $L$ is a language over $\Sigma$, and $x_1, x_2, ... , x_n$ are strings that are pairwise ...
0
votes
1answer
98 views

Are these equivalent representations (labelled graph and adjacency matrix)?

This is an example from Wikipedia's page on adjacency matrices, which from the site's format seems to be suggesting equivalence between the simple diagram below, left, and the abstractly represented ...
1
vote
0answers
53 views

What areas of mathematics are taught in a Computer Engineering course?

I'm planning on taking a Computer Engineering course next year, I study hard when it comes to math so I wanna know what area of mathematics I'm going to tackle during my course so I can study it ...
0
votes
1answer
562 views

What can be defined as a Regular Set

I'm currently studying compilers and am having some issues with understanding regular sets. For example, lets say I had a set of binary strings, (0, 1). Would all integers that are even and positive ...
2
votes
1answer
222 views

If P = NP, then 3-SAT can be solved in P

Prove that if $P = NP$, then there is an algorithm that can find a boolean assignment for a 3-SAT problem in P time if it exists. $P = NP$ only says that we can decide whether a 3-SAT problem is ...
0
votes
1answer
42 views

Prove a language is NP-Complete

$A$ is NP-complete. $B$ is P. $A \cap B = \emptyset $ $A \cup B \neq \sum^{*}$ Prove that $A \cup B $ is NP-complete. How can I prove this ? I think if anything can be P-reducible to A then it ...
1
vote
1answer
50 views

Proof that $n^2 \not\in \omega(2^n)$

I'm trying to prove that $n^2 \not\in \omega(2^n)$ and I have to do it from definition. $f(n) \in \omega(g(n)) = \left\{f(n)| \forall c>0, c \in \mathbb{R}, \exists n_0 \in \mathbb{N}, \forall n ...
1
vote
1answer
46 views

One-way functions and pseudorandom number generator

Is it true that if there is Cryptographically secure pseudorandom number generator then there is One-way function?
1
vote
0answers
29 views

Nonlinear optimization using parallel input/output

I have a system that accepts a vector and returns a function value. The goal is to change the elements of the vector such that the function value is minimized using a derivative-free solver, eg. using ...
0
votes
1answer
130 views

What does it mean to be an “instance of a rewriting rule”?

What is the definition of the following statement? The rewriting rule $l_{1}\rightarrow r_{1}$ is an instance of another rule $l_{2}\rightarrow r_{2}$. PS:This statement comes from the paper of ...
0
votes
1answer
230 views

How can I tell/compare the asymptotic complexity of a function?

For something, like a quadratic I just take the highest degree and see if it is theta or big O or Omega of n, correct? So like 2n^2+2n+1 could be theta(n^2). What are the general ...
0
votes
1answer
411 views

Show that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Let Σ = {0, 1}. Let L = {ww|w ∈ Σ*} I am not sure where ...
4
votes
2answers
1k views

Learning Proofs (for Computer Science)

Harvard's math curriculum, for freshmen, is divided into 4 classes beyond the BC Calculus level, Math 21, 23, 25 and 55. Math 21 is your classic plug-and-chug multivariable calculus and linear algebra ...
0
votes
1answer
64 views

$a + b = a$ in machine precision [closed]

I have the following statement: "If $a + b = a$, then $b = 0$" may not true with the floating point operations. Actually, if $|y| ‎< (\varepsilon / B) |x|$, then $fl(x+y) = x$, where ...
1
vote
0answers
117 views

On hamming hypercubes

Regularly in a Hamming hypercube, the vertices are labelled so that edge difference (minimum number of edges traversed between two vertices) equals Hamming distance (path difference). That is lower ...
0
votes
2answers
2k views

Proving a connected graph is a tree if the DFS and BFS traversals from the same node are equivalent

Let $G$ be a connected graph and $v$ be a vertex in $G$. Suppose a DFS traversal from $u$ is performed resulting in a tree $T$, and a BFS from $u$ also results in the same tree $T$. I would like to ...
0
votes
1answer
88 views

Recursively enumerable language of Turing machines

If you have the language $L_{h}=\{M_{i} | (\exists z \in \sum ^{*}) M_{i}\text{ halts on some input } z\}$ where $M_{i}$ are Turing machines, is $L_{h}$ recursively enumerable? I'm fairly certain ...
4
votes
0answers
475 views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
5
votes
0answers
158 views

How to list the prime factorised natural numbers?

Today I set out to invent a two character numeral system designed to make factorization trivial. Indeed, it lets one factor non-trivial numbers with over thousand digits within 30 seconds per hand - ...
1
vote
1answer
121 views

Picking an appropriate “guess” for Heron's Method and The Fast Reciprocal Method

I've been thinking for a while about writing some code that would use Heron's Method and the Fast Reciprocal Method. Heron's Method This finds the approximation of $ \sqrt{S} $. The initial guess is ...
2
votes
1answer
170 views

Sort objects into groups based on group size preference

I have a research question that involves human subjects being sorted into groups before playing a social game. Before sorting, each person decides on their preferred group size, from 1 to n; where n ...
1
vote
1answer
82 views

Ackermann function and primitive recursiveness

If we define $b_n(m) := a(n,m)$ for all $n$ and $m \in \mathbb{N}$. For which $n$ is the function $b_n$ primitive recursive and for which $n$ it is not a primitive recursive function? Can anyone ...
1
vote
1answer
139 views

I'm a CS PhD student. I want to re-study some of college mathematics

I'm a PhD student in CS and I have a fair amount of background in mathematics. But it's been many years since I studied Mathematics in college. I would like to refresh and in many cases, understand ...
2
votes
1answer
60 views

Decidable language closed under complement

Why are decidable languages closed under complement? So if L is decidable why is the complement of L also decidable.
1
vote
1answer
76 views

Generating a context free grammar

How do I generate a context free grammar for a language $$\left\{a^ib^jc^k:i=j\text{ or }j=k,\text{ and }i,j,k\ge 0\right\}\;?$$ Thanks.
2
votes
2answers
220 views

$\beta$ - conversion and $\alpha$-reduction problem in $\lambda$-calculus

Here is an expression that I am trying to reduce and my operations so far: $$((\lambda x.(x (\lambda z.zy))) (\lambda z.\lambda y. zy) )= (x (\lambda z.zy))[x \to \lambda z.\lambda y. zy ] = ...
1
vote
3answers
140 views

how can we write abstract algorithms?

Writing pseudo-code for algorithms is common practice in the applied mathematics literature. It is also often the case that the ideal input of an algorithm is an infinite set, for example it could be ...
0
votes
1answer
86 views

Can a directed hamiltonian path be found in polynomial time?

I was discussing a programming competition problem with one of my math professors in Linear Algebra that reads as follows: A matrix is an $r\times c$ array of numbers, where $r$ is the number of ...
0
votes
1answer
125 views

How to approach this Secret Sharing scheme?

Suppose that I want to break up a secret into shares such that any set of k people can recover the secret, but I’m also worried that some people might be dishonest and may lie about the secrets they ...