All Questions
0
votes
0answers
3 views
The relation between privileged instructions, traps and system calls
I am trying to understand how a virtual machine monitor (VMM) virtualizes the CPU.
My understanding right now is that the CPU issues a protection fault interrupt when a privileged instruction is ...
1
vote
1answer
7 views
Express boolean logic operations in zero-one integer linear programming (ILP)
I have an integer linear program (ILP) with some variables $x_i$ that are intended to represent boolean values. The $x_i$'s are constrained to be integers and to hold either 0 or 1 ($0 \le x_i \le ...
1
vote
0answers
22 views
Conditional Probabilities as Tensors?
Is it proper to view conditional probabilities, such as the forms:
P(a|c)
P(a|c,d)
P(a, b|c, d)
...and so forth, as being tensors?
If so, does anyone know of a decent introductory text (online ...
0
votes
0answers
4 views
problem in running libsvm in c [migrated]
Hi I wanted to run libsvm on c
I have scaled my train data and tried to do cross validation to obtain the best parameters but I don't know how to do ... in below I tried to read my scaled train data ...
3
votes
3answers
23 views
Using a computer algebra system to optimize mathematical expressions
This is something I've been wondering for years. Software like Mathematica is great at manipulating expressions into simplified, factorized, and other forms. I'm wondering if there's a way, ...
0
votes
1answer
14 views
Context sensitive question
So, I have a book here, which has an example for context sensitive grammar, and the grammar is the famous $0^n1^n2^n$ , and it has:
$$ \begin{align}
S &\rightarrow 0BS2 \mid 012 \\
B0 ...
0
votes
0answers
23 views
Confusion regarding pointer! [migrated]
I was watching a lecture and got confused at a point when professor said
that ptr=&x denotes a variable ptr assigned the address of the variable x.
And for ...
2
votes
1answer
39 views
Converting math problems to SAT instances
What I want to do is to turn a math problem I have to solve into a Boolean Satisfiability problem and then solve it using a SAT Solver. I wonder if someone knows a manual, guide or anything that will ...
-1
votes
2answers
45 views
The sum of all integers less than n with a zero
For example, if n=14, the output should be 10; n=22, the output should be 30=10+20; n=102, output=(10+...+100)+101+102=5703
In this problem, n is smaller than $10^{18}$ , and the algorithm should ...
4
votes
0answers
35 views
Signal-based Search
This is more of an open-ended information question, but to make it concrete, here's an example problem I have thought up:
Consider an $N\times N$ grid, $N$ odd, and consider that a single chunk of ...
2
votes
1answer
54 views
Proof that fast broadcasts have to target larger cycles first
I am having trouble trying to formulate a simple proof. I can clearly see that what I am trying to prove is correct but to prove it I am not sure what to do.
The problem is a broadcasting problem on ...
0
votes
0answers
11 views
Program in R 3.0.0 [migrated]
I would like know how I can program the Gini Index and Lorenz Curve in the program Rx64 3.0.0.
I have loaded:
data(precip)
precip
gini <- function(precip,unbiased=TRUE, na.rm=FALSE){
...
4
votes
1answer
57 views
Is there an affordable experiment which shows chips can't get much smaller?
If I am correct, chips cannot get much smaller because of Heisenberg's uncertainty principle. My friend and I want to perform an experiment (which is cheap, i.e. doesn't require million-dollar ...
3
votes
2answers
72 views
Please explain “decidability” and “verifiability”
I am trying to (intuitively) understand the two terms "decidability" and "verifiability".
I have done a reasonable amount of searching and going through the various texts I can put my hands on. ...
3
votes
1answer
39 views
Realtime hardware/software versus PC software/hardware, how are these distinct and alike?
This question stems from a few answers and comments on a question I posted in signal processing found here.
I guess I am a little confused. Are there any concrete differences between realtime ...
-1
votes
0answers
23 views
Turing Machine Reduction Proof [closed]
Just wondering how I would exactly go about proving this. I found this problem last night while searching for practice problems for my exam. How would I go about proving that this is either ...
-4
votes
0answers
26 views
Should computer science be part of the KS3 National Curriculum? [closed]
I have created a short survey as part of a project at University. It would be great if you could take the time to fill it in! It is completely anonymous and shouldn't take more that a minute and a ...
1
vote
1answer
61 views
Are all databases reducible to this ultimate abstract database design?
I've designed a few databases in my time, and on more than one occasion the drive to abstract common elements from specific tables has led me to create generic top-level tables which contain those ...
0
votes
0answers
45 views
f(n) output of universal program
I have a question concerning an universal program (goto program). Well, let $f(n)$ be the output of an universal goto program $U$ with input $(n,n)$, where the first $n$ describes the encoding and the ...
1
vote
1answer
49 views
Partial recursive function and Turing machine
The wikipedia article about primitive recursion states that
An equivalent definition states that a partial recursive function is one that can be computed by a Turing machine.
My question is how ...
6
votes
3answers
107 views
Graph Has Two / Three Different Minimal Spanning Trees?
I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal ...
2
votes
1answer
36 views
What is the difference between “definition” and “inductive” in Coq?
In Coq, you can use two different kinds of keywords to do definitions--Inductive and Definition. I do not understand the difference between an inductive and a definition, or when it is appropriate to ...
1
vote
1answer
40 views
Find longest common subsequence in limited space
Given three strings $x$, $y$, and $z$ over an arbitrary finite alphabet, I need to determine their longest common subsequence (LCS).
Example: A longest common subsequence of ...
3
votes
1answer
36 views
Is this simplified consensus problem easier than the original?
There is a famous Consensus Problem in Distributed Computing.
Let's consider and try to find the best possible algorithm for a simplified version of the consensus problem.
Assumptions: a process ...
4
votes
3answers
88 views
Example of a non-context free language that nonetheless CAN be pumped?
So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma).
4
votes
0answers
104 views
Google Code Jam Great Wall Problem
So, Google Code Jam round 1C has just wrapped up, and one of its problems seems rather elusive to me: https://code.google.com/codejam/contest/2437488/dashboard#s=p2
A quick summary of the problem is ...
2
votes
1answer
64 views
Shortest sub-sequence of one string, that's not a sub-sequence of another string
Given two strings $x$ and $y$ over the alphabet $\{A,C,G,T\}$, I'm trying to determine a shortest string $z$ such that $z$ is a subsequence of $x$ and not a subsequence of $y$.
Example: a shortest ...
4
votes
1answer
80 views
Is “Find the shortest tour from a to z passing each node once in a directed graph” NP-complete?
Given a directed graph with the following attributes: - a chain from node $a$ to node $z$ passing nodes $b$ to $y$ exists and is unidirectional. - additionally a set of nodes having bidirectional ...
1
vote
0answers
35 views
Game Theory: Regret Minization
I try to get some intuition behind regrent minization in game theory by reading Learning, Regret minimization, and Equilibria A. Blum and Y. Mansour.
The main problem is I am sort of confused by ...
3
votes
2answers
65 views
MAX 10-SAT Algorithm
The MAX k-SAT problem is:
“Given a set of clauses C1,…,Ck, each of length k, over a set of
variables x1,…,xn, find a truth assignment that satisfies as many of
the clauses as possible.”
I'm ...
1
vote
0answers
29 views
In the Hopcroft-Karp algorithm, what is the purpose of the breadth first search?
In the Hopcroft-Karp algorithm for bipartite matching, I don't understand the purpose of the breadth first search. I think it's used to find a set of vertex disjoint augmenting paths, but I'm not ...
1
vote
0answers
23 views
What is an appropriate global optimization technique for a noisy and expensive function?
I have a function which takes 22 real-valued parameters as input that returns a real value. The function is reasonably fast for low return values (ms/seconds/minutes), but takes much longer ...
-1
votes
0answers
42 views
What are the possible research areas for game developers [closed]
Currently I'm doing research about the significance usage of hashtags on twiter, but I'm a games developer enthusiast and I really want to do research in this area, but I'm having problems to think in ...
4
votes
2answers
80 views
Understanding why the polynomial $p(n) = \sum_{i=0}^{k} a_in^i$ is in $\Theta(n^k)$
Hi I've read this lemma in my book:
Lemma 2.1. Let $p(n) = \sum_{i=0}^{k} a_in^i$ denote any polynomial and assume $a_k > 0$. Then $p(n) \in \Theta(n^k)$
Proof. It suffices to show that ...
3
votes
0answers
38 views
how to represent Sparse Matrices
I have been using Harwell Boeing format, also known as Compressed Column Strorage (CCS) in order to store Sparse Matrices.
Could you please suggest me some other way to store/represent sparse ...
1
vote
0answers
28 views
Solving a variant of interval scheduling problem
I am trying to solve a problem of finding compatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.
I have a ...
1
vote
1answer
66 views
What are the possible research areas for Web programmers
I am Electronics student, and have been into programming for a while - especially the web programming in Django, Python.
Now a days I am thinking to get into the research stuff (in CS) and try it ...
0
votes
0answers
30 views
Pushdown automation where number of letter `a` is at least as twice as letter `b` in the word [duplicate]
I have talked to my friend and he said this is the only place somebody could know how to solve it. It is the only exercise(from around 80) from exam revise I just do not know how to do at all.
Create ...
3
votes
1answer
74 views
Pushdown automation where number of letter `a` is at least as twice as letter `b` in the word
I have talked to my friend and he said this is the only place somebody could know how to solve it. It is the only exercise(from around 80) from exam revise I just do not know how to do at all.
Create ...
-1
votes
1answer
31 views
Reducing from Hamiltonian Cycle problem to the Graph Wheel problem cannot be proved vice versa [closed]
I saw a proof by Saeed Amiri,
We will add one extra vertex v to the graph G and we make new graph G′, such that v is connected to the all other vertices of G. G has a Hamiltonian cycle if and only if ...
1
vote
1answer
26 views
Definition of “K-fairness” with respect to concurrency?
There are definitions of Absolute, Strong and Weak Fairness available across the internet, but I cannot find a definition of "K-Fairness" property for critical section algorithms (also algorithms that ...
0
votes
2answers
44 views
How to convert NFA with null moves to NFA without null moves?
I am converting NFA with $\varepsilon$-moves to the NFA without $\varepsilon$-null moves. I understand that if, there is a $\varepsilon$-move between, $q_i$ and $q_j$, then all edges from $q_j$ have ...
0
votes
1answer
33 views
Confusion related to calculating time complexity
I have some confusion related to calculating the time complexity of this algorithm
opt(i)
for j=i:n
a = f(i,j) + opt(j+1)
end
How is the running ...
4
votes
1answer
67 views
Issues with using greedy algorithm (Interval scheduling variant)
I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.
I have ...
0
votes
1answer
21 views
differance of 2 partial computable algorithm
I have 2 algorithms
Algorithm 1:
if( Condition1(input)==true )
print(input);
else
loop forever;
Algorithm 2:
...
0
votes
1answer
68 views
Proof that the regular languages are closed under string homomorphism
Where can I find a proof of this? Thanks!
-1
votes
1answer
36 views
Complement of halting set is not r.e
suppose we don't know that Halting problem is not recursive.
I want to prove that complement of halting set is not r.e. then we can find halting problem is not recursive.
Can you direct prove that ...
1
vote
1answer
41 views
How to calculate the size of page table
Assuming pages of 4Kbytes and 32-bit addressing, estimate the maximum size of the page table for each process.
I think this is $2^{32}$?
Is there a formula for this?
0
votes
0answers
40 views
What is the purpose of Bayes Nets
I have seen a lot of explanations of what bayes nets are, but I simply cannot wrap my head around their use in code. So here is my three part question.
Am I right in my definition of bayes nets? ...
1
vote
1answer
38 views
How does a program execute with respect to the operating system?
I am reading Operating Systems by William Stallings 6th edition and I came across this text,
Program execution:
...
