All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
3 views

Finding the minimum value of a subset in a 2D array

Imagine a N by M 2D array of random positive integers and two coordinates (i1,j1), (i2,j2), which represent the upper-left bound and bottom-right bound of a subarray, respectively. Is there a ...
0
votes
1answer
8 views

OS: Why is it necessary to have hardware support for implementing Preemptive Scheduling Strategies?

I think, Preemption can easily be done in kernel mode, where it just have to call the Context-Switch procedure. Also, based on algorithm we can select the new process from the ready queue as well... I'...
0
votes
0answers
5 views

Numerically solving an ode with infinitely many variables of which only finitely many are significant in magnitude

Suppose I have an ode that involves infinitely many variables, with the property that at any given time, only finitely many of them are large enough to be of interest (say $>10^{-10}$). However, at ...
0
votes
1answer
15 views

Interesting Speedup & Amdhal's law problem

I have found a problem on my Computer Architecture textbook which I have some issues with: We have a process which spends its time in the following way: 50% of the time, it executes common ...
1
vote
0answers
19 views

Sorting algorithm for ranking hundreds of Images based on pairwise comparison

I am facing the task of designing an algorithm to rank some hundred of images (around 300). The ranking is to be based on pairwise comparison judged by human (done through Amazon mechanical Turk). I ...
-2
votes
0answers
15 views

Sub routine for an algorithm

The data in the table below has been collected by a teacher at the end of two unit assessments. Produce a subroutine for an algorithm that could be used to count the number of students who achieved a ...
0
votes
2answers
30 views

Does the O(n) algorithm always run faster than the O(n^3) algorithm? Why?

Assuming that the time complexity of the two algorithms A1 and A2 to solve the same problem are O(n3) and O(n) respectively. If you write programs for these two algorithms and run them in the same ...
0
votes
0answers
10 views

Shift Operation with Shifted Bits Greater Than or Equal To the Operand's [closed]

In Computer Systems A Programmer's Perspective (3rd Edition), the author says, "For a data type consisting of w bits, if we shift by some value ...
2
votes
1answer
25 views

When LP solution is ILP solution?

For many discrete problems, it's natural to consider their continuous relaxations. A common case is when instead of $x_i \in \{0, 1\}$ we allow $x_i \in [0, 1]$. In certain cases, the original problem ...
-2
votes
0answers
14 views

Numerical computing Question

Please help. I am studying and going through questions and dont know how to even start this. I would gladly appreciate if someone could walk me through the problem.
0
votes
1answer
24 views

Assign few binary variables to make all polynomials identically zero

I have 50 polynomials $f_i$ over binary variables $(x_1,\ldots,x_{100})$. Also $f_i(0,0,\ldots,0)=0$ for any $i \in [1,50]$. I want to assign few variables so that all $f_i$ will be identically zero. ...
0
votes
0answers
20 views

When do insertions and deletions get enacted in a buffer tree?

Buffer trees are $(a, b)$-trees in which each node in the tree gets an associated buffer for storing operations to be conducted on elements in the tree. While I appreciate the idea of amortizing the I/...
2
votes
1answer
25 views

How do computers *really* work? (at the most basic level)

While learning about computers I will read about RAM and Storage and the CPU, and while these explain the architecture of a computer and how parts of a computer work together, I still don't understand ...
0
votes
0answers
32 views

How much faster are out machines (generally) than Arthur C. Clarke's machine in 1953's “The 9 Billion Names of God”?

In Arthur C. Clarke's short story, "The 9 Billion Names of God", two software/hardware engineers are contracted by a monastery to generate 9 billion string permutations from a 13-character ...
1
vote
1answer
102 views

Compiler Design Question

Consider the following ANSI C code int main(){ Integer x; return 0; } What will be the type of error? a)Lexical, b)Syntax, c)Semantic, d)None According to me, Syntax Analysis phase should detect the ...
1
vote
1answer
45 views

Why do these functions satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n))?

I don't understand what these function are like and why they satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n)). Where is x? \begin{eqnarray} f(x)= \begin{cases} k^{2k}, &x\in(2𝑘,2𝑘+1)&...
-2
votes
0answers
16 views

Create user searching emulator in PERL [closed]

Can anyone help me I want to create user searching emulator on the perl, so what I need perl code whch: 0.Ask me for browser I shall use it must give me text field to input path to my browser I want ...
0
votes
2answers
44 views

Cardinality of sets and strings -> confused

I have a question regarding the cardinality of sets and strings. If $ \Sigma^* $ is empty, the cardinality is 1, because the empty word $ \varepsilon $ is counted. If $ \Sigma^+ $ is empty, the ...
0
votes
0answers
11 views

Correctness of addition in 1's complement number representation

The one's complement representation of integer numbers in computer memory is generally defined as the system prescribes to invert all bits (all but the sign one) of a negative signed number. It didn't ...
-1
votes
0answers
18 views

selection problem with a group of log(n)

the formula of selection problem if we divide to 5 elements in every group : T(n)=T(n/5)+T(7n/10)+O(n) with a group of 5 elements if we divide to log(n) elements I get T(n)=T(n/log(n))+ ? + O(nlog(log(...
0
votes
1answer
29 views

Showing that T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$)

I am doing an exercise which says that this is true: T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$) So I tried to solve it by substitution, but I am getting a non-sense result. So would really ...
-2
votes
0answers
14 views

Download only folder with it content [closed]

help me please I need it downloading only one folder from the site with it all content without above level folders or equal level folders: like this http: //site.com/directory0... directory0N/...
0
votes
0answers
24 views

Implement Immediate Smaller Element problem using Stack

Immediate Smaller Element Problem: Given an integer array arr of size $n$. For each element in the array, check whether the right adjacent element (on the next ...
0
votes
1answer
32 views

Summation and big theta

Can anyone suggest a starter book or website where I can find information and examples of putting functions under summation signs into Big Theta. basic Arihmetic , geometric, Quadratic are fine , but ...
0
votes
1answer
34 views

Finite automaton for all words whose length $n$ satisfies $\operatorname{gcd}(n,504) \geq 6$

I have been working on the following homework question, and I just can't seem to make any progress: Construct a finite automaton having fewer than 36 states that recognizes the language $\{s \in a^* :...
1
vote
0answers
36 views

How to avoid division by zero in UCT formula in Monte Carlo tree search?

In step 2 (expansion) of the Monte Carlo tree search algorithm, one or more child nodes are created, and one node named C is chosen among them. The simulation step is applied to C giving it a score of ...
1
vote
2answers
77 views

Proving that a preorder traversal of a rooted tree can be performed in linear time

Definition: Let $T(V, E)$ be a rooted tree with root $r$. If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$. If $\lvert V \rvert > 1$, let $T_1, T_2, \...
2
votes
0answers
46 views

Words of the same length in a language

Let $L\subseteq\Sigma^*$ be a language, where $\Sigma$ is a set, and let $n\in\mathbb N$. I am wondering if there is some good terminology for $L\cap\Sigma^n$. Of course I could say "the set of ...
0
votes
1answer
20 views

Designing less than and less than or equal operators for Map with value being a Set

I am trying to come up with less than and less than or equals operators for a Map where values are Sets. These are the hints I was able to get from the Professor. ...
0
votes
1answer
41 views

How do I assign homes to hospitals based on locality? (clustering, kmeans?)

I have a large set of $(X)$ hospitals and $(Y)$ homes, where $(Y)$ is much larger than $(X)$, and their respective coordinates. Each hospital can handle any home within a 50 mile radius, and up to 10,...
0
votes
2answers
50 views

Is $n^2 \log n$ in $O (n^2)$ am confused

I graphed the functions and when $n_0$ is greater than $3$, $cg(n)$ is always greater than $n^2 \log n$ so it would seem to me by definition that $m^2 \log n$ is in $O (n^2) $. I tried to prove it by ...
1
vote
1answer
26 views

Constructing a NFA from a regular expression

I have the following regular expression $R=ab^*(\epsilon \cup c) \cup c^*a$ and I want to construct the NFA that accepts languages defined by that regular expression. I started by constructing the NFA ...
-4
votes
0answers
28 views

Prove that $f(L)=L_{\Sigma^*}$

When: $f(L)=\{f(x) | x\in L\}, L\in R$ $L_{\Sigma^*} = \{\langle M\rangle | L(M)=\Sigma^* \}\notin RE$ and $\langle M_{\Sigma^*}\rangle$ is TM that accept straight away. For: $f(\langle M\rangle)=\...
0
votes
0answers
17 views

How do I create a orthagonal projection of Canada from a shapefile in Python? [closed]

I am currently trying to make a orthagonal projection of Canada in order to produce a heat map. I need the projection to be as if Canada was placed on a 3D globe.
1
vote
1answer
34 views

Find the recurrence relation for the following algorithm

The question requests to find the recurrence relation of the following algorithm and solve it using the characteristic equation. \begin{align} &\text{SORT}(A[0\dots n-1])\colon\\ &\quad \text{...
0
votes
1answer
48 views

Could the halting problem in theory be solved for any finite set of Turing Machines?

Suppose there's a program A that decides whether or not every program halts. Then we could construct program B that invokes A and does the opposite. Do I halt? If so, loop. Do I loop? If so halt. That ...
2
votes
1answer
20 views

Fine-grained versioning of entities in programming languages

I have a question related to design, implementation of programming languages. I hope it fits here and apologize if it doesn't. All or most programming languages version modules (aka packages, ...
1
vote
0answers
35 views

Strong NP-completeness of numerical perfect matching

This is a follow-up to post Perfect matching problem, where nir proved weak NP-completeness. Suppose you are given two sets of integers $L$ and $M$ both having $N$ elements. We want to match each ...
1
vote
1answer
167 views

Is this clique algorithm in polynomial time correct or might it have another time complexity?

I came up with the idea finding a k-clique through starting at a small s-clique (like 1-,2- or 3-clique) and use it to find every s+1 Clique iterative. I had some trouble finding the Time Complexity ...
1
vote
1answer
15 views

How to express complexity of two functions considering it is the same in big O notation

I have two functions. a and b. Both have linear complexity O(n). ...
2
votes
0answers
31 views

Does minimumm spanning tree always include the node with highest degree?

I want to know why the distances between nodes in a minimum spanning tree seems to be rooted to the node with highest degree. A bit of context here: I have spatial explicit weighted network that ...
1
vote
2answers
42 views

What is wrong with this proof that proves that 0*1* is not a regular language?

I know why cases 1 and 2 are wrong because our language can have different numbers of 0's and 1's. But I'm not sure how case 3 can be proved wrong for our language. Exercise 1.30: Describe the error ...
-1
votes
0answers
16 views

Powershell : Update License value for remote desktop services in gpedit [closed]

Requirement : after installing remote desktop services in windows machine using powershell, there is a need to configure license server for the same in gpedit. Attempt Taken: We have tried this using ...
-1
votes
0answers
12 views

Powershell : Update Registry value for RDPFileContent by making change in server port to 799 from 3389 [closed]

Requirement: to update registry value i.e. server port for one of the property : RDPFileContent using powershell. Attempt Taken: Tried fetching entire value first of RDPFileContent using get-childitem ...
-1
votes
0answers
5 views

Convert redshift query to mysql query [closed]

I'm using this redshift query now which is working perfectly fine. But due to some reasons I need to convert it into mysql. It gives parent_order_id, product_id and hub_id. ...
0
votes
1answer
30 views

Vertex cover of minimal graph

I'm looking for algorithm that, for given undirected graph $G=(V,E)$, find graph $G'=(V,E')$ with minimal amount of edges that have same vertex cover as G. I mean, vertices $U$ are vertex cover of $G$ ...
2
votes
1answer
21 views

Is there an optimization algorithm that could help match the maximum number clients to servers with constraints?

How do you go about solving the following problem that tries to match the greatest number of clients with servers with constraints? I'm trying to identify an algorithm or simulation that could help me ...
2
votes
1answer
25 views

Show that moving one symbol to the end still makes a regular language

Question For any string $\sigma$ over alphabet $\Sigma$, we define the operation $\texttt{MOVE}$ as following For $\sigma = aw$ ($a \in \Sigma, w\in \Sigma^*$), $\texttt{MOVE}(\sigma)=wa$ This is ...
1
vote
1answer
17 views

Proving using a SAT solver that KB entails D

Suppose you're given this KB: $$KB = (A, A ⇒ B, A ⇒ C, B ∧ C ⇒ D)$$ How would you show using a SAT solver that $KB \vDash D$?

15 30 50 per page
1
2 3 4 5
788