Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computer-science]

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 ...

0
votes
1answer
17 views

Hoare Logic: Consequence Rule

I can substitute $R$ in the first tuple which gives me $x$ $>$ $2$, but I don't know what $S$ is. What is $S$ in this case and how do you arrive at $x$ $>$ $2$ $\rightarrow$ $x$ $>$ $0$?
-4
votes
0answers
12 views

Calculate Cycle per Instruction and MIPS [on hold]

Consider the execution of a program that results in the execution of 2 million instructions on a 500-MHz single processor. The program consists of four major types of instructions. The instruction mix ...
1
vote
0answers
25 views

Computing a Powerset that contains a set

I understand the concepts of power-sets pretty easily, and have done some substitution to make things easier, but I'm not sure of my answer. I have the set {{a,b},ε,x} I replaced {a,b} with c, so ...
0
votes
2answers
32 views

True or false: $n^2 + 2n^2 + 3n^2 + 4n^2 + … n(n^2)$ is $O(n^2)$

I believe it is false, but having trouble coming up with the contradiction. My solution so far: Suppose by contradiction $n^2 + 2n^2 + 3n^2 + 4n^2 + ... n(n^2)$ is $O(n^2)$, then there exists c > 0 ...
1
vote
1answer
36 views

True or False: $(n + \log(n))(n+8)$ is $O(n)$

Just wondering if I can get some feedback regarding this proof, and whether or not there is a way to do it without limits. My Solution: $(n + \log(n))(n+8)$ is not $O(n)$ Suppose by contradiction ...
0
votes
0answers
5 views

Two dimentional discrete Fourier Transform, dimentions when performing convolution

I have trouble wrapping my head around the way 2d convoluion with fft is performed. I understand how 2d convolution works when performed clasically (technically I'm interested in cross-correlation as ...
2
votes
0answers
145 views

What does the category of RDF models look like in Institution Theory? [on hold]

The Question in short Here is the question in its pure form. Details of my reasoning can be found below. The RDF1.1 spec semantics defines a model to consist of a set IR of objects and IP of ...
0
votes
2answers
53 views

When we understand $\mathbb{Z}_{4}$ as $\{-2, -1, 0, 1\}$ rather than $\{0, 1, 2 ,3\}$, is it same as 2's complement?

Suppose we have an integer ring $\mathbb{Z}_4$. When we understand $\mathbb{Z}_{4}$ as $\{-2, -1, 0, 1\}$ rather than $\{0, 1, 2 ,3\}$, is it same as 2's complement using 2 bit?
1
vote
1answer
35 views

Can you use set builder notation to imply a function with arguments?

So I'm writing a paper (computer sciences) that involves moore neighbourhoods. If I am using set builder notation to define a set, can I use index form for example to either index elements of the set ...
-4
votes
0answers
18 views

can you help me simplify this logic problem? [on hold]

could you help me with this discrete math problem that is logic related? simplify the following, using laws and expressions such as absorption,... ( p V q) <-> ( p -> q)
1
vote
1answer
34 views

Sum of bitwise OR of all possible subarrays [closed]

I came across this question on a programming contest although I was not able to solve it. The editorial was released later but it was super unhelpful, so I am asking it here. You are given an array, ...
0
votes
0answers
17 views

Optimal Polygon Placement on a Grid

I am looking for an algorithm(s?) that basing on the parameters like: cell size and grid type(rectangular, hex, triangular) places the given polygon so that the number of cells covering the polygon ...
0
votes
0answers
10 views

Fourier harmonics [closed]

How to create formula in MsExcel file (or another approach) to construct harmony by harmony according to given set of bits (byte)? In general I need to create this for 8bit set (e.g. 01010101). I ...
1
vote
1answer
53 views

How to find a simple function in Lambda Calculus?

I was doing this exercise : Find the function $$exchange$$ such that: $$(exchange)t \simeq \lambda p(p)t_2 t_1$$ where $$t= \lambda p(p)t_1 t_2.$$ I found $$ exchange= \lambda p(p) (\lambda c (S \ \...
4
votes
1answer
86 views

Is it possible to construct primes with arbitrary messages in them?

Motivation: A friend of mine told me that the number gained by interpreting the binary code of is quite often a prime. A slight copyright themed discussion later and after developing an algorithm to ...
1
vote
0answers
19 views

Asymptotic Growth: Understanding proof of $f(n) + o(f(n)) = \theta (f(n))$?

I'm working through proof of $f(n) + o(f(n)) = \theta (f(n))$ and I came across a part in the proof that I am having trouble understanding. We let $f(n)$ and $g(n)$ be asymptotically positive ...
0
votes
1answer
25 views

Recurrence Relation, Compound Annually

If I invest $\$2000$/yr in a tax sheltered annuity at $7\%$, where $A_n$ is the amount at $n$ years... what is the recurrence relation? I know my initial condition $A_0$ is $2000$. And for some reason ...
0
votes
2answers
35 views

How to prove P $\subseteq$ NP without machines?

I am trying to understand why P is considered a subset of NP. I don't know the definition of Turing machines yet. Is there a simple way to see why this is true? I have seen some people saying that if ...
0
votes
0answers
24 views

Prove that a BST for a limited set of contiguous elements [1, n] has at most n leaves

I define a Binary Search Tree as a tree in which the key in any node is larger or equal than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's ...
0
votes
0answers
15 views

CRC-1 is actually adding a parity bit

I'm trying to understand the claim that CRC-1 is practiallcay attaching a parity bit to data (where the generating polynomial is $x+1$) It has something to do with the fact that when you multiply a ...
1
vote
0answers
45 views

Maximising the distance between $n$ points in a 2d region

I've been looking into the problem of computing the problem of placing $n$ points on a finite rectangular region of size $w \times h$ in a 2d plane so as to minimise the function $\sum_{i,j} \frac{1}{...
0
votes
0answers
21 views

How to determine number of states in a transition system?

I am trying to model the sequential circuit in the picture on the left (C1) as a transition system but cannot figure out the states. I have tried my hand at interpreting this from Principles of Model ...
0
votes
0answers
34 views

Halting behavior of optimal algorithms on getting enough input

Per the advice in this comment, I am submitting this redraft of this question as a new question. This new question not only incorporates the five edits of the original question but also incorporates ...
0
votes
0answers
30 views

Number of football fans in a town Coursera question, why will it terminate?

I've come to a problem while doing the Mathematical thinking Course on Coursera. The problem statement is: There are two football teams in a town. Each of the citizens is supporting one of the teams....
3
votes
1answer
102 views

Properly stating a decision problem for a Hamiltonian cycle problem

I'm running an algorithms seminar and I'm trying to express the Hamiltonian cycle problem in a new way that is exciting to students. I know that many of them play a game called Hearthstone and I'm ...
5
votes
1answer
178 views

History and connecting math to real world

I am software developer with big interest in Mathematics and especially discrete mathematics (which is foundational for computer science). I am currently reading Discrete Mathematics and Its ...
0
votes
0answers
26 views

What knowledge is needed for developing a Music Processing Application like Audacity?

What knowledge is needed if I want to develop a Music Processing Application like Audacity? As a master student of Information Technology, I want to take a research about Music processing. For ...
0
votes
1answer
45 views

What is Algorithmic Game Theory?

Can someone give a good explanation + examples of algorithmic game theory? I read the wikipedia page and found a stanford course on it from 2012, though its still not clear for me what the use cases ...
1
vote
2answers
79 views

Will an optimal algorithm halt when it has read enough of the input to generate a correct answer?

I'll ask the question informally first and then try to work up to something more formal. Consider a linear search problem. We are presented with an unsorted array of numbers and are asked to ...
-2
votes
2answers
29 views

Comparing two Big O notations [closed]

Please, could you help me with the question below. Demonstrate that O(log n^k) = O(log n):
12
votes
1answer
83 views

Learning math while visually impaired

My eyes are destroyed. I have been unable to learn math beyond decimal division in school due to laziness and unhelpful teachers. I am now trying to mitigate this mistake by learning math from the ...
0
votes
0answers
29 views

Subtyping of Prop in Coq. Implementation of Ackermann class theory. First-order theories.

I am trying to implement Ackermann set theory. The first approach is the code below. But there is an incorrect axiom "rs_ax". That's because for every x formula (F x) shouldn't contain predicate M. $\...
1
vote
0answers
29 views

Additivity properties of asymptotic bounds

In several slides, I found the asymptotic property called additivity as follows: If $f = \Theta(h)$ and $g = O(h)$ then $f+g = \Theta(h)$. Below a snapshot from one of this resources is shown: I ...
2
votes
0answers
32 views

How many implication graphs are there for a given number of literals?

The context here is implication graphs over propositional literals and the 2-SAT problem. What function describes the possible number of non-redundant implication graphs given the number of literals? ...
0
votes
0answers
17 views

Sorting functions by an assymptotic order

What does it mean to sort functions by an assymptotic order? suppose I have 5 different functions: $f_{1}(x)=x^{0.8888}\log (x)$ $f_{2}(x)=1.000001^{x}$ $f_{3}(x)={{2^{2}}^{10}}^{6}$ $f_{4}(x)=\...
3
votes
1answer
52 views

Algorithm to decide the universality / functional completeness of a set of logic gates?

Given a set of logic gates $G$, let $F_G$ denote the set of all formulas composed of gates from $G$. We say that $G$ is "universal for computation" or "functionally complete" if it forms a basis for ...
2
votes
0answers
52 views

Finding the Dictator in Arrow's Impossibility Theorem

Arrow's Impossibility Theorem states that if we have at least three different social states and a finite number of individuals (voters), any social welfare function that satisfies the conditions of ...
0
votes
1answer
36 views

Convert Context-Free Grammar to Automata

I am trying to convert the following grammar to an automata: Let $S$ be the start symbol. $S \to aQc$ $Q \to aQc$ $Q \to aaRbb$ $R \to aaRbb$ $R \to \epsilon$. But I don't fully understand how to ...
1
vote
2answers
47 views

Prove $ \forall c \in \mathbb{R^{+}}, \forall B \in \mathbb{N}, \exists n \in \mathbb{N}, (n \geq B) \wedge (\sqrt{2n} > c \ln(n+2)) $?

So far I've proved the following: $2n \geq \ln(2n) > \ln(n+2)$ for $n \geq 3 $ The proof must be without the use of calculus but I have no idea on how to proceed.
0
votes
0answers
28 views

Finding the time complexity of the given code snippet.

Question Find the time complexity of the following code snippet ...
0
votes
0answers
23 views

How do I determine when an optimal solution is found in an auxiliary linear program?

The linear program to be solved after converting to auxiliary and slack form: $$z=-x_0$$ $$x_3 = 4 − x_1 − 2x_2 + x_0$$ $$x_4 = −12 + 2x_1 + 6x_2 + x_0$$ $$x_5 = 1 − x_2 + x_0$$ The final slack form ...
0
votes
1answer
22 views

Directly proportional realtoinship between power consumed and time taken by computer system.

Suppose there is a computer system that performs some specific event in multiple iterations and requires some amount of power and time for each iteration to be calculated. At every iteration system ...
2
votes
2answers
50 views

What is the relationship between modulo and $\log_2$ in this problem?

Here's a screenshot of a diagram from my computer architecture course. You don't need to understand the technical terms here. It's essentially mapping locations from one piece of memory to locations ...
0
votes
0answers
15 views

Proving NP-hardness of GAP problem using PCP theorem

I want to prove that for $0<\epsilon$ , the problem GAP 2-SAT[$\frac{11}{16}$ + $\epsilon$, $\frac{7}{8}$] is NP-Hard. According to the PCP theorem, the problem GAP 3-SAT[$\frac{7}{8}$ + $\epsilon$...
0
votes
1answer
42 views

Lossless Compression and definition of Entropy

I am taking an intro class to Information Theory and I have a question. Suppose we have three symbols a, b, and c with probabilities of them coming out of a chanell ...
2
votes
0answers
28 views

What's the generic-case complexity of the Halting Problem on LBAs?

I'm familiar with Hamkins' result that the generic-case complexity of the Halting Problem is polynomial in time. What's the analogous result for the various Linear Bounded Automata? Edit: For those ...
0
votes
2answers
63 views

what is the probability that a sequence is increasing?

I am preparing for my exams in algorithms & probabilty. For the exam preparation, we have been given this exercise. I couldn't solve this, even with the master solution given to us. In a casino ...
1
vote
3answers
69 views

Are context free languages closed under taking substring?

Let $L$ be context free and $\Sigma $ an alphabet Define $s(L):=\{y \in \Sigma ^*\mid \exists x,z \in \Sigma ^*: xyz \in L\}$ Is $s(L)$ context free ? I haven't been able to find a counterexample ...
-1
votes
2answers
45 views

Set cover: To show the number of minimum coverable combination of the power set of universe $U$ is less than $2^n$

Given a set $U=\{1,2,...,n\}$, and its power set $\mathcal S=\{S_1,...,S_{2^n-1}\}$(without emptyset $\emptyset$), a minimum coverable combination is $S_i\cup...\cup S_k=U$ and $S_i,...,S_k$ are ...
1
vote
2answers
33 views

Minimize the sum of a maximum of $X$ elements and $Y$ elements from $2$ different arrays so that a total of $N$ elements are chosen

A group of $N$ people are on a hiking trip. It starts raining heavily and the group starts looking for places where they can be protected from the rain. There are $2$ enclosures nearby where ...