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

20 views

### Calculating screen intersection points with lines

I am writing a game and for the life of me can't figure out the most efficient way to program this. I have a boss who comes into the middle of the screen. He then engages 4 lasers which extend well ...
40 views

### How to use binary search to find a function

I am reading somewhere that $$(\phi'(y))^{-1}=y^{-c_1}+y^{-c_2},$$ $c_1,c_2$ are some numbers, can be solved for $\phi$ using binary search. I am surprised because binary search binary search is used ...
67 views

### Pigeon-Hole Principle and 2d grid

Q:Consider the 2D grid with integer coordinates.Prove that if we take 5ve points on the grid then there exist two of the points whose average is also a point on the grid. I understand the basic idea ...
39 views

### Hypercomputation & Higher Dimensional Variants of Conway's Game of Life

Conway's Game of Life is a simple and important mathematical game with some rules of evolution in a two dimensional space. It appears in many subjects in mathematics, artificial intelligence and ...
14 views

### Maximum variable string length $m$ needed to represent $n$ items using strings of size $1$ through $m$ with fixed alphabet size

Consider the following problem. You have a list containing $k$ total identifiers comprising $n$ unique identifiers such that $k \ge n$ (i.e. there can be duplicates). These identifiers are long ...
12 views

### Induction for quantified statement with two discrete parameters

Given a quantified statement ∀n, n>0 (∃x, x>2k | x=2k+n) ( a subset of the natural numbers) This can logically this can be deduced as valid; however, I wish to use induction. Specifically I would ...
59 views

### Increase by one all edges, Min-Cut, changes or not?

My Friends, as i ask a new question recently, Increase by one, Shortest path, changes the edges or not? i want to ask a related question as a new post Suppose we have a Graph G in which weight ...
37 views

### Increase by one, Shortest path, changes the edges or not?

as i read the following text : "Let P be a shortest path from some vertex s to some other vertex t in a graph. If the weight of each edge in the graph is increased by one, P will still be a shortest ...
34 views

### How much RAM is needed for $2^{14}$ square grid of double numbers?

How is calculated the memory that is needed for matrix of $2^{14}$ by $2^{24}$ double precision real numbers ? Matlab stops responding with 32Gb ram.
38 views

### Big O - arithmetic rules

I need to prove the following statement: $O(f(n)g(n))=f(n)O(g(n))$ At first I thought the statement is false but apparently it is true. How can I prove it?
25 views

### Entropy determination regarding lossless data compression

Suppose I had many computer data files to compress losslessly and wanted to know what is the theoretical limit to each one as far as minimum filesize possible. How would a math person go about doing ...
102 views

### Computers can't deal with limit of $\Delta x \to 0$

While I was studying about finite differences I came across an article that says "computers can't deal with limit of $\Delta x \to 0$ " in finite differences.But if computers can't deal with these ...
120 views

### Good resource/exercises for learning asymptotic analysis?

I am studying asymptotic methods right now; things such as mellin transform, inverse mellin transform, saddle point method, laplaces method, etc... and I get very frustrated because I can't get very ...
11 views

### Amortized analysis: Understanding the potential formula

The potential formula is: $$\overset{\wedge}{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1})$$ $\overset{\wedge}{c_i}$ the amortized time of operation $i$ is the actual time $c_i$ plus the change of the ...
50 views

### Pumping Lemma for Context Free Languages: Is this language CFL?

I am learning for the first time the Pumping Lemma for CFL, and I thought I understood how it works until I came across this example: "Show that $L = \{a^m b^m c^n \mid m \leq n\}$ is not a CFL." My ...
23 views

### Proof of why the partition function Z in probabilistic graphical models (PGM) is NP-complete

I was wondering if someone knew why computing the partition function for probabilistic graphical models is NP-Hard? I would like to see a full blown rigorous proof, however, I am as happy to get a ...
18 views

### Turing machine that goes left on first symbol

I have a turing machine with transitions given by the following table I'm inputting the string aaaa. So if I look at the first symbol "a" in state A, it says to replace it with an X, go into state ...
64 views

### For those wanting to study theoretical computer science, is Math a degree that worth more than Computer Science?

At my University, everyone first enrol in a Science and Technology, a very general course, and then choose the specialisation (like Computer Science, Math, some Engineering, etc). As I was finishing ...
21 views

### How to take the integral of a derivative to obtain desired result?

I am aiming for the form of derivative below computed over time that causes its differentiated variable V to go from an initial -.001 and increase to reach 10. I will explain my current calcs below ...
80 views

### Humankind knows the prime factorization of the first how many consecutive integers?

I am only looking for an approximation. I'm guessing the answer must be somewhere between $10^{20}$ and $10^{50}$. . Edit: Okay so my first initial estimation was pretty poor... I should have ...
62 views

### A Strange Algorithm on Processor [closed]

We have n processes, each with a predetermined start and end time. We want to use the ...
34 views

### The disease problem

Students are sitting in a n * n grid. There's a disease spreading among them in a particular fashion. At start, there a 'k' students infected(At random). After every time step(equal intervals), the ...
86 views

### Las Vegas algorithm to satisfy most clauses in SAT

Consider an instance of SAT with $m$ clauses, where every clause has exactly $k$ literals. Give a Las Vegas algorithm (i.e., an algorithm that always gives the correct result) that finds an assignment ...
46 views

### Most efficient mental way to convert Decimal to Hexadecimal

My question is as follows: What is the most efficient mental way to convert Decimal to Hexadecimal? I've heard of many methods. Some people divide the decimal by 16 and find the remainder. Others ...
42 views

### Prove that wheel (Wn) graph family are hamiltonian

I need to determine and prove that wheel (Wn) graph family are hamiltonian. I know that the Wn graphs are hamiltonian where it's possible to create a cycle that contains all the vertices, but How to ...
86 views

### Numbers as sum of distinct squares

Yesterday Polish Olympiad of Information Science ended, one of the questions was purely mathematical, Squares (PL). In the task, we have defined square ...
50 views

### Counting the number of complete bipartite subgraphs

I am stuck with problem and not getting much ideas. I have a graph with $N$ vertices and $M$ edges. I have to count number of ways I can choose a pair of set of vertices say $(p,q)$, such that every ...
22 views

### Two decidable languages for which a mapping reducibility does not exist?

The trivial null language might not be reduced to another language, but are there standard examples of two decidable languages $L_1$ and $L_2$ such that there is no mapping reduction possible from ...
39 views

### How to find the shortest path of a graph in a turing machine

I'm reading about Turing machine and I saw some examples as: Let $M_{1}$ a Turing Machine and the language $B = \{w\#w \vert w \in \{0,1\}^{*}\}$, We want $M_{1}$ to accept if its input is a member of ...
40 views

### How can be a conservative field constraint be efficiently implemented in a continuous optimization problem?

Suppose we have the following continuous optimization problem: $$\underset{x}{\mathrm{minimize}}f\left(x\right)$$ subject to $$\exists X:\nabla X=Jac\left(X\right)=x$$ where $f$ is a function ...
21 views

### How to determine the increase in the Z-Axis. Of a tessellated sphere

I have been tasked with drawing the sphere below for a programming assignment using openGL. I have the assignment mostly completed however I am having issues figuring out the math for the sphere. For ...
18 views

### What is the complexity of halving the size of an $n$-bit number every time.

I was discussing this question with my fiend the other day and was hoping to get some confirmation from someone if the logic I used is correct. Suppose that we have a number $N$ in base 2 ie ...
15 views

### Check if an axis aligned bounding box intercepts with a triangle

As the questions says I am trying to check if an AABB intersect with a triangle. I've divided the problem in 3 parts: check if any of the triangle edges intersect any of the AABB faces check if the ...
50 views

### How to find an expression for a number via a given set of math operators and constants?

Consider one gives you $n$ digits of a (possibly irrational) number and a finite set of math operators and constants, like $\{\sin(x), \ln(x),+,\times, \pi,e,7\}$. Then he asks you to build a ...
19 views

### How to define percentage values in terms of scalar

Imagine a game in which you choose many cards with different A,B,C values. Such as : Card 1 A - 4 B - 5 C - 6 Card 2 A - 2 B - 7 C - 4 ... and so on.. To ...
74 views

### Is it possible to express the idea of a number bigger than any other number ($\infty$) in programming languanges? [closed]

I'm studying graphs and algorithms, most of the algorithms we're using (such as Prim's algorithm), have the need of a table with a symbol $\infty$. Which in some contexts mean that it is the biggest ...
18 views

### Nondeterministic finite automaton understanding problem

It is probably a silly question but I have problem understanding it. Let's say I have to design a nondeterministic finite automaton that accepts the language consisting of words containing a string of ...
29 views

### Pushdown automaton design

I have to design a PDA that recognizes the language: $$L=\{w \mid \#(a,w) - 3\#(b,w) = 2\}$$ where $\#(a,w)$ means the number of letters $a$ in $w$ My idea is to count $a$'s and $b$'s. I have to ...
22 views

### Why are all singletons confluent?

A relation R of a set M is confluent, if $\forall x \in M \forall w1,w2 \in M :((xRw1 \land xRw2 ) \to \exists z \in M (w1Rz \land w2Rz))$ . 1. Someone told me that all singletons, no matter the ...