Tagged Questions

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
0answers
22 views

Computing composite functions

This may not be strictly a math question but is related. Whenever there is some function that computes more than two elements, is it possible that all elements are computed at once? Or is computing ...
0
votes
2answers
156 views

the strings of five decimal digitis

My question is : Consider strings of five decimal digits, such as 00147, or 99999. In each case below, what is the number of such strings satisfying the given property? (a) The string has no repeated ...
1
vote
1answer
37 views

Regular language that has a string that cannot be pumped.

This is a question from a past exam. Consider the language $F = \{w | w \in 0^{*}1^{*}\}$ that is kown to be regular. a) Show that if string $w$ is chosen to be $0^p1^p$, that is a member ...
0
votes
2answers
151 views

Invertible functions - proving that $g \circ f$ is invertible

If I were to suppose that $f : A \to B$ and $g : B \to C$ are functions which are both invertible, how would I go about proving that $g\circ f$ is invertible with $(g \circ f)^{-1} = f^{-1} \circ ...
0
votes
0answers
16 views

Big Oh proof. Need help finding c constant

Ok I have the equation . I have compared each term with 2^n and proved that 2^n is greater for some n_0. My problem is how do I gather the terms up and find the c? $ \sqrt[]{2}^{\log n} + \log^2 n + ...
1
vote
0answers
23 views

Nonregular languages that satisfy the pumping lemma at different strengths

There are three versions of the pumping lemma that I've seen, each one stronger than the last (as in it fails on some non-regular languages that pass the weaker ones) The three versions are as ...
2
votes
1answer
39 views

Converting to Chomsky Normal form- derivations

I'm attempting to convert the following grammar into Chomsky Normal Form: $$S \to a S b S \mid b S a S \mid ε$$ I'm confused because in every example I've seen the grammar has been broken up into ...
0
votes
1answer
41 views

Y-Axis units on FFT graph

A 50Hz sinusoid wave with a voltage range of +/-20V is sampled at 512Hz for 1 second. No bias or phase shift are present. The signal is run through an FFT. The result is one spike at 50Hz on the ...
0
votes
1answer
53 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
23 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
55 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
46 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 ...
5
votes
1answer
188 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
47 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
68 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
23 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
202 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
44 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
66 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
22 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
50 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
1answer
23 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
29 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
19 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
26 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
39 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
59 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
95 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
36 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?
2
votes
3answers
53 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
80 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 ...
1
vote
1answer
86 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 ...
1
vote
0answers
36 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
36 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
10 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
61 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
56 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
37 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
66 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
38 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
34 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
47 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
52 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 ...