All Questions

0
votes
0answers
10 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 ...
0
votes
0answers
15 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
19 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
29 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
19 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
27 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
1answer
45 views

Algorithm for scheduling tasks

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 where the task must be delivered. Here ...
1
vote
1answer
34 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
1answer
9 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
22 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 ...
14
votes
5answers
1k views

What does Turing mean by this statement?

I encountered below statement by Alan M. Turing at 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
38 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
10 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: ...
2
votes
1answer
24 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 ...
2
votes
1answer
23 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
16 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
14 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 ...
7
votes
2answers
852 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
18 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) ...
0
votes
1answer
14 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
0answers
18 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
40 views

Big Oh Time Complexity Involving 'for i in range(n)'

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
36 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 ...
-1
votes
0answers
24 views

Theory of computation [on hold]

for two languages L1 and L2 E E* define L1/L2 the right quotient of L1 by L2 as follows: L1/L2={wEE*: there exists u E L2 such that wu E L1} show that if Lisa context free language and R is a regular ...
1
vote
1answer
39 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
vote
0answers
19 views

vertex cover of bipartite graph

A vertex cover of a graph 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. ...
0
votes
0answers
33 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
14 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
23 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
16 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
34 views

Hardest problem in P and easiest problem in NP

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
23 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 ...
-1
votes
0answers
17 views

What is the source to understand Feedback edge arc set? [on hold]

What is the source to understand Feedback edge arc set? I tried wikipedia and research papers any easy tutorial?
4
votes
3answers
735 views

What is a fractional matching?

For the maximum matching problem, we can find the fractional matching which I understand involves some sort of weighting for the edges. However, I cannot seem to find an exact and simple explanation ...
0
votes
0answers
13 views

Is there a collision free Hash Function for dynamic data that preserves already created hashes?

I am familiar with the concept of hash functions and fingerprints but I am new to the implementation of functions and the specific characteristics of all those hash functions out there. What I need ...
0
votes
2answers
23 views

Do the “virtual memory”s mentioned in the 2 articles refer to different things?

I've read the following 2 articles explaining the difference between virtual memory and physical memory. One thing that I found ...
0
votes
0answers
27 views

is this given language in class P? [duplicate]

i was wondering: is this language in class P? $NONDISJOINT_{DFA}\:=\:\left\{<A,B> |\:A\:and\:B\:are\:DFAS\:and\:L\left(A\right)\:\cap L\left(b\right)\:\ne \varnothing \right\}$ explanation: a ...
0
votes
0answers
17 views

How do I prove this equation [on hold]

if n==0: return 1 else: return x*recursion(x, n-1) I already tried proofing it, I replaced n with n= k+1 and 2K +1 but I'm not getting the correct answer, ...
-2
votes
0answers
23 views

Disprove efficiency $(\log n)^{(\log n)} \in$ O($n^{2}$) [on hold]

Disprove: $(\log n)^{(\log n)} \in$ O($n^{2}$)
0
votes
1answer
51 views

How many possible ways to go right and up in an array

Let's say we have a 2D matrix, and we begin at $(0, 0)$. We must travel $m$ steps to the right and $n$ steps up, in any order. Each step moves the position right or up by $1$. For example if $n = 5$...
0
votes
0answers
26 views

Are real computers capable of producing true random series with a program of finite length?

Suppose that one has a Blum–Shub–Smale machine. Is it possible to write down a program of finite length that produces a series of numbers, with each consisting of a finite number of digits, such that ...
0
votes
1answer
19 views

Tree search returning parents and children

I've a flat structure where a node references its parent instead of children class Node(int Id, Node Parent, string Data); Given a list of all nodes, and a ...
2
votes
0answers
16 views

Formal semantics of a mutable/imperative stack

When introducing formal semantics for data structures, immutable stacks are a nice simple example : $\mathit{is\_empty}(\mathit{create()})=\mathrm{True}$ $\mathit{is\_empty}(\mathit{push}(e, s))=\...
1
vote
3answers
45 views

What is the asymptotic bound for $1n + 2(n-1) + 3(n-2) + … + (n-1)2 + n$?

My best guess is that the series $$ \sum_{i=1}^n i(n-(i-1)) $$ becomes $$ 2 \Bigg[ n + 2(n-1) + ... + \frac{n}{2} \bigg(n-\bigg(\frac{n}{2}-1\bigg)\Bigg)\Bigg] $$ So the highest term is $n^2$ and ...

15 30 50 per page