0
votes
0answers
1 views

Applications of min spanning trees

What are the significant applications of minimum spanning trees? After doing some research online and in several textbooks, I have found three real-world applications: Building a connected network. ...
0
votes
0answers
5 views

Separability of the nearest power of two function

I have a function $f$ given by $f(x)=nearest\ upper\ power\ of\ two\ of\ x$ For example, $f(5)=8$ and $f(2)=2$. Are $f(x \wedge y)$ and $f(x+y\mod{N})$ separable over some operator. For example, ...
0
votes
0answers
18 views

Learning to program in C [on hold]

I have about a month to become proficient at programming in C. I wonder if anybody could recommend some worksheets/exercises that get progressively harder so I can practice and learn. Many thanks!
-1
votes
0answers
12 views

Asymptotic runtime of Apriori and Fp Growth

What is the asymptotic runtime of apriori and fp growth? I have been searching from on internet for a week for results but have been unable to find any proper reference.
0
votes
0answers
15 views

How to conduct time complexity analysis for an implemented algorithm [duplicate]

Main task In my bachelor degree's thesis I've developed an algorithm for recommender systems which uses personalized PageRank with some particular features as nodes. In the recommender systems' ...
-2
votes
0answers
11 views

What's time complexity of this algorithm for “Work Break”? [duplicate]

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
-2
votes
0answers
23 views

Cascading Two DFA's [on hold]

How do we cascade two DFA's M1(Q1,S1,R1,F1,G1,qI1) and M2(Q2,S2,R2,F2,G2,qI2) such that the output of M1 is used as the input of M2 and the output of M2 is the output of the cascaded machine M? How ...
1
vote
1answer
131 views

Deciding if a finite automata accepts strings of any length

Question is you're given a DFA. Give an algorithm which tells you whether strings of all lengths $n\in \mathbb{N}$ are acceptable or not. What I doing was, I have algorithm to count the number of all ...
3
votes
3answers
321 views

What is the notation for bounding running time in worst case with concrete example resulting in that worst case running time

I know that Big O is used to bound worst case running time. So an algorithm with running time $O(n^5)$ means its running time in worse case is less than $n^5$ asymptotically. Similarly, one can say ...
3
votes
2answers
56 views

Difference between weak and strong AI

I'm trying to understand the difference between weak and strong AI. For an example, let's say we would pass the turing test - would it show strong AI or weak AI then? I don't believe that this is ...
-1
votes
0answers
11 views

OpenCV: How to focus camera only on required area [on hold]

I want to detect the face using VJ's algorithm in OpenCV and it's working fine, but I want to focus only on the region where face is detected not any other thing form the video stream.
2
votes
1answer
18 views

Check whether it is possible to turn one BST into another using only right-rotations

Given two binary search trees T1 and T2, if it is possible to obtain T2 from T1 using only right-rotation, we say that T1 can be right-converted to T2. For example, given three binary search tree T1, ...
3
votes
1answer
24 views

Can coq express its own metatheory?

I'm learning about language metatheory and type systems, and am using coq to formalize my study. One of the things I'd like to do is examine type systems that include dependent types, which I ...
4
votes
1answer
13 views

Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data

So in biology (DNA sequences), sequence alignment is a generalization of longest common subsequence where an alignment of two sequences is scored typically with a linear function of how many spaces ...
3
votes
1answer
33 views

What is the definition of a $\Pi_1$-sentence?

What is meant when somebody says that a problem can be expressed as a $\Pi_1$-sentence? I know that for the arithmetical hierarchy, a $\Pi^0_1$-sentence is a sentence of the form $\forall n_1\forall ...
-1
votes
0answers
7 views

Proving number of internal nodes in the subtree rooted at any node x of Red Black trees

Reading Lemma 13.1 from the book Introduction to Algorithms, 3rd Edition To prove: A red black tree with n nodes has height at most 2 lg(n+1) First it attempts to prove : the subtree rooted at any ...
-2
votes
0answers
9 views

Help with linked list [migrated]

As i have had no formal education with computer science, please pardon if my question seems trivial. I was reading on linked lists, and the only good source i could find was one from stanford ...
3
votes
1answer
26 views

Converting generalized NFAs to NFAs

I came across generalized nondeterministic finite automata (GNFAs) in Sipser's Introduction to the Theory of Computation. These are automata where transitions are labelled with regular expressions, ...
-4
votes
1answer
37 views

Linear-time algorithm for solving a set of inequalites

We have a set $A$ of $n$ distinct numbers. We want to determine for all $x,y,z \in A$ whether the following relations hold. $$ x+y>z\qquad x+z>y\qquad y+z>x $$ Anyone could describe ...
0
votes
2answers
42 views

Show that the language of words with even sum of positions of a letter is regular

Let $\Sigma=\{a,b\}$, and let $S(a)$ be sum of the positions of $a$ of string $S$. I want to prove $$L=\{S\in \Sigma^{*} \mid S(a)=0(\bmod 2)\}$$ is regular. What I was thinking is to do somehow keep ...
3
votes
0answers
35 views

Algorithms that are similar to Dynamic TIme Warping

Dynamic time warping (DTW) is an algorithm in time series analysis for measuring similarity between two temporal sequences which may vary in time or speed. Here are some explanations of DTW: Dynamic ...
-4
votes
0answers
34 views

SLR(1) and LALR(1) in given grammar [on hold]

Infact i ran into multiple choice question in recent exam on Compiler Course. Suppose T1, T2 is created with SLR(1) and LALR(1) for Grammar G. if G be a SLR(1) Grammar which of the following is TRUE? ...
0
votes
1answer
26 views

Grammars: is there some connection between non-terminals $S$ and $S'$?

Given a grammar such as the following, does $S'$ have some special meaning or does it just denote another non-terminal like $B$, $A$, $P$, $Q$ etc.? $$\begin{align*} S &\to aBS'\\ B ...
1
vote
0answers
34 views

What is regular about regular languages? [duplicate]

I am new to automata theory. I am well aware of the definition of regular language in automata, that is "a language is called a regular language if some finite automaton recognizes/accepts it" [MS]. ...
4
votes
1answer
68 views

Complexity of Linear Diophantine equations

My question is simply, can linear Diophantine equations be solved in polynomial time? Specifically, I am looking at equations of the form $a_1 x_1+a_2 x_2 + ... + a_n x_n = k$, where $a_i,x_i,k$ are ...
1
vote
2answers
34 views

Why comparison is dominant time consumption for comparison-based sorting algorithms? [duplicate]

Comparison-based sorting algorithms does a number of different operations to accomplish the sorting, why comparisons are the dominant time consumption? While I understand the standard analyses of ...
1
vote
0answers
13 views

Probability Game Question [migrated]

I am new to probability. I am trying to solve the following problem. In a game, probability of winning the game is $w$ & losing the game is $l$ & probability of game continuing is $(1 - w - ...
-1
votes
0answers
35 views

What are the advantages and disadvantages of a larger word size?

I'm doing a sample exam paper and there is this question: What are the advantages and disadvantages of a larger word size? Thinking of advantages, the only one that comes to my mind is that we ...
-3
votes
0answers
23 views

Solve Recurrence Equation Problem [duplicate]

I ask this question before, and someone put it as duplicate. i dont know why no one can answer some question, mark question as duplicate. please be kind and let others to know from others. link of my ...
0
votes
0answers
12 views

Vehicle Routing Frameworks in Python [on hold]

Are there any frameworks like optaPlanner or VRP in python out there (preferably on an apache license) which give solutions for Vehicle Routing Problems and/or Traveling Salesman Problem with Profits. ...
0
votes
1answer
37 views

Can/Do multiple processes run simultaneously on a multi-core system?

I understand context switches and threading on a single core system, but I'm trying to understand what happens in a multi-core system. I know multiple threads from the same process can run ...
2
votes
0answers
21 views

Scalable quantum computation vs Uncertainty Principle

What does it means for a Quantum Computer to be scalable? I see a zero sum game between Quantum physics measurement being unpredictable and Quantum computing being scalable (and classically ...
3
votes
0answers
56 views

Solve Recurrence Equation Problem [duplicate]

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n\,.$$ Any nice solution would be highly appreciated. My solution is to substitute $n=3^m$, ...
1
vote
2answers
49 views

NP-hardness of an optimization problem with real value

I have an optimization problem, whose answer is a real value, not an integer such as vertex cover and set cover. Therefore, the decision version of my problem is given an input and a real value $r$. ...
1
vote
1answer
22 views

Neural Network Weights per input nodes

Sorry, I'm really new to neural networks and this question is probably pretty obvious. If you have any resource that can help clarify these concepts to me it would be much appreciated. The way I ...
4
votes
0answers
45 views

How to avoid cascading resizes when resizing hash tables?

With conventional collision resolution methods like separate chaining and linear/quadratic probing, the probe sequence for a key can be arbitrarily long - it is simply kept short with high probability ...
-2
votes
0answers
14 views

Alpha Beta Pruning in Special Case [on hold]

I'm so glad that ask my first question on this site. I ran into a question that so nice. it said: we have a Tree (Main Fig) and we know minimum value is 1 and maximum value is 15. in which ordering ...
0
votes
1answer
24 views

tightest upper bound on binary search tree insertion? [on hold]

The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced What will be the tighter upper bound on this,will it become O(logn) I have read that ...
-4
votes
0answers
36 views

How can I compute the joint distribution of this Bayesian network?

We have a Bayesian Network that A to D is Boolean variable. we want to calculate the probability which C and D be True and A be false. my answer sheet calculate the last result and is 0.0424. any ...
3
votes
0answers
81 views

Sorting with gaps

Suppose we have a directory containing $N$ files whose names are numerals, but not necessarily contiguous numerals. Let's say for concreteness that each file contains an email message, each of which ...
10
votes
2answers
236 views

Is computation expression the same as monad?

I'm still learning functional programming (with f#) and I recently started reading about computation expressions. I still don't fully understand the concept and one thing that keeps me unsure when ...
-1
votes
0answers
20 views

NFU, MFU, LRU Page-Replacement Algorithm Finding Frame To Replace

Could anyone help me with the order of replacing frames? Assuming the frames goes this way Page - Frequency Used - Age P1 - 1 - 2 P2 - 1 - 1 P3 - 1 - 3 Age is the "Queue" of the Pages when they ...
0
votes
0answers
53 views

Running time of an algorithm which is using an array [on hold]

Currently learning how to get running time of an algorithm and slightly confused at my answer (unsure if its right). I have the following: ...
0
votes
0answers
10 views

How to calculate the complexity of Uniform Binary Search algorithm [duplicate]

I was studying the Uniform Binary Search algorithm authored by Donald Knuth which is an optimization of the classic Binary Search algorithm. Can someone explain the complexity analysis for Uniform ...
9
votes
7answers
2k views

How to simulate a die given a fair coin

Suppose that you're given a fair coin and you would like to simulate the probability distribution of repeatedly flipping a fair (six-sided) die. My initial idea is that we need to choose appropriate ...
5
votes
2answers
66 views

Exponential-size numbers in NP completeness reduction

In the proof of Theorem 4 in [GS'12], the authors reduce an instance of PARTITION to their problem. Therefore, they create for each element $a_i$ in the instance of PARTITION a number $2^{c \cdot ...
-5
votes
0answers
38 views

program to print a series which result in zero [on hold]

write a program in c that takes in input any digit N(1<=N<=9)and print all the possible series starting from 1 and ending in N with either "+" or "-" in between the digits so that the resultant ...
4
votes
1answer
53 views

Algorithm to find most nodes in distinct cycles

I am trying to design a program where people trade objects within a fixed set of objects. They offer a single product, and designate a set of products they are willing to accept for that product. ...
0
votes
0answers
5 views

Newly built computer refuses to show anything on the monitor [migrated]

First off, sorry if I'm posting in the wrong area, first time user of this site. Mother Board:Maximus VII Hero RAM: Trident 8GB(2x) GPU: ASUS DirectCU II CPU: Intel i7 4990k Power Supply: EVGA ...
-2
votes
0answers
23 views

Which one is now more trendy software for data analysis either R or Python? [on hold]

Which software should I prefer to learn in this current situation for data analysis either R or Python?

15 30 50 per page