Articles of computer science

Finding an MST among all spanning trees with maximum of white edges

Let an undirected graph $G=(V,E)$ with the color property $c(e)$ for every edge (could be black or white) and a weight property $1 \le w(e) \le 100$. Find the MST from the set of all spanning trees with the maximum number of white edges. Do it in linear time ($O(|V|+|E|$). So basically I want to […]

The Entscheidungsproblem and the notion of decidability in first order logic

The Entscheidungsproblem asks if we can find an effective procedure to decide for every formula of first-order logic if its true or false, or what is the same with regard to its completeness, if it is provable or not. This could be read on wikipedia. This problem was answered in the negative by Church and […]

“Plotting” an equation

I have an equation like $$ (x – a)^2 + (y – b)^2 = r^2 $$ that represents a circle. I need to “plot” it very basically with a programming language. Computer graphics coordinate generally use the “lower-right” quadrant of a Cartesian plane (0, 0 being top left). I want my circle to have its […]

Complexity of verifying proofs

My question can be read on many levels and so I welcome answers to any reading. The general question is: What is the computational complexity of verifying a proof? One way of looking at a computational complexity class (for decision problems) is that is is a set of theories (a theory being a set of […]

Prove that if $f(n) \in O(g(n))$ then $g(n) \in \Omega(f(n))$

Prove that if $f(n) \in O(g(n))$ then $g(n) \in \Omega(f(n))$. So I know that $$O(g(n)) \Rightarrow f(n) \leq c\cdot g(n)$$ and that $$\Omega(g(n)) \Rightarrow f(n) \geq c\cdot g(n)$$ but how do you use these to do the above proof?

Is there a computer programm or CAS (maybe GAP?) that can calculate with projective (indecomposable) A-modules (A is a finite dimensional k-algebra)?

I have the following question(s): I have an “Algebra-With-One” $R$ as a subalgebra of a full matrix algebra in GAP. Furthermore, I have 5 primitive orthogonal idempotents $e_1,…,e_5$, which sum up to $1_R$ (the identity matrix). I would like to compute the projective indecomposable modules $P_1=e_1R,…,P_5=e_5R$ with GAP (or another computer programm (e.g. SAGE) which […]

Why is the following language decidable? $L_{one\ right\ and\ never\ stops}$

I can’t understand how the following language can ever be decidable: $L= \{ \langle M \rangle | M \ is \ a \ TM \ and\ there\ exists\ an\ input\ that\ in\ the\ computation\ $ $of\ M(w)\ the\ head\ only\ moves\ right\ and\ M\ never\ stops \}$, but apparently it is. We need to approve […]

How to find the modular reduction of a very large number.

Suppose I want to calculate the modulus of a number raised to a number of powers, as in $$94^{{93}^{92 ^{{…}^1}}} \equiv x \pmod {265}$$ Is there a way to compute x , using a computerized method? (without actually computing the power)

Question about queues

A queue is implemented with a sequence $Q[1\ldots n]$ and two indices $\def\head{\operatorname{head}}\head[Q]$ and $\def\end{\operatorname{end}}\end[Q]$ such that the elements of the queue are the following: $$Q[\head[Q]], Q[\head[Q]+1], \ldots , Q[\end[Q]-1]$$ Initial $\head[Q]=\end[Q]=1$ When $\head[Q]=\end[Q]+1$ the queue is complete. Does ”Initial $\head[Q]=\end[Q]=1$” stand when there is one element in the queue? Could you explain me what […]

The time complexity of finding a neighborhood graph provided an unordered adjacency matrix

Imagine I have an unordered adjacency matrix for some graph $G$ with a set of vertices $V$ and a set of edges $E$. I would like to find a subset of edges that determines a $k$-hop neighborhood graph about a chosen vertex $v_i \in V$ (i.e. a graph consisting of the vertices and edges “reachable” […]