# All Questions

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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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){ ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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).
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
1answer
68 views

### Proof that the regular languages are closed under string homomorphism

Where can I find a proof of this? Thanks!
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 ...
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?
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? ...
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: ...

15 30 50 per page
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 37, "mathjax_display_tex": 0, "mathjax_asciimath": 4, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9259008765220642, "perplexity_flag": "middle"}