All Questions

2
votes
1answer
60 views

Determine number of values less than mean in one pass through list

The problem statement is as follows: Can we determine precisely the number of elements less than the mean in a list $A$ of $n$ numbers in only one pass through the array (starting at $A_1$ and ...
0
votes
0answers
36 views

prove that the language is not context free language

Prove that the language $\{a^i b^j c^k $ $|$ $i>j>k \geq 0\}$ is non context free language without using the pumping lemma. we could use some helpful facts to solve the question: $A$ is a ...
-2
votes
0answers
25 views

how do i fix this. the total amount is still zero after running the program [closed]

this is my coding👇👇 include include using namespace std; int main() { string name, address, category; int unit, float amt; ...
1
vote
1answer
21 views

Closest k points - performance on large lists

Very similar to this Problem formulation: Given a list $L$ of n points with GPS coordinates and a second list $Q$ of $m$ points, find the $k$ (let's say 3) closest points on $L$ for each element on $...
1
vote
0answers
40 views

Delivering to two or more locations in one go while respecting deadlines?

Assume that I have a business where people can place product orders. Each order must be delivered within a time limit, say $x$ minutes. I need 15 minutes to make each product. However, multiple ...
0
votes
1answer
22 views

Understanding the Linear speedup theorem and how strong it is

Let $k \in \mathbb{N} $ and define the language $L = \{ n,m | n^k = m \}$ Consider a (deterministic) TM deciding $L$ then it has to compute $k$'th power which will take $f(|n|+|m|) + h(k)$ time in ...
1
vote
2answers
29 views

Proving that a specific grammar is ambiguous

How can I prove that the following grammar is ambiguous: $$ A \to AA\mid B \\ B \to aBb\mid ab $$ I tried finding a string that can be derived in two different ways, but to no avail.
1
vote
1answer
12 views

Determine image of hypercube under linear map

Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
2
votes
2answers
33 views

Interpretation of this regular expression: (1*0*)*

Do the values of the two * inside the ( ) need to remain unchanged for every repetition of ( )? For example, 110011001100 is part of this language set, but 1100100010 isn't? Or can the values of the ...
2
votes
0answers
18 views

Yao's minimax lemma for Monte Carlo algorithms

In the query complexity model, we define $R(f)$ as the bounded-error query complexity of $f$. It is said that Claim. we can find two hard distributions over the 0- and 1-inputs of $f$ respectively, ...
1
vote
1answer
29 views

How does the cpu know which process to wake?

In general, my understanding is: the cpu is executing a process/thread until either it is interrupted, the scheduler kicks it out, or it's waiting for something else (I/O for example), when it's put ...
0
votes
1answer
27 views

whether an algorithm terminates or not after a finite number of steps

I was reading some documents on web about finiteness property of an algorithm where it is mentioned that "The algorithm must always terminate after a finite number of steps." Does it mean that any ...
1
vote
0answers
20 views

Time complexity: Using linear programming to solve a system of linear equations

As far as I know, most direct methods for solving linear systems of equations have time copmlexity $O(n^3)$ (where $n$ is the number of variables), with the few methods being faster having huge ...
0
votes
1answer
45 views

Operations making non-context-free languages regular [on hold]

If $A$ is a non-context free language, is $A^*$ a regular language? If $A$ is a non-context free language and $B$ is a regular language, is it possible that their concatenation is a regular language?
0
votes
1answer
29 views

can anyone tell what programing languages use for writing parallel program [closed]

i have heard we can use c, c++ and fortran in order to write parallel program but there is any other languages that i can use to write parallel program. And if it is then what library should i use ...
0
votes
0answers
28 views

Prove $\mathsf{DSPACE}(\log \log \log n) = \mathsf{DSPACE}(1)$

There is a similar question here . Instead of proving $\mathsf{DSPACE}(\log \log \log n) = \mathsf{DSPACE}(1)$, the link attached is trying to prove $\mathsf{DSPACE}( o( \log \log n)) = \mathsf{DSPACE}...
1
vote
1answer
32 views

How to prove that {<M1, M2> : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?

My idea is to find a turing machine which recognizes this language in $\log N$ space, could anyone give me some clue on how to find such turing machine?
2
votes
0answers
11 views

How to prune branches in a branch-and-bound solution for Flow Shop Scheduling?

I am implementing a Branch-and-Bound algorithm to find the optimal solution for the Flowshop Scheduling Problem, but I am stuck on the optimization phase, here is a rundown of the problem and what I ...
0
votes
0answers
9 views

Validating req.params with express validator [closed]

If you use check('') it targets the req.body, how can we validate the req.params? I'm trying to make sure the ID entered in the url is valid.
0
votes
0answers
11 views

Tools to simulate active stereo vision algorithms [closed]

I would like to simulate and experiment with various active stereo vision algorithms. Lets say I have a laser that can project a point or line beam onto some 3D geometry (which I have in the form of ...
0
votes
0answers
20 views

Height of a node in a binary tree [closed]

How do I calculate the height of a node in a binary tree, with a function that returns void. Most code examples I've seen return an integer from the height function. I'd need to solve for this ...
0
votes
0answers
16 views

What is the output of the program if the values are passed by value and-result and name?

I just want to make sure I'm doing this correctly. The first part is asking what the output is if the values are pasted by value-result and address of z[w] is computed at the time of the call. I got: ...
0
votes
0answers
29 views

Quicksort with Hoare's Partition Algorithm

I've came across Hoare's partition algorithm in Cormen. After analysis I think that the algorithm isn't working as I expected. Let's suppose that we've array [4,3,2,1], then in my opinion partition ...
-1
votes
0answers
46 views

Approximation Algorithms

Atleast give the reason for downvoting.I am crying. vijay vazirani -approximation algorithms I am trying to understand max sat approximation algorithm from https://doc.lagout.org/science/0_Computer%...
0
votes
0answers
53 views

How to find the minimum number of states of a deterministic finite automaton accepting a given language [duplicate]

Let $L$ be a language over $\Sigma$. And $\Sigma = \{0,1\}$ is a set of input alphabets. $L = \{ w \mid w \in \Sigma^*, \text{ where $w$ is a string with numbers of 0s divisible by 3 and number of ...
-1
votes
0answers
64 views

Do you agree with the following claim: Why (not)? [closed]

"We should rewrite database systems such that they execute transactions in a serial manner." It might seem to be a subjective question but apparently it is not, there is a right choice, it is an exam ...
2
votes
1answer
39 views

Why do OS and DBMS have their own synchronisation mechanisms, when OS can alone do it and it sits at the bottom of DB?

I know that synchronization is important in the OS, but why do we need a separate topic synchronization and concurrency in the DBMS? The OS concentrates on program synchronization while the DBMS ...
0
votes
0answers
44 views

How to find the length of maximum subarray sum in segment tree query?

Problem: Given an array with size$\ n $: for each$\ a[i] $, it denotes the value of the house. You are given the task to build the wall that saves the house that is not exceed$\ w $ length. What is ...
0
votes
1answer
31 views

Crafting a Context Free Grammar

I'm trying to figure out the intuition on creating a CFG in my head. I understand the idea of Grammar rules akin to "onions" with various layers throughout. For example, I was working on a problem ...
-2
votes
0answers
15 views

Machine Learning [closed]

Can anyone tell me what is the error. the Log_model does not accept the text reveiw as string. ValueError: could not convert string to float: 'Drinks were bad, the hot chocolate was watered down and ...
0
votes
0answers
19 views

sklearn text review [closed]

THE ERROR is ValueError: could not convert string to float: 'Drinks were bad, the hot chocolate was watered down and the latte had a burnt taste to it. The food was also poor quality, but the service ...
17
votes
6answers
8k views

Can we generate random numbers using irrational numbers like π and e?

Irrational numbers like $\pi$, $e$ and $\sqrt{2}$ have a unique and non-repeating sequence after the decimal point. If we extract the $n$-th digit from such numbers (where $n$ is the number of times ...
3
votes
2answers
121 views

Is the empty problem (or its complement) Karp reducible to any problem in NP?

I'm currently following a course on Complexity Theory, and whilst studying, I came across a rather counterintuitive statement: If $\textbf{P}=\textbf{NP}$, the following holds: For every $A \in \...
1
vote
0answers
16 views

A term for a set of vertices with a small set of neighbors

Given a graph $G(V,E)$ ans a subset $S\subseteq V$, define $N(S) = $ the set of neighbors of $S$. Is there a standard term for a subset $S\subseteq V$ for which $|N(S)|\leq |S|$? Is there a standard ...
0
votes
0answers
23 views

Total bits required for a direct-mapped cache

I'm taking a course in computer architecture in which the main reference is the Computer Organization and Design by Patterson and Hennessy. I came across an example which I couldn't grasp its answer: ...
0
votes
0answers
10 views

Unknown code Inquiry [closed]

Does anyone know what this code is and what it converts to in text? qaid=199646&qubaid=22551&qid=41263&slot=8&checksum=96fe3ab9eb49e6df7b1887fd9fff59a6&sesskey=F46Dv04rYW&...
3
votes
1answer
63 views

Stacking things of different thickness to approximate desired thickness

I have $N$ objects of different thickness. Is there an algorithm to determine which of those objects should be stacked on each other to get as near to a desired thickness as possible? (I don't want to ...
1
vote
0answers
30 views

Finding a path with a smallest product

Let $G$ be a graph whose edges have integer weights between 1 and 255. What is an efficient algorithm for finding a path between two vertices $s,t$, such that the product of weights on the path is ...
2
votes
1answer
39 views

Algorithm for identifying correct subset

My raw data is composite, but for simplicity sake let's say they consist of three elements. One might consider a sample set thusly. ...
2
votes
1answer
30 views

Construct a decidable set $B$ such that $B \neq A_w$ for any $w \in \Sigma^\star$

I've been stuck on this problem for a while. Any hints would be appreciated! Let $A \subseteq \Sigma^\star$ be decidable. Given $w \in \Sigma^\star$, define $$A_w = \{x \in \Sigma^\star\:|\: \langle ...
0
votes
0answers
18 views

Finding an optimal machine assigning

I have $m$ machines and $n$ jobs. Each machine has a load capacity. Each job can be only handled by either one or two machine, and each job takes some time to finish. After it finished, new jobs can ...
1
vote
0answers
13 views

Can Expectation-Maximization algorithm with batch update diverge?

I am using EM to uncover a continuous hidden variable $z$ (E-step), then maximizing the model prediction (M-step) with parameters $\theta$. The complete data are $[x,z]$. I can formulate the E-step ...
0
votes
0answers
21 views

Automation selenium java anrerp [closed]

import org.openqa.selenium.By; import org.openqa.selenium.JavascriptExecutor; import org.openqa.selenium.WebDriver; import org.openqa.selenium.WebElement; import org.openqa.selenium.chrome....
5
votes
0answers
53 views

Minimum Number of Edges Added to a DAG to get Unique Topological Order

The question is simple: Given an unweighted directed acyclic graph, $G = (V, E)$, what is the minimum number of directed edges we need to add to $E$ such that the resulting graph $G = (V, E')$ has ...
0
votes
1answer
38 views

Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint

I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative ...
0
votes
0answers
23 views

Looking for an esoteric graph theory algorithm

So I'm sure this is an unusual question for this type of site, but I am to give a talk on algorithms for discrete graphs in a few weeks. It has been specified that the talk is to be on some algorithm ...
-4
votes
0answers
20 views

Its turing machine problem [closed]

!Turing Machine problem]1 [It is a turing machine problem which has to do enumeration. I know to solve normal turing machine but was not able to do this problem
1
vote
1answer
21 views

Implementing a symbol table with a hash table and a stack

I was in class today, in a Language Translations course, thinking about the best way to write a symbol table for a compiler. My professor showed us a hash-table with linked-lists connecting different ...
0
votes
0answers
21 views

real time rfc 4175 video capture from ethernet interface by using ffmpeg [closed]

I try to capture video to my laptop from a camera. The camera interface is ethernet and video is encoded as RFC 4175 (RTP Payload Format for Uncompressed Video) standard. I searched how can I decode ...
3
votes
1answer
59 views

Why is finding minimum number of comparisons to sort $n$ elements so difficult?

In The Art of Computer Programming 2nd Ed, Vol 3, Section 5.3.1 then discuss a function $S(n)$ which is define as: $S(n)$ : The minimum number of comparisons that suffice to sort $n$ elements. ...

15 30 50 per page