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.

learn more… | top users | synonyms

0
votes
1answer
52 views

How can I justify it formally?

Given the following algorithm: Function Fun(int n){ int j,k,t=1; for (j=0; j<=4n^2; j+=4){ for (k=j; k<=4*sqrt(n); k+=4){ t+=8; } } } I ...
1
vote
1answer
20 views

Why does the following formula cycle the bits by shifting the binary representation from left to right?

Intuitively, I was trying to come up with a formula that would cycle through the binary representation of numbers from left to right. Let our range of numbers goes from $0, .., N-1$ and let $m$ ...
2
votes
0answers
51 views

Algorithm to reduce expressions to canonical form

I'm writing a small computer algebra system that only knows rational numbers and all expressions that you can get from them by using basic arithmetic operations and powers. So the expressions are ...
0
votes
1answer
43 views

Disproving Big O Statements

Show that $2^{\sqrt{n}}$ is not $O(n^{10})$ from the definition of $O()$. I'm not sure on how to start this problem. From the definition, if we want to prove such an statement, then $\forall ...
4
votes
1answer
166 views

Graph Min Cut Problem

The idea is to give an Flow Network in which the minimum cut goes through a lot of edges. So adding one unit to each edge will change the min cut. The following figure, as a counter example, shows a ...
0
votes
0answers
27 views

Cantor or Szudzik pairing function corollary for real number

First of all, I'm sorry since I'm not mathematician, I'm just Computer Science student trying to apply pairing function into my algorithm. I have a two real values that I need to map into single real ...
1
vote
1answer
62 views

disprove $L = \{ a^nb^n\mid n \geq 0 \}$ is not a context-free using pumping lemma for CFL

I am writing something about pumping Lemma. I know that the language $L = \{ a^nb^n\mid n \geq 0 \}$ is context-free. But I don't understand how this language satisfies the conditions of pumping lemma ...
1
vote
1answer
21 views

correcting an invalid binary heap in $\Theta (n)$

We are given a binary max (every node is larger than its children) heap with $n$ elements. We now change $\frac{n}{4}$ of the elements at random. We don't know which ones and to which value. And so, ...
0
votes
2answers
80 views

Any power of logarithm is $O(N)$

This is more of a computer science question but it uses calculus and proof techniques so I think it might be more appropriate here. Basically, how do I prove that, for any constant $K \geq 1$, ...
0
votes
1answer
36 views

Big Omega Proof for $5^n = \Omega(6^n)$

I got the Big-O ($\mathcal{O}$) proof but I am having troubles with the Big Omega ($\Omega$) proof. I am trying to prove $6^n$ is not the tightest bound for $5^n$. Is this logic true: $7^n$, $8^n$ ...
0
votes
1answer
21 views

Geometric sum of recurrence relation

I am reading the textbook Algorithm Design by Kleignberg and Tardos and I am having trouble on page 216. $$T(n) \le \sum_{j=0}^{log_2n - 1} \left ( \frac{q}{2}\right )^j cn = cn \sum_{j=0}^{log_2n - ...
1
vote
3answers
199 views

Let X be a subset of {1,2,…,2014}…

Let X be a subset of {1,2,...,2014}. How would I show that if |X| ≥ 64, then there exist at least two different pairs {x,y} and {u,v} of distinct elements of X which |x-y|=|u-v|? I'm not too sure ...
5
votes
2answers
63 views

Recurrence Relation from Old Exam

I see this challenging recurrence relation that has a solution of $T^2(n)=\theta (n^2)$. anyone could solve it for me? how get it? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 ...
0
votes
1answer
39 views

How to know if a graph exists or not?

Draw the required graph or explain why no such graph exists: 8-vertex, 2 component, simple graph with exactly 10 edges and three cycles. I think there is a graph but I'm not sure. Can anyone help to ...
2
votes
1answer
63 views

Asymptotic Function proof?

I am doing questions from past exams and I stumbled upon this one. I have no idea how to go about solving it.I never had any logarithmic functions in my previous bigOh proofs nor have I had to use ...
0
votes
1answer
18 views

Proving the correctness of a program

So I have this program below SquareRootRecursion that I need to prove is correct. However i'm not sure what it's pre and post conditions would be and how I would use those to prove it's correctness. ...
2
votes
1answer
48 views

Given 2 colors, how to calculate the mix amount between them?

As an input I have two colors, let's say red (RGB = 1,0,0) and magenta (RGB = 1,0,1). Now I have an image which includes additive mixes between these two colors, for example purple (RGB = 0.5,0,1). ...
0
votes
0answers
19 views

Implement using switches the following logic functions

Implement using switches the following logic functions: F(a,b,c,d)= ab + cd F(a,b,c,d)=(a + bc)d' how can i do it ? Digital System
0
votes
1answer
20 views

Use the power-set construction to find a deterministic automata

Given a nondeterministc automata N, how do you use the power-set construction to find a deterministic automata that recognizes L(N)? Here is my work so far: We can start in state 1, 2. If we get ...
2
votes
0answers
28 views

Prove the big theta

I need to find a $n_0$ and $k$ for Big Oh and an $n_0$ and $k$ for Big Omega, to find a big theta bound for: $5n^2 - 9n = \theta(n^2)$ Can anyone help me and show me how to find these for this ...
0
votes
1answer
17 views

Comparing algorithmic complexities

If an algorithm has a running time $ T(n) = O(n$ log $n)$, would it be possible to show that $T(n) = o(n^2)$?
1
vote
1answer
24 views

Taking the log of both sides to determine big Theta/Omega/O

I've managed to confuse myself over this detail: Obviously: $n^2 \notin \Theta(n)$ Now if we take the $\log$ of both sides, we get: $$\log(n^2) \leq \log(cn)$$ $$2\log(n) \leq \log(c) + \log(n)$$ ...
0
votes
1answer
35 views

Structural Induction Subsets

Consider the set $S \subset \mathbb{N}^2$ of ordered pairs of integers defined by the following recursive definition: • $(3, 2) \in S$ (basis) • If $(x, y) \in S$, then $(3x − 2y, x) \in S$ ...
3
votes
2answers
57 views

Coloring Graph with some constarints

if Graph G be a Cycle with Length=4. how many ways we can color this graph with at most $\lambda$ different color, in such a way that non of two adjacent vertex has a same color?
5
votes
2answers
94 views

Nice Question in Mathmatics about Times

I ran into a nice question from one book in Discrete Mathematics. I want to someone lean me how solve such a problem, because I prepare for entrance exam. if the time is "Wednesday 4 ...
0
votes
1answer
31 views

Calculating the average degree/valency of vertices

If I were to let T be a tree with n vertices, what would be the average degree/valency of the vertices in T? How would I go about calculating this?
0
votes
0answers
22 views

Help with first principle proof

I am stuck on this proof. I just do these for fun. $n^n \in \omega(n^{20})$ I am stuck on this one. not sure how to show this is bound in little omega.
0
votes
0answers
32 views

Prove or Disprove Asymptotic Complexity

Not sure how to prove or disprove this. $$\min\{f(n), g(n)\} \in \Theta\left(\frac{f(n)g(n)}{f(n)+g(n)}\right)$$ Could someone please give me a hint on how to approach this?
1
vote
3answers
51 views

How many numbers can a typical computer represent?

I couldn't find this elsewhere so I thought I'd give it a try to figure out exactly how many numbers a typical desktop computer can represent in memory. I'm thinking about this in the context of ...
1
vote
0answers
34 views

Inference using Proof by contradiction and resolution rule [duplicate]

I get stuck in inference. please help me in step by step inference? By using Resolution Rules, and Proof by contradiction from following Knowledge base, we want to understand how we get the answer of ...
-1
votes
1answer
74 views

Finding a minimum weight spanning tree? [duplicate]

Letting W be the weighted graph created by taking a complete graph K5 on five vertices 1, 2, 3, 4, 5 with the weight of each edge {x,y} given by ({x,y})=x+y, How would I find a minimum weight ...
0
votes
0answers
9 views

Use structural induction to prove the following binary tree

Recursive def for Set $X$ (there are two): (1)a single node is in $ X$ and (2) if $x_1$ and $x_2$ are in $X$, then the bigger tree with root r connected to the roots of $x_1$ and $x_2$ is in $X$ use ...
0
votes
0answers
63 views

When to use weak, strong, or structural induction?

For weak induction, we are wanting to show that a discrete parameter n holds for some property P such that P(n) implies P(n+1). For strong induction, we are wanting to show that a discrete parameter ...
0
votes
0answers
23 views

Help Representing Python Algorithm Mathematically

For a project I am doing (using rhythm comparisons as an alternative to password authentication), I created an algorithm called "MalKonform", which compares keystroke times between two instances. ...
1
vote
0answers
35 views

Constructing a “one-way function” of two variables (a.k.a “stop my friend from hacking my game”)

This might be more of a computer science question than a mathematics one; I thought I'd start here but perhaps people might want to point me to a better forum, if this isn't the right one. ...
0
votes
2answers
35 views

In general, what does the location of the rightmost “1” in a binary number tell you? Is it different for positive and for negative numbers?

In general, what does the location of the rightmost “1” in a binary number tell you? Is it different for positive and for negative numbers?
1
vote
0answers
21 views

Shortest route with a requirements set

Suppose you have a weighted connected graph, $G(V, E)$, with $n$ nodes such that every node has a edge to every other node (a large clique). You are also given a set of sets, $\{l_1, l_2, ... l_n\}$ ...
0
votes
0answers
9 views

Is the set $L =\{ M_ i: M_i$ accepts only one string$\}_{i=1}$ an recursive enumarable set?

I am having trouble with this question "Is the set L = {i such that M_ i accepts only one string} an recursive enumarable set ?" My answear is "No, because we can reduce this set to The K set K={i ...
0
votes
1answer
60 views

How would I find a minimum weight spanning tree for W?

If I were to let $W$ be the weighted graph formed by taking a complete graph $K_5$ on five vertices 1, 2, 3, 4, 5 with the weight of each edge $\{x,y\}$ given by $(\{x,y\}) = x + y$, how would I find ...
1
vote
1answer
46 views

Calculating MIPS [closed]

Been struggling to solve this question. From my notes, you can calculate MIPS through this formula: MIPS = Instruction Count / Execution Time X 10^6 And the question goes like this: Given an ...
0
votes
1answer
36 views

How many bits are needed to encode the following data?

A weather station on Santa Rosa Island sends data about weather conditions once every 15 minutes. The data sent is as follows: Temperature (0..60 degrees Celsius) Wind speed (0..170 kph) Wind ...
1
vote
1answer
42 views

Proof of big-O notation

Prove the following: If f is a polynomial of degree $d$, then $f(n)=O(n^{d})$. For every $d \in N, n^{d} = O(e^{n})$ Intuitively, it makes sense to me that for the first one, growth order depends ...
1
vote
1answer
36 views

What's the parametric equation for the general form of an ellipse rotated by any amount? Thanks.

What's the parametric equation for the general form of an ellipse rotated by any amount? Preferably, as a computer scientist, how can this equation be derived from the three variables: coordinate of ...
0
votes
1answer
30 views

What mathematical structure best entails self-modifying programs?

If a program description can be represented as a sequence, then what is the best structure to entail program descriptions which self-modify? There must exist a relationship between the structure in ...
1
vote
1answer
46 views

Prove using structural induction?

First off: I am not sure if I have posted to the correct site, but I am quite lost with this question. I am in a theory of computation class after taking 1.5 years off school and we are on ...
0
votes
0answers
49 views

Proving that there always exists two opposite points on a circle where the temperature difference is less than 1

You are given $n$ ($n$ is even) integers $a_0,a_1,\ldots,a_{n-1}$ representing temperature measurements, equally spaced around a circle. Since the points are "close", the temperature difference ...
1
vote
1answer
28 views

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable. (This is the same as the problem of detecting unreachable code in a program.)
2
votes
1answer
33 views

Expected Value on code

I'm trying to figure out the expected number of times this algorithm will print. I'm stuck on how to go about doing so. I used an indicator variable to keep track of the number of print statements ...
0
votes
1answer
15 views

In the loop average computation

I want to compute the average of a set of number, which is constantly increasing. I guess it's simple, but I'm struggling here: Let's say: 1st iteration: m(i)=a+b/2 2nd iteration: m(i+1)=a+b+c/3 ...
0
votes
1answer
39 views

Trouble reading mathematical statements. Need to know I'm on the right track.

Σ = {a, b}. We write #a(x) for the number of occurrences of the letter a in the word x and similarly for #b. note: $\Sigma^*$ refers to the set of all finite strings (words) over Σ. ...