All Questions

2
votes
2answers
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. ...
2
votes
1answer
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 ...
-2
votes
0answers
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 ...
0
votes
3answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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?
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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, ...
0
votes
0answers
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!
1
vote
1answer
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
48 views

Does solving all Halting problem instances 'in the limit' imply we solve an undecidable problem?

The recent Arxiv paper "Learning the undecidable from networked systems" attempts to construct a network of $N$ Turing machines$^1$ that can solve the Halting problem for any program of size $O(\log N)...
0
votes
1answer
28 views

Can a NP problem be reduced to another NP problem?

I have three related questions which have been bothering me for a while now... Suppose I have a problem $A$, which is in NP. Suppose there is another problem $B$ in NP, can I ...
0
votes
0answers
52 views

Alternative proof of the fact that heapify can be linear-time

As an exercise, I'm trying to prove by myself that constructing a binary heap from an array in-place can be $O(N)$. I've come up with an idea, but I'm not sure about its correctness. Firstly, I ...
-1
votes
0answers
20 views

computer network : network layer [on hold]

how to different network create a secure environment? i found in net but im not sure is this correct?? Perform auditing and mapping. ... Keep the network up-to-date. ... Physically secure the ...
0
votes
0answers
44 views

How to quickly solve a linear equation for 7000 times?

I need to solve a linear equation Ax=b for 7000 times (A is sparse and complex square matrix), and at each time only 4 elements (A(i,k), A(i,m), A(j,k) and A(j,m)) are changed while all other elements ...
0
votes
2answers
134 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...
1
vote
1answer
38 views

Can the notation for polynomial reduction, A ≤p B be reversed in computability theory?

I don't know this is a proper question on this forum but I was reading about computability theory and I saw the reduction concept and its notation like this: $A \le_pB$. I just wanted to know is this ...
0
votes
2answers
22 views

Address bus and memory

If I have an address bus of 64K, i.e. it can access 64*1024 or 65536 locations, should I also have a memory chip with 65536 locations in it? What I'm trying to ask is that do all the 65536 locations ...
1
vote
0answers
30 views

How to reduce number of move operations in an array?

Say I have an array of numbers, e.g. [0, 1, 2, 3, 4, 5] and I want to end up with an array, e.g. [2, 1, 4, 0, 5, 3]. At my ...
0
votes
0answers
6 views

Memory interfacing problem [duplicate]

I've learnt that the memory interfacing problem is used when we need to connect a memory that has lesser number of locations to a processor that has more address lines. For eg. Connecting memory chips ...
27
votes
4answers
4k views

What did Turing mean when saying that “machines cannot give rise to surprises” is due to a fallacy?

I encountered below statement by Alan M. Turing here: "The view that machines cannot give rise to surprises is due, I believe, to a fallacy to which philosophers and mathematicians are ...
1
vote
1answer
56 views

Given an array of size n, create a sub array with given conditions using dynamic programming

We are given an array of integers of size n, which is not necessarily sorted, and we want to create a sub array. We are allowed to do one of 3 tasks below in each level: 1. skip the number in original ...
0
votes
0answers
12 views

Finding percentage memory utilization in pipelining architecture

I was solving problems from the exercise of the book "Computer Organization and Design" by Patterson. The problem reads like this: Consider stage latencies: ...
3
votes
1answer
33 views

Proof that type does not have decidable equality in Agda

Can one create such function in Agda ? ℕ→ℕ-undecidable : ¬ ( (f g : ℕ → ℕ ) → Dec (f ≡ g)) ℕ→ℕ-undecidable = ? I am particularly interested in proof using ...
3
votes
1answer
37 views

Finding the shortest path for synchronized pawns in a maze

I have been trying to wrap my head around this problem, and I just can't get it. We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, ...
0
votes
0answers
27 views

Understanding the rules of parsing table construction

I'm studying top-down parsing, especially LL(1) parsing. However, I cannot understand what is the meaning of rules. Example grammer is like this S → ( S ) S | $\epsilon$ How can I derive like ...
0
votes
0answers
23 views

Relational Algebra with only one operator?

There's a parlour game of inventing exotic operators for Relational Algebra, and thereby reducing the number of operators needed to be 'Relationally Complete'. A popular operator for this is 'Inner ...
11
votes
2answers
1k views

What is the meaning of 'breadth' in breadth first search?

I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this: Breadth-...
1
vote
1answer
20 views

Complexity of set partition generation while equivalence relation is given

Given a binary equivalence relation, R on a set A, Let P be the resulting partition. I want to generate the partition means each subset in the partition. What would be the fastest algorithm for this ...
0
votes
0answers
10 views

Java Source Code for Constrcuting Buchi Automata from LTL formulas [on hold]

I am looking for a java implementation of constructing nondeterministic B\"uchi automata from linear temporal logic formulas. I tested several ones, but none of them worked for me. For example: 1) ...
1
vote
1answer
107 views

Will this algorithm always solve a constrained sudoku puzzle in quadratic time?

Constrained Puzzle Generation: Let us say a sudoku puzzle is generated with the following procedure: Gather a sequence input of 9 unique numbers in the range $[1 .. 9]$. Call it $S$. Map $S$ to a $3 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
42 views

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

Given the code below and the comment analysis: ...
-1
votes
0answers
16 views

in assembly language what does the # sign represent like in LDAA #$10 [on hold]

in assembly language what does the # sign represent like in the instruction LDAA #$10
-2
votes
0answers
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 ...
-2
votes
0answers
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$ } \}$. ...
1
vote
1answer
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 ...
-1
votes
0answers
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://...
0
votes
0answers
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 ...
1
vote
1answer
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$ ...
1
vote
1answer
15 views

Address and data bus

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? ...
1
vote
1answer
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 ...
-1
votes
0answers
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 ...
1
vote
1answer
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: ...
0
votes
0answers
35 views

Hardest problem in P and easiest problem in NP [on hold]

As of today, what is the hardest problem we know to be in P and what is the easiest problem in NP ? I would also like to know the complexity of both (big O notation). I tried searching for this online ...
0
votes
0answers
24 views

a^nb^nc^nd^n using 2-stack PDA

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

15 30 50 per page