All Questions

I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 ...

I am looking for a fast solution to the assignment problem for large cost matrices (5000x5000 or larger). The Hungarian algorithm is $O^3$, which is impractical for any moderately large problem. Are ...

I have two functions, $$ f = n^{1.6} $$ $$ g = n^{1.5} $$ I thought this is $ f=\theta(g) $, since $ f $ is asymptotically tight bound of $ g $, if $ n $ goes to infinity. However, the answer is $ f ...

As the title states, how do you prove that $A$ is productive? With $W_{x}$ I mean the set of points in which the turing machine with index $x$ halts. The standard approach that I follow is functional ...

I need some help with understanding the difference between greedy and non-greedy regular expressions. I used java to practise my implementation of regex. I organised the regex in to groups for easy ...

I have a problem with my random number generator! Here is my code: //A simple C++ program that allows a user to flip a coin x amount of times. include include using namespace std; //Creating ...

After many years, I have been revisiting the venerable old Halting Problem and the self-referential / diagonalization “party trick” that shows that there is no Turing Machine able to solve it. I was ...

I usually do it via topological sort and wonder if there is a simpler way to generate a linear extension from partial orders without consider the graph of the relation.

Say I have an array and I want to add those values to something else. What is the space complexity if I incrementally take one of those values off the first list and add it to the second? For example, ...

1) What is the difference between protocol deadlock and routing deadlock ? 2) Why {packet classes} = {message classes} X {resource classes} ?

Given an acyclic graph, how can I build a lambda calculus term such that this graph is the term's Böhm tree? If the Böhm tree is a finite tree (so the result is a strongly normalizing term). If the ...

I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem theorem. it is this If i number of people voted for A and j number of people voted ...

I have heard about all these Man-In-The-Middle Attack preventions and I am wondering, how this can possibly work if the man in the middle only listens to your stream and does not want to change the ...

We say that a binary tree : $B(l, x, r)$ is increasing if $x$ is smaller than all the nodes of the binary tree and if $l$ and $r$ are also increasing trees. One way to merge these kind of trees is as ...

Good morning. At the moment I try to understand pipelining of an MIPS processor. I know that, if I have a piece of Code and one instruction depends on the other, than we maybe could a have problem (...

I can't make out what is the avantage of it comparing with the port designed I/O Is it faster? Is it more reliable? Is it cheaper?

I was reading about tge Turing machine. I also came across with the Shakespeare programming language. After trying to understand the basics of the PL, I thought ...

I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination ...

I have to transform the following grammar into a non left recursive grammar: S → aSb | bAS A → AaA | bAA | AAa | bAb This is what I came up with: A → bAAA’| bAbA’ A’ → aAA’| AaA’| ε S → aSb | ...

It is known that in the case of a Regular Language $L$ , the pumping lemma can be extended to apply to any sufficiently long subword of the language, ie, if $uwv \in L$ and $|w| \ge p$ then we can ...

Which arithmetic operation does the term $\texttt{$\lambda$n.$\lambda$m.m (MULT n) 1}$ compute?

What is the normal form of the following lambda term? I'm stuck between two answers and I just wanted to know which one is correct. $$\lambda y. (\lambda x.x)\ y$$ Possible Answer 1: $\lambda x.x$ ...

Consider the following computational problem (or rather, task): Given: An array of $A$ of (not necessarily distinct) elements from a fully-ordered finite domain An ordered sequence pivot ...

I've just began a course on logic and learned the following : De Morgan's laws Normal forms How to represent a logical formula (using or, and, not operators) using binary trees How to ...

I'm just posting this to verify my answer to the below question... If a closed term is a weak head normal form, it has to be an abstraction “\x.M”. Why? It has to be an abstraction because M ::= x |...

I know that the general strategy to do the correction of an algorithm is as follow : if the algorithm is recursive then prove the correctness using induction if the algorithm is iterative (...

I want to work with django framwork of python.I faced this problem. How to install the pipenv shell by cmd. what is the solution ?

How would I indicate whether the following lambda terms have a normal form: 1.) \x.(\y.yx)z)v 2.) (\x.xxy)(\x.xxy)

I am learning lambda calculus from the book https://www.irif.fr/~mellies/mpri/mpri-ens/biblio/Selinger-Lambda-Calculus-Notes.pdf and do not understand the meaning of the following symbols. The ...

How can we show that the term $\Omega = (\lambda x.x\ x)\ (\lambda x.x\ x)$ does not have a normal form? Building on this, what is an example term different than Omega that is not normalizing (meaning ...

Note: this question was marked as a duplicate in favor of this question/answer which attempts to provide a generic formula for translating code to mathematics. Unfortunately I didn't find that ...

I have some code that implements the Gillespie algorithm, and have started looking at using Fenwick trees for the interval membership part of the algorithm. However, my rates are calculated in a way ...

First of all, it's my first time in #ComputerScience at StackExchange so, my apologies if I'm making some newbie mistake when asking this question. So, I'm currently researching algorithms for ...

I am picking up from this thread for which I have no privileges to comment on: Is C actually Turing-complete? I was wondering if there's any progress on this and what the conclusion actually was. ...

I want to buy a new laptop. My purpose is to do artificial intelligence and some programming. I will occasionally (once a week) do photo and video editing. My preference is a thin and light one. I ...

In the ARM Architecture pipelining stages, we know that the instructions pass from fetch to decode and so on? But, from where does the fetch unit get the instructions?

I am working on IDDFS with some demo graphs but it's not working properly. I need input graph in specified format (as shown below) and want to print the list of visited nodes. Here is the current code,...

I'm doing a problem where I need to find the equivalence classes of the language below: Let A = {x ∈ {0, 1}* | #(01, x) = #(10, x)}, where, for a, b ∈ {0, 1}*, #(ab, x) is the number of places in x ...

How to generate CFG for this language? $ L = \{ w \mid w \in \{ (, [, ], ) \}^* \text{ s.t. } $ In any prefix of $w$, no. of ( is more than no. of ), and no. of [ is more than no. of ]. $\}$ Thus,...

I have the language $ A_{1} \triangleq\left\{a w c^{l} d^{m}\mid l \in \mathbb{N} \wedge m \in \mathbb{N}^{+} \wedge w \in\{a, b\}^{*} \wedge |\left.w\right|_{a}=l+m\right\} \operatorname{with} \...

I'm looking at the reccurrence $$T(n) = T(n/2) + T(n/3) + n,$$ which describes the running time of some unspecified algorithm (base cases are not supplied). Using induction, I found that $T(n) = O(n\...

Suppose we have a total ordering over elements $a_1,a_2, ..., a_n$ be a list of unique numbers, and hence there is a total ordering of them $a_{i_1}<a_{i_2}<...<a_{i_n}$ which we don't know. ...

What do you exactly mean by changing memory map and clearing memory map?

Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$ My approach was to ...

It keeps on giving 0 as the result... Here is the code: puts "Hello" puts "Enter number:" num1 = gets puts "Enter second number:" num2 = gets puts "1. Addition\n2. Subtraction\n3. Multiplication\...

Let's say we have $L_1$ which is a regular language and $L_2$ which is not. I understand that if $L_1 \cup L_2 = \Sigma^*$ then $L_1 \cup L_2$ is a regular language. Does that implicitly mean that ...

I want to configure my nginx server that capable to serve static images files from.both react and node how can I setup the configuration

Given a directed graph G and a starting vertex $v$ and a cutoff weight $w$, I want to find a simple walk with net weight < $w$ that visits as many nodes as possible. Currently, I have a recursive ...

• You need to look up a person’s address given her name from a list of names and addresses. • Develop an algorithm to describe this process. • Using the algorithm developed above, write a ...

While learning Median of Medians algorithm i came across the following lemma ; "For any recurrence of the form $T(n)<=T(an)+T(bn)+O(n) $, if $(a+b)<1$ the reccurence will solve to $O(n)$" (...