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 questions from scientific computing, use (computational-mathematics).

Filter by
Sorted by
Tagged with
0
votes
2answers
45 views

Proving homomorphism from functions

I am really struggling to grasp the concept of homomorphism as it has been poorly explained to me in courses, and I have not been able to find any clear examples of how to actually classify a function ...
-2
votes
0answers
25 views

Numerical computation [closed]

I am trying to study for a course I am about to take and I dont know where to even start on this. enter image description here
3
votes
0answers
115 views

I made one theorem (with proof) does it already exist?

Notations: $\mathbb{F}(\left\{0;1\right \})$ is the set of all finit word on $\left\{0;1\right \}$ let $m \in\left\{0;1\right \}^{\mathbb{N}} $ then $m|_n$ is the finit word of size n which coincide ...
0
votes
0answers
15 views

Sparse matrices, sparse accumulator and multiplication

I'm trying to implement the algorithm for multiplying two sparse matrices from this paper: https://crd.lbl.gov/assets/pubs_presos/spgemmicpp08.pdf (the first algorithm - 1D algorithm). What bothers me ...
2
votes
0answers
25 views

Non optimal multiple traveling salesman problem

The following is a variation of the multiple traveling salesman problem (MTSP) where the salesman begin at different locations: There are $S$ sites in a city at different fixed geo locations $(a_i,a_i)...
0
votes
0answers
33 views

What does difference over sum mean in a set of values? [closed]

What would be the meaning of $X$ given that $A$ and $B$ are a list of values in which the values are approximately the same, i.e., $ \frac{A}{B} \approx 1 $ and both ${A,B} > 0$ ? $$ X = \frac{A-B}{...
1
vote
2answers
56 views

Simplification of the Traveling Salesman Problem

I'm not sure I can call it a simplification of TSP but here it is: Suppose you're given the Traveling Salesman Problem but in addition, you're also given the shortest possible distance (not the route) ...
1
vote
1answer
42 views

Prove $\{0^k10^k10^k1 \in \{0,1\}^* \mid k \geq 0 \}$ is not context free

I'm practising for my CS exam and got stuck on this problem $$ \{0^k10^k10^k1 \in \{0,1\}^*\mid k ≥ 0\}. $$ I think I have good start however I don't know how to proceed. I assume the L is context ...
0
votes
1answer
26 views

Solving a problem involving primitive and partially recursive functions.

We have that for a partial function $f : \mathbb{N}^{k+1} \to \mathbb{N}$, the $\mu-$ operator is defined as the following: $$\mu (f)(x_1, ..., x_k)=\begin{cases} n, & f(n,x_1,...,x_k)=0 \...
-4
votes
0answers
30 views

Problem in latex file. [closed]

I have a latex document on my PC which I create before 2 hours. unfortunately, it shows blank while opening in Texmaker or Texstudio. command-tab is also blank. an error log is: ! Text line contains ...
0
votes
0answers
40 views

Kruskal's Algorithm [closed]

How can I prove that a minimum-geometric-mean spanning tree of G is made through Kruskal’s algorithm? (through contradiction, induction, or another method?)
2
votes
1answer
94 views

Why is $f_1(n)$ not computable but $f_2(n)$ is?

I have the following two functions, where the first one is not computable and the second one is. $$f_1(n)= \begin{cases} 1 & ,\text{if in the decimal representation of n appears in the ...
-3
votes
0answers
9 views

how many exchanges will occur for a tree height h in the Worst case analysis of MAX-HEAPIFY procedure? [closed]

I'm a little confused about this activity in my course, and reading the textbook it's just confusing me more.
1
vote
1answer
45 views

Eigen-Decomposition of Householder operator

Define the eigen decomposition of householder operator $H=I-2ww^*$ where $\vert\!\vert w\vert\!\vert=1$, geometrically! I know that the eigen-values are $[-1, 1 \dots 1]$ but I cannot understand about ...
1
vote
1answer
25 views

Stationary Distribution of Tsetlin Library/Move to Front Markov chain

Consider $R_1, R_2, ... R_N$, N items arranged in a sequence. With probability $p_i > 0$, item $R_i$ is moved to the front of the sequence. This defines a finite Markov Chain of $N!$ states. What ...
0
votes
0answers
32 views

What are some applications of graph edge colouring in computer science or discrete geometry, or other areas of math?

My area of interest is graph theory (I am starting my PhD soon) and I have done a bit of research already, mainly proving small results in the area of graph colouring and extremal graph theory. Of ...
3
votes
3answers
344 views

Interpreting english EITHER-OR when approaching logical deductions doubt

The following question has been asked in the Indian entrance examination "GATE CS 2021", and it has stirred up a lot of confusion regarding how one should interpret "either-or" ...
6
votes
1answer
138 views

World's smallest (Exception-based) proof-checking language (in Python). In what way is Coq, Lean, Isabelle “better”? [closed]

As you may already know, the codebases written for Coq, Lean, etc. are humungous. Thus a goal in a new proof assistant might be to simplify things. Suppose we restrict our attention not to general ...
0
votes
0answers
14 views

Cyclomatic number is equal to number of linearly independent paths through graph

I'm trying to understand the cyclomatic complexity metric. It says that cyclomatic number of graph is equal to the number of linearly independent paths through the graph. I don't see the connection ...
0
votes
0answers
29 views

How to prove the optimality of greedy algorithm in a change problem with binary coin values?

Consider the change making problem, the input to this problem is an integer L. The output should be the minimum cardinality collection of coins required to make L cents of change (that is, you want to ...
0
votes
0answers
10 views

Entity Relationship Diagram.

I have to make a biathlon relationship diagram. country (MAA), players(URHELIJAT), Venue(PAIKKA), Competition(KILPAILU), Competition type(KILPAILU TYYPPI), score (Sijoitus) are my entities. In my case ...
1
vote
1answer
87 views

Music and Fourier Transform

I am trying to build a "program" to determine musical chords. I want to add that that I am not an expert in this field of mathematics so it should be considered an unrigorous project. ...
3
votes
1answer
55 views

Can I interpret $\models$ as $\implies$ while proving logical expressions using different techniques?

In the book by Artificial Intelligence by Norvig and Russel, I came across following problem: Prove if correct: $(A ∧ B) \models (A ⇔ B).$ I quickly interpreted $\models$ as $\implies$ and tried to ...
-1
votes
2answers
49 views

Prove that the following program is correct using Hoare logic inference rules [closed]

I have to prove the correctness of the following program using Hoare logic inference rules. I just know that we are given precondition and post condition. I don't know how to do it. Please can anyone ...
0
votes
0answers
38 views

Optimize a linear programming problem

problem \begin{align} \text{minimize}&\;\;\;c^Tx\\ \text{subject to}&\;\;\;\|x\|_p=1\\ &\;\;\;x\geq0 \end{align} for $c, x\in{\bf R}^n$ and $p\geq1$. Hi, I know $-x \leq 0$ then $x \geq 0$...
0
votes
0answers
12 views

Minimum Equal Pairs in Set Containing Specific Values

I'm currently working on a program which involves presenting equal pairs of values to a user, from a list pseudo-randomly populated with values between 1 and 8. E.g. [1,5,5,4,3,4,5,5] would return 3 ...
1
vote
1answer
38 views

Relation between Halting problem and Godel's incompleteness Theorem

I've heard that these are closely related to each other. However, while the former looks totally trivial to me, the latter still puzzles me even after I read the proof of it. So I made up a scenario ...
0
votes
0answers
17 views

CS Problem being inconsistent in sample test cases, Balanced trees

I am preparing for the Canadian Computing Competition, and I have stumbled across this problem: Problem Description Trees have many fascinating properties. While this is primarily true for trees in ...
0
votes
1answer
25 views

Proof of greedy algorithm.

Given n numbers find the way to assign them to blocks of 3 (and possible one block of 1 or 2 if n is not divisible by 3) so that sum of smallest elements from each full block is maximal. ie. numbers ...
0
votes
0answers
13 views

Asymptotics in multiple variables problem

Assume that $f(k)$ is a function dependent only on some parameter $k$. $n$ is the size of input. I have an algorithm running in time $O(f(k)\cdot n^{c})$ for some constant $c$. I wish to show that ...
1
vote
1answer
15 views

The concept of the creation of a trapdoor in NP-complete or NP-hard problems

I am reading the book An Introduction to Mathematical Cryptography. In its chapter 7, there is the following statement: In real world scenarios, cryptosystems based on NP-hard or NP-complete problems ...
1
vote
0answers
65 views

Shortcuts of basic arithmetic: why or why not is it helpful?

This is a question about simple arithmetic, especially multiplication, of positive integers. The usual way of computing the product of, for example $53$ and $47$, is $$ 53\times 47=50\times 40 + 3 \...
1
vote
0answers
19 views

Finding the closest triangle matching the inverse uv mapping

I have an algorithm which takes 2 triangles ABC and PMN, where ABC is the triangle that is rendered and PMN is an extra triangle that is used for texture mapping and converts the PMN triangle to UV, ...
0
votes
1answer
65 views

2-universal hash-function

In my theoretical computer science course the professor left followed statement open (so we could create our own proof), but i really do not understand it: Let $s \in \mathbb{N} $ and $p \in Prime$. ...
0
votes
1answer
29 views

CRC polynomial must include $X^0$?

Must every polynomial include $x^0$, for example $G(x) =\dots+ x^0$? I could not find any resource which elaborates on it. From computer networks: Both the high- and low-order bits of the generator ...
1
vote
1answer
36 views

Masters Theorem $T(n) = 2T(\frac{n}{4}) + (\log(n))^2$

I have a problem that I am trying to understand using the master theorem since it applys. The problem at hand is, $T(n) = 2T(\frac{n}{4}) + (\log(n))^2$. I am not sure I am correct in my final ...
2
votes
0answers
30 views

How to improve the accuracy when using computer calculating?

In practical application, it is often required to calculate a certain sum of the series (accurate to a certain decimal place) and there is no doubt that I will use a computer to calculate that For ...
0
votes
1answer
21 views

Binary floating point precision question

How do we know what is the degree of precision of an 8 bit floating point number and what fraction of the possible value of the number might it vary by and still be represented by the same bits in my ...
1
vote
1answer
56 views

0.1+0.2=0.30000000000000004 in floating point IEEE representations arithmetic addition manual proof.

I am trying to prove the 0.1+0.2=0.30000000000000004 by adding the numbers 0.1, and 0.2 in IEEE floating-point representation. I have added the operand values in IEEE format, with the general addition ...
0
votes
0answers
11 views

Can ratio data be plotted using same-sized bins?

I often want to plot ratio data (one variable divided by another) but don't know how to bin the data for visualization. An example ratio dataset is normalized standard deviation: Every day I have a ...
0
votes
0answers
13 views

Existence of an example of biased function in double precision computations using round-to-nearest.

When performing an operation on a computer, the result (often) needs to be rounded to fit mantissa length of double precision, i.e. the last digit of the mantissa is chosen based on the rounding ...
0
votes
2answers
51 views

What is the language recognized by the finite automaton?

I have no idea how to approach this?
2
votes
0answers
37 views

How to get a combined measure of error (cm) and angle (degree)?

I am a researcher in cognitive psychology studying object locations respective to a landmark. I have the error (distance between the real position of the object and the position where the patient put ...
0
votes
1answer
27 views

Sudoku based problem. Counting with permutations?

I have been playing Sudoku lately, and I've seen a problem with this general form: Given N items, each of which belongs alone (1-to-1) in one of N boxes, and given a list of statements of the form: &...
1
vote
1answer
45 views

A graph theory problem from mobile games

Example game interface This is the question that comes to my mind when I play a game called QuickyRoute,which essentially a Hamilton graph problem,the game will randomly generate a number of points,...
0
votes
0answers
23 views

Why doesn't the K-SVD algorithm simply take the derivative equals zero method to update $d_k$?

Here is K-SVD from wikipedia. the objective function is $$ \quad \min \limits _{D, X} \{ \|Y - DX\|^2_F \} \qquad \text{subject to } \quad \forall i \;, \|x_i\|_0 \le T_0. $$ In the K-SVD algorithm,...
2
votes
2answers
92 views

Motivation behind Lambda Calculus?

The lambda calculus provides a formalism broad used in theoreretical cs to write functions without giving them explicit names, it declares anonymous functions. That is at first glance it's just an ...
1
vote
1answer
41 views

Combining two DFAs into 1 DFA using concatenation [closed]

L= { w : w has exactly two a's and at least two b's} Picture of DFA's https://i.stack.imgur.com/4mPHU.png I have made the two DFA's separately, but I am having trouble combining them specifically the ...
2
votes
1answer
29 views

proof that any boolean function can be written in canonical form

It's bugging me for a while but although I can vaguely see that when writing canonical forms we kind "build them" in a way specificly to make it be true but I can't grasp exactly why it is ...
2
votes
0answers
22 views

Tutorials on lexicographically first maximal clique?

The lexicographically first maximal clique problem is P-complete. Could you direct me to any tutorial materials that show how the reduction from Circuit-Value to lexicographically first maximal clique ...

1
2 3 4 5
97