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

12k views

### Reduction from Hamiltonian cycle to Hamiltonian path

I'm looking for an explanation on how reducing the Hamiltonian cycle problem to the Hamiltonian path's one (to proof that also the latter is NP-complete). I couldn't find any on the web, can someone ...
283 views

### is all math beyond arithmetic just advanced arithmetic? [on hold]

Is it true that at the bare-bones of all advanced math, its all just mostly arithmetic? In computer programming languages they are mostly constrained to arithmetic operators. I suppose this is ...
5k views

### Are there dictionaries in math?

Consider the following dictionary in the programming language Python: D = {'A': 1, 'B': 2, 'C': 3} It is saying that the value of A is 1, the value of B is 2, ...
30 views

### Does 3-SAT reduce to 3-CNF-SAT?

I know that SAT goes to 3-SAT and SAT is reducible to CNF-SAT and CNF-SAT is reducible to 3-CNF-SAT but is 3-SAT reducible to 3-CNF-SAT? They are not the same thing though right because CNF makes it ...
179 views

### How to attack universal hash function based on finite-field arithmetic?

As per the Recursive n-gram hashing is pairwise independent, at best paper, I want to use the algorithm described in chapter 6 and 7 (page 7 - 10). The hash works as follows: Define a random ...
7k views

### What is the difference between discrete and continuous mathematics?

I am studying computer science and this has me absolutely flummoxed. The definition I can find is that discrete data is countable and that continuous is uncountable. Examples are given stating that ...
31 views

### Is there a method that determines an unknown permutation better than $\sum_{k=1}^n (k+1)/2$ steps on average?

Suppose I have a random permutation $s \in S_n$ that is unknown to me. However, suppose I can make a query where when I ask if $i$ is in the $j$th position in the permutation, I receive a yes or no ...
17 views

16 views

### Passing variables into function (MATLAB)

I am creating a function that perform multiple regression in MATLAB. The function is created as function [Beta] = george_linreg(y,x1,x2,x3,....,xN). I don't ...
598 views

### Can anyone explain the average case in insertion sort?

I am not sure if this question is off topic or not but a question like this has been asked on this site before - Insertion sort proof Here is an example of insertion sort running a on a set of data ...
26 views

### The relativised Church–Turing thesis

Barry Cooper states in his computability theory "The relativised Church–Turing thesis" on page 142 as follows: All formalisations of "$B$ computable from $A$" which are sufficiently reasonable ...
1k views

### How to use BFS or DFS to determine the connectivity in a non-connected graph?

How can I design an algorithm using BFS(Breadth First Search) or DFS(Depth First Search) algorithms in order to determine the connected components of a non-connected graph? The algorithm must be able ...
103 views

### Why does this pattern occur when using modular arithmetic against set of prime numbers?

I have been recently playing around with number theory and going through the project Euler problems. So I am very new to a lot of these things. I apologize for not knowing how to look up my answer. ...
76 views

### As a computer science major, should I take differential equations, linear algebra, or both? [closed]

I've taken three semesters of calculus (altho the way my school does it, Calc III excludes Green, Stokes, Divergence/Curl Theorems and puts them in a class called Calc IV), and I've met my math ...
427 views

### Data Representation Question

A computer stores a number of $16$ bits word using floating-point arrangement. Given that the first bit is reserved for the sign and followed by $6$ bits for the exponent using biased form. The ...
45 views

### Find a path from $s$ to $t$ with smallest “bottleneck”

Let an undirected graph, $G=(V,E)$ with weights defined by the function $w:E\to\mathbb{N}$ and for each edge: $1\le w(e) \le |V|$. You are given two vertices: $s,t\in V$. Find a path from $s$ to $t$ ...
23 views

### How to get increasing int number based on two values

I did ask this question on SO but it seems this will find more appropriate audience here. I have a Google map where I am dropping markers based on events, this happens periodically and after 8 hours ...
22 views

### 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 ...
49 views

### Shortest path from $s$ to $t$ in a graph with $5$ negative edges and no negative cycles?

Let $G=(V,E)$ a directed and weighted ($w:E\to\mathbb{R}$) and let $s,t\in V$. It is given that there are exactly $5$ negative edges and no negative cycles. Find the shortest path from $s$ to $t$. ...
5k views

### Number of ways to partition a rectangle into n sub-rectangles

How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be: ...