All Questions

Filter by
Sorted by
Tagged with
1
vote
1answer
14 views

Why does $L = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belong to $\mathcal{P}$?

My professor said that the non-regular language $L_{1} = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belongs to $\mathcal{P}$. I do understand that all regular languages belong to $\mathcal{P}$ as ...
0
votes
0answers
5 views

Using Lean Theorem Prover from command line

I have read this link about using Lean: https://leanprover.github.io/reference/using_lean.html and am able to use Lean with VSCode, but I still have questions about using Lean from the command line. 1....
0
votes
0answers
13 views

Under the assumption that $P \neq NP$, prove or disprove the following propositions

I have problem to point 7 and 8. Let $L1,L2 ∈ \{0,1\}^*$. Under the assumption that $P \neq NP$, prove or disprove the following propositions: $L_{1} ∈ P ⇒ L_1^c ∈ NP$. [FALSE] because with $P \neq ...
0
votes
0answers
5 views

Convert a polygon mesh into a b-spline surface

$\textbf{Problem:}$ Getting a $\textit{polygon-mesh}$ as input, I have to construct a surface that looks exactly to the given input. My task is to generate a $\textit{b-spline}$ surface that exactly ...
0
votes
0answers
8 views

ln(n) + 1 Approximation for Set Cover constructions

Set Cover Problem: Given a set $X$ and a collection of subsets $S_1, S_2, \ldots S_m \subseteq S$, we want to find the smallest cardinality of a set of $k$ elements $\{i_1, \ldots i_k \}$ such that $\...
0
votes
1answer
17 views

Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

I want to find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$ I've tried the following: $G=(V,\Sigma,R,S)$ with $\Sigma=\{a,b,c,\lambda\}$, $V=\{S,B\}$, $S=S$ and $$R=\{S\to \...
0
votes
1answer
16 views

Can polynomial many-to-one reduction be done to a specific problem instance?

Let's say I reduce the problem $A \in L$ to $B \in K$ , with a function $f: \Sigma^{*} \rightarrow \Gamma^{*}$ such that $w \in L \Leftrightarrow f(w) \in K$ . I know if I want to solve $A$, given ...
0
votes
1answer
17 views

How to convert a centralized algorithm to a distributed algorithm?

Is there any algorithm or procedure to convert a centralized algorithm to a distributed algorithm? Is there any theoretical result or relevant complexity analysis?
-2
votes
0answers
10 views

data hazard about five-stage instruction pipeline

or $2,$5,$3 sw $1,3($2) lw $5,1($6) Does data hazard occur in these three instructions? My answer is no but I am not sure. Also, is ...
0
votes
0answers
5 views

Splitting filename text by underscores using RStudio [closed]

In R I'd like to split file names in the format "a_b_c_d.jpg I need the a and b value If I use strsplit I get [1]"a" "b" "c" "d.jpg" but i want [1] a [2] b and for c, d it's unimportant what's ...
2
votes
1answer
17 views

Weighted Average of Multi-Output Neural Networks

[1] discusses how to construct an ensemble of neural networks by giving each network a certain weight $\alpha_i$: \begin{equation} f_\mathrm{GEM}(\boldsymbol{x}) = \sum_{i=1}^N \alpha_i f_i(\...
0
votes
0answers
9 views

Doubt in effective memory access time in case of n level paging + TLB

I am getting confused with calculation of EEMAT(Effective memory access time). I decided to close the book and think on my own and make an equation. Please see whther this is correct or not. I thought ...
0
votes
0answers
12 views

Equivalence between two different definitions of PAC learnable

In a course on machine learning, I saw a definition of "PAC learnable class". But on a paper of C.Laskowski, there is a slightly different definition and I cant prove the equivalence between them. I ...
-1
votes
0answers
14 views

Question about pipeline cycle hazard [closed]

The question is to find the hazards within Cycle 1 to 6 and their correct values, as well as the type of the harzards Thank you!
0
votes
0answers
19 views

decidability and reducibility

I am a bit confused on how I can show the finiteness problem is undecidable using Rice’s Theorem. So I’ve got something like B = { | M is a TM and L(M)- finite}. I thought I could reduce A TM (...
-1
votes
1answer
31 views

Program v. Algorithm v. function

I'm a beginner with C++ and have been going thru SICP. Recently, I have started to grapple with the difference of a program v. algorithm v. function and want to know, would this be a good comparison ...
0
votes
0answers
24 views

Probability of detecting errors in codewords

I have been struggling with the below question for quite some time, and I don't have a pointer to move forward. A certain Error Control Coding scheme using block codes takes an input block (...
0
votes
0answers
31 views

What is the logical reasoning behind Arden's Theorem proof of unique solution?

Here is the proof for Arden's Theorem assertion that R=QP* is the unique (only solution) to R=Q+RP. My question is: what is the logical reasoning to prove that any equation is the unique (only ...
-3
votes
0answers
15 views

Need to fill in missing parts c++ Language [closed]

template void hashT::insert(int hashIndex, const CType2& rec) { // Fill up this part! } template void hashT::search(int& hashIndex, const CType2& rec, ...
-2
votes
0answers
18 views

Assuming a set is decidable, prove that another set is decidable

Suppose we're dealing with programs that output zeros and ones. Consider all such programs (in a fixed language) having at most n instructions. For each program in this finite set, look at how many ...
-1
votes
0answers
9 views

How to tell if a language is regular or context free based on its description [duplicate]

I dont understand how to tell if a language is regular or context free by just looking at its description. For example question 1.2: how is it not regular? can't we create a regular expression for ...
0
votes
1answer
38 views

triangle inequality TSP is NP-complete?

I have been reading online source and it mentioned triangle inequality TSP is NP-complete but without proof. In general, the reduction from HAM-cycle problem to TSP works for asymmetric and symmetric ...
1
vote
0answers
26 views

How do I modify Floyd-Warshall to find the shortest path with an odd number of edges?

Given a connected weighted graph $G=(E,V)$, how do I modify Floyd-Warshall to find the shortest path with an odd number of edges? Floyd-Warshall recurrence $$ D_{ij}^{k} = min\{ D_{ij}^{k-1}, D_{...
1
vote
1answer
24 views

Dijkstra without decrease key

I was reading though this paper, which suggests using dijkstra without edge relaxation, but to rather to just insert new nodes, cf page 16 for the pseudo code. But to me the code looks wrong. I think ...
0
votes
1answer
35 views

Validity of self refering state with linear temporal logic 'X' connective

Lets say we have model like the one above or a similar one where a node refers back to itself. Now let's say if I want to know the validity of the formula: $M, s_2 \models Xr$ Will this be valid ...
0
votes
0answers
12 views

I need help with Converting Polynomials into Binary form [closed]

X^7 + x^4 + x^4 + x + 1 i don't know what to do with double x^4 help pls, and sry for my english
0
votes
0answers
9 views

How can you track if a gmail email has been opened or not [closed]

I've been trying to setup a email tracking system but it seems like nothing I've tried so far works with gmail. I've tried using google analytics but even google says it won't work with gmail. So I ...
0
votes
0answers
8 views

Improving Turing Machine for Eulerian Path Problem [closed]

I'm trying to construct a determinististic one-tape Turing Machine for an Eulerian Path (https://en.wikipedia.org/wiki/Eulerian_path). I have written the one below as a starting point, but would like ...
0
votes
1answer
27 views

What is the relation between a programming language and the language of its input?

I find some references say that all the features of programming language fall within what can be captured by context-sensitive grammars. In fact, no programming language known to humankind anything ...
0
votes
0answers
30 views

If any problem in NP is not in P then NP C ∩ P = ∅

If any problem in NP is not in P then NPC ∩ P = ∅ The proof is: We have $X ∈ NP$ and $X \not\in P$. Assume $Y ∈ NP C ∩ P$. As $X ≤_P Y$ we have $X ∈ P$, which is a contradiction. I have not clear ...
2
votes
0answers
10 views

Probability of colisson for classes of hash functions

I am going through some old exams in one of my courses, and I don't have acces to solutions, and found a exercise I am not sure how to tackle. I am not looking for the answer but some help/guidance if ...
2
votes
0answers
18 views

Generation of pseudorandom floating point numbers on floating point vector DSP

I am working on a custom IEEE754 floating point vector signal processor with 64 cores and need to generate pseudo-random floating point numbers at high rate. The only numerical operation available to ...
2
votes
0answers
19 views

How to use machine learning algorithm for different input data? [closed]

Yes, You heard it right. My title is "How to use a machine learning algorithm for different input data?", For example, we have an algorithm called "Email spams detector". Okay, so how to apply the ...
1
vote
2answers
19 views

Question for “Only if” part for the theorem “A language is Turing-recognizable iff some enumerator enumerates it.”

I am trying to prove the theorem A language is Turing-recognizable iff some enumerator enumerates it. I proved the "if" part, but I have no idea of proving the "only if" part, so I searched a ...
0
votes
0answers
5 views

CPLEX anytime results [closed]

I am working on an NP-Complete problem. When I ran the CPLEX, it gives me only the final solution. I am asking for the help so that I can print the interim results with the time. I am using Python v....
-2
votes
0answers
21 views

Design a NFA and DFA which accepts: (1+01)*(0+00)(1+10)*

This is the DFA I came up with and my teacher said it was wrong without explaining why. I couldn't find the mistake. Any help will be appreciated
0
votes
0answers
23 views

How to solve the following problem by using Gaussian elimination with partial pivoting (A=PLU)?

****The Question is here***** (in the link) Given a nonsingular matrix A $\in$ $R^*(nxn)$, how would you solve the following problems efficiently using Gaussian elimination with partial pivoting (the ...
1
vote
0answers
25 views

Proof of Fundamental Lower Bound on Regret

Online Convex Optimization sees optimization as a continuous process in which the algorithm learns new aspects of the problem and improves upon. Every iteration consists of the player making a ...
2
votes
1answer
57 views

What is the problem in this Turing Machine that describes $a^nb^{2^n}$?

So I have tried to describe a Turing machine that describes the said language with the following ...
0
votes
0answers
60 views

Minimizing the distance from a set of nodes in a tree

We have a binary tree with n nodes and a number k which signifies the number of nodes that we put on a set. What is the optimal algorithm to select a set consisting of k nodes, that minimizes the ...
0
votes
0answers
38 views

A question about Pipeline Cycle

This is my question, I am so confused with my answer, looking for help! This is my answer: Explanation: At the third instruction, instruction is waiting before ID, thus, no stalling is needed. (it ...
0
votes
0answers
19 views

Deleted Partition and backing up data on Windows [closed]

so in order to make partition to install Ubuntu I have deleted my whole partition on hard disk and I thought all my data was lost. Then I come around notion that my data should be there even if I ...
0
votes
0answers
14 views

The rotation matrix of a stereo pair with the cameras are horizontally aligned

Please forgive my ignorance on this. It seems like very soon I will have a D'OH moment and it will click. In the meantime, I am having trouble thinking about the joint rotation-translation matrix of ...
0
votes
0answers
6 views

Contingency Table Confusion NLP

Hello for the contingency table: [true positive, false negative, false positive, true negative]. I am having a hard time remembering the difference between these terms because all the terms are ...
1
vote
2answers
15 views

Complexity of minimizing the maximum inter-cluster distance?

Given $n$ non overlapping points $x_i \in \mathbb{Q}$, and an integer $k\geq 2$, what is known about the complexity of finding $k$ means ($a_1, a_2, ..., a_k$) that minimize the maximum inter cluster ...
3
votes
1answer
28 views

Partitioning bag of sets such that each set in a group has a unique element

Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one ...
-2
votes
0answers
27 views

How to formally prove the dependencies of a computer malware?

I'm in the process of the writing a thesis. A small part of it is to prove that certain malware have certain dependencies which must first be satisfied before they are successful in infecting the host....
2
votes
0answers
16 views

Rackoff's coverability bounds in case the addition vectors of VAS and the target vector are from {-1, 0, +1}?

In "The covering and boundedness problems for vector addition systems", Rackoff considers a VAS $(v,A)$ of dimension $k$ and size $n$ and derives an upper bound of $2^{2^{(\log_2 3)n(\log_2 n)}}$ on ...
0
votes
0answers
8 views

question about register file in mips

I'm studying the MIPS , i have one question that how can the register file get two instruction and write to the two instruction in one cycle ? can i add a new data bus to the second instruction ? (the ...
-1
votes
0answers
26 views

Help with computer engineering problem [closed]

Have been trying to figure out this problem for quite some time but don't know how to approach it. Consider a system that can host 64 GB of memory and has 8MB of L3 cache. Suppose that each cacheline ...

15 30 50 per page