1
vote
0answers
6 views

Tallest Person Average Memory Updating?

We ran into a problem that mentioned in an Interview 2-days ago. How can help us with any idea or hint? n persons randomly enter to a room . we want to find ...
0
votes
0answers
4 views

Strongest Statement to made about complement and dec.

Let's say I have a decision problem, D and it's complement D'. I know D is poly-time reducible to D'(it's complement). Furthermore, I know D is Np-Complete. What is the most strongest statement I ...
0
votes
0answers
12 views

A logic function that is true iff the first operand is less than the second operand

In my computer organization class I have been given a series of problems. One I'm stuck on currently is below: Assume that $X$ consists of 4 bits, $x_3 x_2 x_1 x_0$, and $Y$ consists of 4 bits, ...
0
votes
0answers
7 views

Relationship between independant set and VertexCover

Directly from Wikipedia, A set is independent if and only if its complement is a vertex cover. Does this imply the independent set problem's complement is the vertex cover problem?
0
votes
0answers
6 views

Understanding terms related to 2 SAT algorithm

Recently I am learning about solution of 2-Satiability problem using SCC(Strongly Connected Component). There is a theorem related to this problem given below: Theorem 2: The formula F is true if and ...
0
votes
0answers
4 views

Poly-time reduction: D and D Comp

Looking at the IndependentSet problem and it's complement. I want to show that IS is poly-time reducible to it's complement, however I am struggling on coming up with the reduction function. I will ...
0
votes
0answers
6 views

Placing data on the bus for a synchronous read operation

This question is taken from Computer Organization and architecture, William Stalling: For a synchronous read operation (Figure 3.18), the memory module must place the data on the bus sufficiently ...
0
votes
0answers
8 views

Is this grammar LR(1)?

A bit confused about whether this grammar is ambiguous or not C' -> C C -> d C u C C -> d C C -> ε I tried building the DFA for this but I get this ...
0
votes
0answers
9 views

VC Dimension for open intervals

I'm having difficulty calculating VC dimensions for these scenarios, any help is appreciated. $H = [a,\infty)$,I think it's 1 since if the label is less than a it's not gonna shatter. One sided ...
1
vote
0answers
7 views

In which pipeline stage are exceptions detected?

Do you immediatly handle an exception when it occurs (for example an overflow exception in the EX stage) or do you wait until the final pipeline stage and then check whether any interrupts had ...
-1
votes
1answer
14 views

Edges of minimum spanning trees.

Is as edge of a minimum spanning tree in a graph $G$ the shortest path between its incident vertices? I think this might be true due to the cut property of but I am unable to prove it.
0
votes
1answer
17 views

Recursive algorithm to compute a sum of product like function

I am working on a recursive formula associated with discrete mathematics which seems very difficult to compute. The formula is as follows $F_{i,j}(m)=\sum_{t=j}^{m}\left [ ...
2
votes
2answers
26 views

What's the difference between declarative syntax and encapsulation?

I had been first introduced to the idea of declarative syntax when using Angular JS. From what I understand, the idea is that you say, "do this" instead of "in order to do this, do this, this and ...
-1
votes
0answers
9 views

Sat Solving with conflict driven backtracking

I'm stuck at a question as It had no other UIP than the decision variable so , what to choose for a conflict clause first cut as a conflict clause or the decision variable. Is Taking cut as conflict ...
0
votes
1answer
19 views

Proving that any CF language over a 1 letter alphabet is regular

I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far: Let L be a ...
-1
votes
0answers
15 views

How do I prove that 1 function is an upper bound of the other?

If for every $n > 0$ and some $b > 1$, $T(n) \le h(n)$ and $h(n) = O(h(n/b))$ then how can I prove that $T(n) = O(h(n))$, I understand that $T$ is bounded by $h$, so $h$ must be its upper bound, ...
2
votes
1answer
29 views

Undecidable (logic) Post correspondence problem instance

Since the post correspondence problem is undecidable, there exists an instance of this problem such that we can neither prove that the instance is positive nor prove that the instance is negative. ...
-3
votes
0answers
10 views

mingw does not let me use complex.h [on hold]

I am trying to use complex.h in mingw, but it is not working. I get the error message: $ gcc complex.c -std=c99 In file included from complex.c:2: /usr/include/complex.h:25:20: _mingw.h: No such file ...
0
votes
1answer
33 views

If $F$ is valid then $F \cup \{res(C_1,C_2,A_i)\}$ is valid

I have to prove the following problem in propositional logic: Let $F$ be a set of clauses and let $F' = F \cup \{res(C_1,C_2,A_i)\}$ be the extension of $F$ by a resolvent of some clauses $C_1,C_2 ...
1
vote
1answer
23 views

Term rewrite system is non-confluent, but cannot find different normal forms of term

I wrote a simple TRS that I believe is non-confluent, but I'm not able to find a term with two normal forms for it. The TRS is defined on the signature $\mathcal F=\{f,\ l,\ s,\ o\}$ and the rewrite ...
0
votes
0answers
17 views

Sequential vs Parallel Source Code [on hold]

I am a student of computer engineering. For my course of study I need to find code written in both serial and parallel (MPI), to write a report where I compared the efficiency. Browsing the ...
2
votes
1answer
35 views

Going deeper with pseudo-polynomial time algorithm for set partitioning

If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next? To illustrate this ...
0
votes
0answers
16 views

How to measure a probability that two data objects represent the same entity [on hold]

What algorithmic ways exist to assign a probability for two data objects to represent the same entity? For instance, identifying misspelled person names, using ambiguous initials, when we may also ...
1
vote
0answers
28 views

Potential method analysis for Insert and Extract-max on a Max heap data structure

Suppose that you do some sequence of operations on a max heap, in this case only Insert and Extract-max. Whenever the heap ...
2
votes
1answer
19 views

When can we assuredly say that a function is little o of some other function? [duplicate]

I'm trying to determine a function $f(x)$ that is $O(f)$ but not $o(f)$ and also not $\Omega(f)$. Note the $f$ used in the asymptotic notation is not the same as $f(x)$. Originally I thought of ...
3
votes
1answer
60 views

Primitive Recursion and course-of-values recursion - examples?

I ran into examples that I not trivially understand on course-of-values recursion, In defining a function by primitive recursion, the value of the next argument $f(n+1)$ depends only on the ...
3
votes
1answer
38 views

Greedy algorithm for Set Cover problem - need help with approximation

I want to approximate how close is the greedy algorithm to the optimal solution for the Set Cover Problem, which I'm sure most of you are familiar with, but just in case, you can visit the link above. ...
2
votes
1answer
23 views

Explanation of implementation of an algorithm for Dominating Set [on hold]

I'm working on an application, in which users can use domination in graphs. I have already finished up with graph generation algorithm, I use lists to store vertices... So, I have found a well ...
3
votes
0answers
13 views

Pi Calculus: Restriction necessary for molecular (atomic) action?

In "A Calculus of Mobile Processes, Part 1" [1], Milner et al. give an example for transmitting a pair of values $(u,v)$ from the process $P$ to either $R$ or $Q$ (see page 13). All three processes ...
1
vote
1answer
25 views

Difference between normal-order and applicative-order evaluation

The language I'm learning is Scheme and I'm working on an exercise that gives this: ...
-2
votes
1answer
58 views

What is the algorithm to add 2 binary numbers with boolean operations?

What is the algorithm to add up 2 binary numbers when the basis is {negation, conjunction, disjunction} in linear time? Also the program needs to be linear as well, meaning there can only be ...
3
votes
0answers
29 views

Can someone help me make this branch and bound algorithm more efficient for a large input?

I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the coursera discrete optimisation course) I tried implementing dynamic programming first, and that worked ...
0
votes
0answers
32 views

Does a computer science major need any certificates after completing their major? [on hold]

sorry if this a dumb question, and many, many thanks in advance!!! assuming one were to do well academically, and build up their portfolio also during their free time (hobby and such), would a ...
0
votes
1answer
29 views

Is a partial function Turing-computable?

From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and ...
1
vote
0answers
8 views

Importance of indexes in Type(i) in calculus of inductive constructions [duplicate]

So I am reading about the calculus of inductive constructions. And I see here and here that there hidden indexes that the user does not know about in the $Type$ sort. It says that they are ...
0
votes
0answers
29 views

A context free grammar for the language of even-length non-palindromes [duplicate]

I am trying to find a context free grammar for the language $L = \{xy \mid |x|=|y| \text{ and } x≠y^R\}$ where $y^R$ is the reverse of string y and $x, y\in \{a,b\}^*$ . Here is a possible ...
-4
votes
1answer
24 views

Complexity if special case of SAT

I have the following problem: How to show that the special case of SAT, in which each clause has either exactly two literals or at most one negative literal, is NP-complete?
0
votes
0answers
11 views

how to use dynamic memory in c language to create arrays with variable size [on hold]

I want to know how to use dynamic memory in c language to create arrays with variable size? i.e. i need to get the size of the array from the user and not i want it to have a predefined ...
0
votes
1answer
11 views

Express XOR with multiple inputs in zero-one integer linear programming (ILP)

In the below post, it is explained how to express xor of two variables as linear inequalities. Express boolean logic operations in zero-one integer linear programming (ILP) Naturally, the xor of ...
0
votes
0answers
18 views

Memory allocation for C++ [on hold]

I am having trouble understanding which parts of a C++ program, or even in general, is part of dynamic memory, static memory, and the activation record?
5
votes
3answers
85 views

Unreachable Real Numbers - Randomness & Computability

I've recently read that there were many real numbers that would never be reachable by humanity. The explanation itself says that we can write as many programs as integers which is infinite, but there ...
-1
votes
1answer
38 views

Comparing two graphs, finding vertices that changed their positions [on hold]

I have a task of comparing two organisation charts. These chart objects are described as a set of nodes (people) where each has a unique ID field and a parent ID field (pointing to another node's ...
1
vote
2answers
34 views

How can I see which language type will result from the union or intersection of different language types?

I have to decide which language type will result from the union of a type-2 (context-free) and a type-3 (regular) language. Is there a way or rule to decide this for all language types?
0
votes
1answer
23 views

What is a sufficiently complex system?

I have been reading about the AI approaches, and I came across the AI emergent approach that has the following definition: That is, the appearance of an entity with a sense of its own identity and ...
0
votes
0answers
7 views

Generating Function and Recurrence Relation in Contest? [migrated]

What is the generating function for the sequence $\{a_n\}_{n \geq 0}$, defined by $a_0=0$ and $a_n=\frac{1 \times 5 \times ... \times (4n-3)}{1 \times 2 \times ... \times n}$ for $n \geq 1$. ...
0
votes
0answers
8 views

Any good algorithms for 3d volume alignment by feature extraction, especially ones involve machine learning?

I am trying to align 3d mri brain images of different rat individuals. I have dozens of examples that have been aligned manually, which are good resources for machine learning. I am considering ...
0
votes
0answers
9 views

In Grover and Shor Algorithms 2 registers of qubits are handled at books, but it's really just one seen as 2?

I found in the literature that we require at least two quantum registers for arithmetics operation. Example: The function $f(x)=x^2$ is then a unitary evolution of the two registers, in this ...
4
votes
1answer
37 views

What is an $NP^{NP}$-complete problem? [duplicate]

So in this paper I'm reading (https://adamsmith.as/papers/fdg2013_shortcuts.pdf), the authors talk about an $NP^{NP}$-complete problem, in relation to Answer Set Programming. I know what P, NP, etc. ...
0
votes
1answer
17 views

Looking for an algorithm to generate an identicon/avatar from genome data

I am looking to develop an app that generates a single identicon image that summarizes the genome information in visual form. Identicons are essentially a visual hash of of data. usually string data ...
-3
votes
0answers
8 views

Visio/ Infopath to R [on hold]

I am looking to import company IT asset info from Visio/ Infopath to R programming language. I have tried converting these to excel and then importing into R but the problem is I have a lot of visio ...

15 30 50 per page