All Questions

2
votes
2answers
94 views

Decidability of equivalence to existential formulas

I'm looking for an algorithm to decide if a given first order formula over a fixed vocabulary admits a logically equivalent existential one (i.e. a formula in prenex form where all quantifiers are ...
1
vote
1answer
28 views

Minimal, “natural” set of operations to manipulate a binary tree

Consider binary trees with some abstract values at the leaves. A tree t2 is said to be "derivable" from a tree t1 iff the set of values in the leaves of t2 is included in the set of values in the ...
-1
votes
1answer
27 views

Truth table and logic circuit problem

Does anyone know how to make this into a truth table and a logic circuit? (x•y)+x If so please send me the answer.
0
votes
0answers
13 views

Are there any Linear genetic programming tools available? [closed]

I have been learning the concepts of linear genetic programming(lgp) lately but I am not able to find any tool which implements the concepts of lgp. Can someone suggest tools/software which ...
4
votes
2answers
49 views

Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?

I can see that $L$ has to be context-free but not regular here as regular languages are closed under concatenation and intersection. But $L\cap L^2$ looks too weird. I couldn't think of any $L$ that ...
0
votes
1answer
31 views

What's a general rule for this little lambda calculus identity?

I've been fiddling around with a project that does some normalization of lambda calculus(-like) expressions and I stumbled upon that (λ λ ... λ n (n-1) ... 2 1) (...
0
votes
1answer
30 views

Which BackJumping Algorithm is being used here?

This is the illustration of the Backjumping algorithm for four queens exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem .I am confused whether this is ...
-1
votes
0answers
13 views

visual basic displaying in different forms by module [closed]

How can I display MICROSOFT ACCESS data ( supplier) from datagridview1 of different form by calling it from the module? is it possible? i have tried to display it using private sub but i want my ...
3
votes
1answer
31 views

Can maximum matching algorithms be used for maximum weight matching?

There are two fast algorithms for maximum matching on general graphs: Micali and Vazirani in $O(E\sqrt{V})$. Mucha and Sankowski in $O(V^{2.376})$. Can these be also used for maximum weighted ...
0
votes
0answers
38 views

Prove or Disprove: If A is regular and A ∪ B is not regular, then B is not regular

I'm doing a problem where I need to prove the following statement: If A is regular and A ∪ B is not regular, then B is not regular. In another similar problem that I did, I know that if A is regular ...
1
vote
1answer
27 views

Trying to understand the question(well spaced points ?) better

Let us have a sorted array of n numbers and we would like to find a well spaced set of C of them, More specifically, we want to get a subset $ S\subset T$ with |S| = C and with $min_{i,j \in S,i\ne j}...
2
votes
1answer
38 views

Union of infinitely many regular languages [duplicate]

I need to prove or disprove the following statement. If $A_n ⊆ \Sigma^*$ is regular for each $n \in \mathbb{N}$ then $\bigcup\limits_{n=0}^{\infty} A_n$ is regular. I know that if two languages ...
0
votes
0answers
15 views

The computer is doing weird things [closed]

My laptop does things its not supposed to for example -it turnes on the ctrl+alt+del screen and presses the log off button all on its own (it uses the mise pointer to do that) -the pointer presses the ...
1
vote
1answer
30 views

Make a Pushdown automata that accepts a language defined by strings that contain the same number of a and b [duplicate]

How do I build a pushdown automata that accepts the language over the alphabet $\Sigma = \{a, b\}$, defined by the strings $w$, such that $|w|_a = |w|_b$? I'm sorry I can't give any approach of what ...
0
votes
1answer
50 views

Design an algorithm that solves the same problem in. O(nlogn) time. Prove it’s time complexity [on hold]

I have the following algorithm and need to solve the problem in a more efficient O(nlogn) time. ...
2
votes
1answer
49 views

Learning the activation function in a neural network?

Neural networks use specific activation functions, commonly used ones are tanh, ReLu. I have seen that people have experimented with continuously parametrices activation functions, for instance here. ...
5
votes
2answers
461 views

Logic behind O(n) solution for 'Maximum length sub-array having given sum'

I am unable to understand the logic behind O(n) solution of this classical problem- Maximum length sub-array having given sum (...
0
votes
0answers
18 views

Adding a Date Reported field to a General Ledger - Multi Dimensional Bucket Adjusting

Problem: Given a typical general ledger where balances are posted as "deltas", such that the total net of amounts (debit-credit, below simplified as "amount", equals the ending balance), we want to ...
-1
votes
0answers
31 views

Implementation of Tertiary Heaps [closed]

How would you represent a ternary heap in an array? What is the height of a ternary heap of n elements in terms of n? What is an efficient implementation (in pseudo code) of EXTRACT-MAX in a ...
-1
votes
1answer
45 views

Analyzing asymptotic notation $\sqrt n = O(\log^2 n)$

I am trying to determine whether $f(n) = \sqrt n$ is in $O(g(n))$, $\Omega(g(n))$, or $\Theta(g(n))$ where $g(n) = \log^2 n$. The answer says that only $f(n) = \Omega(g(n))$ is correct, but why isn't ...
0
votes
0answers
33 views

Accumulators in Microprocessors [closed]

Could somebody tell me how I can solve this problem? In an 8085 processor, suppose the accumulator content is FFH and the carry flag is 0. What will be the content of the accumulator after RAL and RLC ...
2
votes
0answers
27 views

The equation for how much data is produced every period [closed]

I am trying to find out how much data we produce to project how much we will produce in the future. I find stuff like this and this: There are 2.5 quintillion bytes of data created each day at our ...
-1
votes
0answers
27 views

How to infer whether we will apply supervised or un-supervised learning in below situations?

In this question , how to characterize whether we have to employ supervised or unsupervised learning ?
0
votes
0answers
26 views

Storing binary tree with arbitrarily sized nodes without linked-list or large 32-bit pointers

So you can store a binary tree without pointers using a 1-D array: Binary Trees can be represented using 1-D array in memory(Fig 1).The rule to store binary tree in array are : The values of ...
1
vote
1answer
29 views

heap pop creates unbalanced tree?

say you have a min-heap. Popping removes the root and replaces it with the value of one of the leaves and then heapifies. couldnt this last heapify result in an unbalanced tree? is there something ...
4
votes
0answers
30 views

Highest covering repeated string

Let's say I have the following string: XXXXXAYYYYBYYYYCXXXXXDYYYY We can see that the substring XXXXX is 5 characters long, ...
1
vote
1answer
34 views

Which AC-3 algorithm is being used here?

This is the illustration of the AC-3 algorithm for four queens from exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem by Md. Ahsan Ayub, Kazi A Kalpoma,...
1
vote
0answers
49 views

An Alternative History of Haskell: being lazy without class?

[The q is a play on the title of this 2007 survey of Haskell.] tl;dr I have a couple of connected questions about Haskell's overloading mechanisms. I'll ask first then explain why. I'm looking at the ...
0
votes
0answers
25 views

Number of ways to partition a tree(containing values in its nodes) into groups such that each group has xor sum equal to Z

I tried two approaches: 1. Give each edge two numbers on its left and right side denoting xor sum for subtree on its left and right respectively. If total xor sum for whole tree is Z, then it can only ...
0
votes
0answers
34 views

Minimum number queries on matrix

As part of a solution to an earlier question, I am interested in the following problem. I have a 2-D matrix $M$. I want to preprocess it in linear time so that I can answer queries of the following ...
1
vote
0answers
19 views

Elegant or readable way to store tree by user [closed]

Sorry if my title or question is unclear. I lack the vocabulary to formulate it properly. I've got a classical tree structure with several layers. I have to manage authorization for each user, as not ...
0
votes
1answer
11 views

How do we fix area of detectors in object detection?

I have gone through various articles on medium and also some from other sites trying to understand SSD. I am able to figure out most of the things from articles except this one. They always say that ...
0
votes
0answers
9 views

Architecture of ANN to combine images

I am interested in ANNs that combines two images in single as it shown below: But I don't know how it's called and can't find any papers or tutorials about the architecture of these ANNs. Can ...
5
votes
2answers
75 views

Must the champion of an entire tournament beat the champion of a possible tournament among other players?

I have a list of "players" of a "tournament". Any two adjacent players may "compete", which results in the loser being thrown out of the tournament. Winning is not transitive. The winner of a given ...
3
votes
2answers
44 views

Regular expression for binary words with 1 in the middle

Given the alphabet $\{0,1\}$, generate a regular expression with the following language: $$ \{w\in \Sigma^* \mid w \text{ has odd length and its middle symbol is }1\}. $$ I'm having trouble finding a ...
-5
votes
0answers
19 views

Should we still study finite automatan? [duplicate]

Can anybody help me with this homework question? In the era of information, technology changes at drastic speed, and the same is observed in Computer Science and Information Technology. The need ...
-2
votes
1answer
105 views

Regular Expression and Finite automata in field of compiler construction [closed]

In the era of information, technology changes at drastic speed and same observed in Computer Science / Information Technology field. Need of intelligent compilers for high level languages are ...
2
votes
1answer
49 views

Lexicographically smallest down-right path in matrix

Here is the problem which I thought was simple dynamic programming, which is however not the case. Given an $N \times M$ matrix of numbers from 1 to $NM$ (each number occurs only once), find a path ...
0
votes
1answer
63 views

Proving the singleton language {x} is regular for all x ∈ Σ*

So I'm aware that the singleton language is in fact regular for all x ∈ Σ*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would ...
1
vote
0answers
31 views

$n$ machines, $n$ types of jobs with $q_j$ jobs, minimizing the cost

I have this problem A firm has $q_j$ jobs of type $j$, where $1 \leq j \leq n$. It also has $[n] = {1,2,...n}$ machines. Machine $i$ can service any job of type $j$ where $j ≤ i$. The cost of ...
0
votes
0answers
12 views

Algorithm to find sum of all values in a 2D matrix when i<j [closed]

Given an array A of n integers, output an n by n array B in which B[i,j] (for all i=j values of B[i,j] are left unspecified so ignore that case). My approach: The most natural way to do this is by ...
0
votes
1answer
24 views

What is the asymptotic complexity of the following code snippet?

for (i = 2; i < n; i = i * i) { for (j = 1; j < i / 2; j = j + 1) { sum = sum + 1; } } I know that the outer loop can run for a maximum of $n^2$ ...
0
votes
0answers
18 views

Did Menezes et al. switch the letters $\mu$ and $\lambda$ in Floyd's cycle detection note 3.8?

The letters $\mu$ and $\lambda$ are usually used to represent, respectively, the length of the tail of the graph and length of the cycle in the graph. But Menezes on note 3.8, page 91 (or PDF-page 6),...
0
votes
1answer
18 views

Sorting on non-linear topology

Disclaimer. What I'm going to ask about below may seem to be "Topological sorting". To my understanding, it is not. The latter runs in linear time, while I'm looking for a modification of the regular ...
2
votes
2answers
39 views

Is the reverse of a closed under operation maintainable?

I'm looking at the following question from this handout: The class of decidable languages is closed under union My question is, does this hold in reverse? Is there a phrase for this? Basically, if ...
0
votes
1answer
44 views

DFA for $L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$

$L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$ Any idea? I have problem with this kind of task.
-1
votes
1answer
44 views

How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$

$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$ I don't have any idea. Can someone help me.
1
vote
0answers
25 views

Reasons for why x - 1 and x -1 gives different result in F# [closed]

I assume the reason space makes a difference in F# is due to reserving a certain function, when minus is in front of a number without space, however what are the reasons for this? I can't seem to find ...
3
votes
1answer
41 views

Replace queries on string

Let's define a replace query on some string $s$. Consider a string $s$ of length $n$ over alphabet $C = \{ c_{0}, c_{1}, c_{2}, \dots, c_{k}\}$. Also consider $l, r \in \{0, 1, 2, \dots, n - 1\}, l \...
4
votes
0answers
27 views

What is a “model” of lambda calculus?

I know about the concept of the "model" of a logical proposition in the context of mathematical logic: It is a mathematical structure in which that proposition is true. However, it's not clear to me ...

15 30 50 per page