All Questions

1
vote
1answer
13 views

What is an efficient data structure for prefix matching?

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 ...
2
votes
0answers
12 views

Sub-optimal and fast solutions to assignment problem

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 ...
1
vote
1answer
12 views

Algorithm notation between two functions

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 ...
1
vote
0answers
16 views

How do you prove that $A = \{ x \in \mathbb{N} | W_{x} = [0..x]\}$ is a productive set through functional reduction?

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 ...
0
votes
0answers
20 views

Regular expressions java(greedy and non-greedy)

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 ...
0
votes
0answers
10 views

A Simple Random Number Function C++ [on hold]

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 ...
1
vote
1answer
27 views

Halting Problem, Typed Version: A Headache

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 ...
0
votes
1answer
10 views

Simple algorithm to generate a linear extension from partial order set

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.
0
votes
0answers
21 views

What is space complexity of shrinking one array to increase another?

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
votes
0answers
15 views

Protocol deadlock versus Routing deadlock [on hold]

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

Construct a lambda term from a Böhm tree

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 ...
2
votes
1answer
26 views

Bertrand's ballot theorem

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 ...
6
votes
3answers
495 views

Can you prevent a man in the middle from reading the message?

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 ...
0
votes
0answers
32 views

Merging of two increasing binary trees why do we exchange left and right subtree

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 ...
0
votes
0answers
12 views

How can I build an dependency table to prevent NOPS

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 (...
1
vote
1answer
30 views

What is the avantage of having memory mapped I/O?

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?
2
votes
1answer
43 views

Is the Shakespeare Programming Language Turing complete?

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 ...
2
votes
1answer
26 views

All pair shortest path in a tripartite graph

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 ...
1
vote
1answer
31 views

Can there still be infinite recursion if I remove all left recursion?

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 | ...
2
votes
1answer
14 views

Can the pumping lemma for context free languages be extended to any subword?

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 ...
-3
votes
1answer
22 views

Arithmetic Operations - Lambda Calc [on hold]

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

Reduce to Beta Form Verification

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$ ...
2
votes
0answers
15 views

Is there a more commonly-used term for “multi-pivoting”?

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 ...
3
votes
2answers
63 views

Interesting logic problems

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 ...
0
votes
0answers
13 views

WHNF abstraction

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 |...
2
votes
1answer
21 views

Correctness of an algorithm difference between recursive and iteraive

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 (...
0
votes
0answers
13 views

I want to install run pipenve n my computer for working with django framework . I faced this problem. what is the solution? [on hold]

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 ?
-1
votes
0answers
14 views

Reduction to Lambda Normal Form

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

What do the symbols M and N mean in this definition of lambda terms?

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 ...
0
votes
2answers
27 views

No Lambda Normal Form

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 ...
0
votes
0answers
33 views

What time complexity (big o) is this specific web crawler implementation? [on hold]

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 ...
1
vote
0answers
14 views

Updating every element in a Fenwick Tree

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 ...
3
votes
0answers
27 views

What is the current fastest algorithm for finding the maximum common subgraph?

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 ...
0
votes
0answers
58 views

Is C actually turing complete follow up

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. ...
0
votes
0answers
12 views

Which laptop should I buy for artificial intelligence and programming [on hold]

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 ...
0
votes
1answer
19 views

From where does the Fetch Unit get its instructions?

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?
0
votes
0answers
9 views

Iterative deepening traversal (IDDFS without goal node) [on hold]

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,...
1
vote
1answer
17 views

Identifying the Equivalence Classes of a Language with equal number of 10 and 01 strings

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 ...
1
vote
1answer
28 views

Constructing CFG

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,...
0
votes
1answer
54 views

Which word could I use for the Pumping Lemma proof?

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} \...
7
votes
2answers
52 views

The recursion $T(n) = T(n/2)+T(n/3)+n$

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\...
3
votes
1answer
22 views

Random observations of a total ordering, how much they tell us?

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

Changing and clearing memory map [on hold]

What do you exactly mean by changing memory map and clearing memory map?
2
votes
2answers
76 views

Negative simple path NP-Complete

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 ...
0
votes
0answers
9 views

I have a problem with my ruby code for a calculator [on hold]

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\...
2
votes
2answers
33 views

Union of a regular and a non-regular language

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 ...
-2
votes
0answers
8 views

Configuring the nginx server [on hold]

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
3
votes
1answer
19 views

Longest simple walk below a certain weight

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

computer science [on hold]

• 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 ...
1
vote
0answers
29 views

Prove that the upper bound for T(n)=T(an)+T(bn)+O(n) is O(n) [duplicate]

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)$" (...

15 30 50 per page