# All Questions

30,205 questions
30 views

### Least common multiple of a list of numbers

I'm trying to learn computer science by doing some challenges. One is the following. 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. ...
68 views

### Path between two vertices in directed graph without cyclic vertices

I have been searching online for some time but I have not found an answer. Is there a polynomial time algorithm to find a path in directed graph between two vertices so that within the path no cyclic ...
30 views

### Is A.I. through computation possible? [on hold]

As far as I know, all contemporary electronic computers, or even the future quantum computers, follow the Turing machine model in the essence. But it seems none of them can achieve the computational ...
26 views

### Program counter in a CPU

I know that the CPU has a program counter which takes instructions that are required to execute a program, from the memory, one by one. I also know that once the first instruction is executed, the ...
30 views

### Deterministic Finite State Automata - Benefits of using DFA to typical software coding and testing [on hold]

Suppose I have modeled the behavior of my system by Deterministic Finite Automaton (DFA) A, and I need to check if it satisfies a safety condition. I have created another DFA S, which represents the ...
26 views

### Undecidability of emptiness of LBA

How is the emptiness of Linear Bound Automata (LBA) i.e $L = \{B \mid L(B) = \emptyset \}$ is undecidable?
28 views

### Triangulation algorithm for an arbitary amount of points?

I have multiple cameras that records the 2D pixel coordinates of the features each camera sees. After some searching, I came across this paper with a method to calculate the 3D coordinates of the ...
25 views

### What is the minimun type of logical system that recognizes if a formalized sentence is a well-formed formula thus reducible to the boolean value?

The formula, in the old way of using it, can contain symbols in order and a mixture that does not meet the criteria of correctness (i.e. arbitrary symbols do not form a well-formed formula (WFF) and ...
19 views

### Question on preventing k from reducing too quickly during KMV intersection

This question considers KMV, an algorithm that is able to estimate the cardinality (unique item) from a stream of data. The way it does it is to first map the stream of data to a space that almost ...
26 views

### What is the equivalent of the integers symbol Z for n bit only integers?

We refer to the set of all integers as $\mathbb{Z}$. Now suppose we have a set of integers that can be held within a computer variable of $n$ bits width. Clearly they can only be of $2^{n}$ range, ...
22 views

### How do I solve the part (a), of the following question?

The problem I'm facing is how do I know whether the mapping is "1-way set associative", "2-way set associative", "4- way set associative", etc. Please help!
21 views

### Question is about a paper “A Block-sorting Lossless Data Compression Algorithm” by M. Burrows and D.J. Wheeler

In the paper A Block-sorting Lossless Data Compression Algorithm by M. Burrows and D.J. Wheeler Link. On page number 5. please describe this line If the original string $S$ is of the form $Z^p$ for ...
16 views

### Which book or books are being used in these lectures on Distributed Systems?

Kindly take a look at these lecture materials. The instructor is suggesting to study books of Tanenbaum along with his supplied reading list. But, I am not finding any similarity of the content ...
48 views

15 views

### List of all possible reasoning tasks - satisfiability and theorem proving only?

What is the exhaustive list of reasoning tasks? As far as I can understand, then any logical reasoning reduces to 2 tasks only: 1) satisfiability problem (finding the assignment of the variables) and ...
26 views

### ILP representation of the number of maximal 1 sequences in a row

I am currently using an ILP to model events which occur on some input sequence from $1...n$. These events modify the input sequence in order to obtain a desired sequence. Each event can happen on some ...
42 views

### Big Oh Time Complexity Involving 'for i in range(n)' [on hold]

Given the code below and the comment analysis: ...
16 views

50 views

### Turing Machine the undecidable language

Consider the undecidable language $$\mathrm{ALLTM} = \{\langle M\rangle \mid M\text{ is a Turing machine with }L(M) = \Sigma^*\}.$$ Suppose you had an oracle for the halting problem (that is, you have ...
40 views

### Theory of computation [on hold]

For two languages $L_1$ and $L_2 \in E^*$, define the right quotient of $L1$ by $L2$, denoted $L_1/L_2$, as follows: $L_1/L_2=\{ w \in E^*: \text{there exists$u \in L_2$such that$wu \in L_1$} \}$. ...
48 views

### Why are those very similar languages in a different complexity class?

i am having a real time understand why the following two languages are in two different complexity classes(the first is NP-Hard and the second is in P). tried to look online at various resources and ...
91 views
+50

### Vertex cover of bipartite graph

A vertex cover is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover with minimal cardinality. https://...
42 views

### Find a minimum weight matching of a specific size

Given a positive-weighted complete graph $G=(V,E)$ and an even integer $k$, I want to find a minimum weight matching of size exactly $k$, i.e., I want to choose $k/2$ vertex disjoint edges such that ...
17 views

### Vertex Cover without covering all edges

What would be the name of the problem of a vertex cover that covers all the vertices without the requirement of covering all the edges? Vertex cover has to answer whether or not there is a set of $k$ ...
15 views

When people use the word "bidirectional" while describing buses, what are the two "directions" that are being talked about? Also, why is the address bus unidirectional, as opposed to the data bus? ...
27 views

### How exactly does a CPU do process scheduling?

I know in theory how various scheduling algorithms work, such as round robin, where each process is given small time slices to run a few instructions, before the operating system passes execution onto ...
17 views

### How can I find only the common integer partitions between two numbers? [on hold]

How to find only the common integer partitions between two numbers? Say we have 2 numbers, x, and y. I want to find the integer partitions that both of those numbers share, preferably with a python ...
30 views

### Fixed Points of Factorial Function

(This is taken from the book Semantics with Applications) I'm trying to determine the fixed points for the following block: ...
I need to construct a PDA using 2 stacks for accepting the language $L = \{a^nb^nc^nd^n |$ $n \geq 0\}$. Pushing $a$'s to first stack and $b$'s to second and poping them for corresponding $c$'s and ...