Search Results

Search found 70 results on 3 pages for 'eskay'.

Page 2/3 | < Previous Page | 1 2 3  | Next Page >

• reservoir sampling problem: correctness of proof

  - by eSKay

  This MSDN article proves the correctness of Reservoir Sampling algorithm as follows: Base case is trivial. For the k+1st case, the probability a given element i with position <= k is in R is s/k. The probability i is replaced is the probability k+1st element is chosen multiplied by i being chosen to be replaced, which is: s/(k+1) * 1/s = 1/(k+1), and prob that i is not replaced is k/k+1. So any given element's probability of lasting after k+1 rounds is: (chosen in k steps, and not removed in k steps) = s/k * k/(k+1), which is s/(k+1). So, when k+1 = n, any element is present with probability s/n. about step 3: What are the k+1 rounds mentioned? What is chosen in k steps, and not removed in k steps? Why are we only calculating this probability for elements that were already in R after the first s steps?

  Read the article

• not able to use g++ from Fedora

  - by eSKay

  $ yum list | grep gcc arm-gp2x-linux-gcc.i686 4.1.2-11.fc12 @fedora arm-gp2x-linux-gcc-c++.i686 4.1.2-11.fc12 @fedora gcc.i686 4.4.3-4.fc12 @updates libgcc.i686 4.4.3-4.fc12 @updates avr-gcc.i686 4.4.2-2.fc12 updates avr-gcc-c++.i686 4.4.2-2.fc12 updates compat-gcc-34.i686 3.4.6-18 fedora compat-gcc-34-c++.i686 3.4.6-18 fedora compat-gcc-34-g77.i686 3.4.6-18 fedora compat-libgcc-296.i686 2.96-143 fedora gcc-c++.i686 4.4.3-4.fc12 updates gcc-gfortran.i686 4.4.3-4.fc12 updates gcc-gnat.i686 4.4.3-4.fc12 updates gcc-java.i686 4.4.3-4.fc12 updates gcc-objc.i686 4.4.3-4.fc12 updates gcc-objc++.i686 4.4.3-4.fc12 updates mingw32-gcc.i686 4.4.1-3.fc12 fedora mingw32-gcc-c++.i686 4.4.1-3.fc12 fedora mingw32-gcc-gfortran.i686 4.4.1-3.fc12 fedora mingw32-gcc-objc.i686 4.4.1-3.fc12 fedora mingw32-gcc-objc++.i686 4.4.1-3.fc12 fedora msp430-gcc.i686 3.2.3-3.20090210cvs.fc12 $ gcc works fine on .c files but fails on .cpp files saying: $ gcc: error trying to exec 'cc1plus': execvp: No such file or directory g++ fails saying: $ g++: Command not found. What should I do to be able to compile C++ files?

  Read the article

• How do I detect overflow while multiplying two 2's complement integers?

  - by eSKay

  I want to multiply two numbers, and detect if there was an overflow. What is the simplest way to do that?

  Read the article

• How is counting sort a stable sort?

  - by eSKay

  Suppose my input is (a,b and c to distinguish between equal keys) 1 6a 8 3 6b 0 6c 4 My counting sort will save as (discarding the a,b and c info!!) 0(1) 1(1) 3(1) 4(1) 6(3) 8(1) which will give me the result 0 1 3 4 6 6 6 8 So, how is this stable sort? I am not sure how it is "maintaining the relative order of records with equal keys." Please explain.

  Read the article

• Does Java support dynamic method invocation?

  - by eSKay

  class A { void F() { System.out.println("a"); }} class B extends A { void F() { System.out.println("b"); }} public class X { public static void main(String[] args) { A objA = new B(); objA.F(); } } Here, F() is being invoked dynamically, isn't it? This article says ... the Java bytecode doesn’t support dynamic method invocation. There are three supported invocations modes : invokestatic, invokespecial, invokeinterface or invokevirtual. These modes allows to call methods with known signature. We talk of strongly typed language. This allows to to make some checks directly at compile time. On the other side, the dynamic languages use dynamic types. So we can call a method unknown at the compile time, but that’s completely impossible with the Java bytecode. What am I missing?

  Read the article

• Memory allocation in case of static variables

  - by eSKay

  I am always confused about static variables, and the way memory allocation happens for them. For example: int a = 1; const int b = 2; static const int c = 3; int foo(int &arg){ arg++; return arg; } How is the memory allocated for a,b and c? What is the difference (in terms of memory) if I call foo(a), foo(b) and foo(c)?

  Read the article

• Time complexity of Sieve of Eratosthenes algorithm

  - by eSKay

  From Wikipedia: The complexity of the algorithm is O(n(logn)(loglogn)) bit operations. How do you arrive at that? That the complexity includes the loglogn term tells me that there is a sqrt(n) somewhere. Suppose I am running the sieve on the first 100 numbers (n = 100), assuming that marking the numbers as composite takes constant time (array implementation), the number of times we use mark_composite() would be something like n/2 + n/3 + n/5 + n/7 + ... + n/97 = O(n) And to find the next prime number (for example to jump to 7 after crossing out all the numbers that are multiples of 5), the number of operations would be O(n). So, the complexity would be O(n^2). Do you agree?

  Read the article

• How to speed up calculation of length of longest common substring?

  - by eSKay

  I have two very large strings and I am trying to find out their Longest Common Substring. One way is using suffix trees (supposed to have a very good complexity, though a complex implementation), and the another is the dynamic programming method (both are mentioned on the Wikipedia page linked above). Using dynamic programming The problem is that the dynamic programming method has a huge running time (complexity is O(n*m), where n and m are lengths of the two strings). What I want to know (before jumping to implement suffix trees): Is it possible to speed up the algorithm if I only want to know the length of the common substring (and not the common substring itself)?

  Read the article

• reservoir sampling problem

  - by eSKay

  This MSDN article proves the correctness of Reservoir Sampling algorithm as follows: Base case is trivial. For the k+1st case, the probability a given element i with position <= k is in R is s/k. The probability i is replaced is the probability k+1st element is chosen multiplied by i being chosen to be replaced, which is: s/(k+1) * 1/s = 1/(k+1), and prob that i is not replaced is k/k+1. So any given element's probability of lasting after k+1 rounds is: (chosen in k steps, and not removed in k steps) = s/k * k/(k+1), which is s/(k+1). So, when k+1 = n, any element is present with probability s/n. about step 3: What are the k+1 rounds mentioned? What is chosen in k steps, and not removed in k steps? Why are we only calculating this probability for elements that were already in R after the first s steps?

  Read the article

• How do functional programming languages work?

  - by eSKay

  I was just reading this excellent post, and got some better understanding of what exactly object oriented programming is, how Java implements it in one extreme manner, and how functional programming languages are a contrast. What I was thinking is this: if functional programming languages cannot save any state, how do they do some simple stuff like reading input from a user (I mean how do they "store" it), or storing any data for that matter? For example - how would this simple C thing translate to any functional programming language, for example haskell? #include<stdio.h> int main() { int no; scanf("%d",&no); return 0; }

  Read the article

• Effects of changing a node in a binary tree

  - by eSKay

  Suppose I want to change the orange node in the following tree. So, the only other change I'll need to make is in the left pointer of the green node. The blue node will remain the same. Am I wrong somewhere? Because according to this article (that explains zippers), even the blue node needs to be changed. Similarly, in this picture (recolored) from the same article, why do we change the orange nodes at all (when we change x)?

  Read the article

• How to read formatted input in python?

  - by eSKay

  I want to read from stdin five numbers entered as follows: 3, 4, 5, 1, 8 into seperate variables a,b,c,d & e. How do I do this in python? I tried this: import string a=input() b=a.split(', ') for two integers, but it does not work. I get: Traceback (most recent call last): File "C:\Users\Desktop\comb.py", line 3, in <module> b=a.split(', ') AttributeError: 'tuple' object has no attribute 'split' How to do this? and suppose I have not a fixed but a variable number n integers. Then?

  Read the article

• How to represent a Towers of Hanoi problem using a graph?

  - by eSKay

  I am not able to figure out how the graphs shown here are constructed? For example, what does this graph represent? "Nodes are distribution of discs", but I will only have one disc of size a. So, what does node aa represent? I know the answer would be simple, but I cannot figure it out at the moment.

  Read the article

• Why does forward declaration not work with classes?

  - by eSKay

  int main() { B bb; //does not compile (neither does class B bb;) C cc; //does not compile struct t tt; //compiles class B {}; struct s { struct t * pt; }; //compiles struct t { struct s * ps; }; return 0; } class C {}; I just modified the example given here. Why is that the struct forward declarations work but not the class forward declarations? Does it have something to do with the namespaces - tag namespace and typedef namespace? I know that the structure definitions without typedefs go to tag namespace. Structures are just classes with all public members. So, I expect them to behave similarly.

  Read the article

• How is 6 trits equal to 9.5 bits?

  - by eSKay

  This reddit thread says 6 trits ~ 9.5 bits. How is 6 trits ~ 9.5 bits?

  Read the article

• How is schoolbook long division an O(n^2) algorithm?

  - by eSKay

  Premise: This Wikipedia page suggests that the computational complexity of Schoolbook long division is O(n^2). Deduction: Instead of taking "Two n-digit numbers", if I take one n-digit number and one m-digit number, then the complexity would be O(n*m). Contradiction: Suppose you divide 100000000 (n digits) by 1000 (m digits), you get 100000, which takes six steps to arrive at. Now, if you divide 100000000 (n digits) by 10000 (m digits), you get 10000 . Now this takes only five steps. Conclusion: So, it seems that the order of computation should be something like O(n/m). Question: Who is wrong, me or Wikipedia, and where?

  Read the article

• Efficiently storing a list of prime numbers

  - by eSKay

  This article says: Every prime number can be expressed as 30k±1, 30k±7, 30k±11, or 30k±13 for some k. That means we can use eight bits per thirty numbers to store all the primes; a million primes can be compressed to 33,334 bytes "That means we can use eight bits per thirty numbers to store all the primes" This "eight bits per thirty numbers" would be for k, correct? But each k value will not necessarily take-up just one bit. Shouldn't it be eight k values instead? "a million primes can be compressed to 33,334 bytes" I am not sure how this is true. We need to indicate two things: VALUE of k (can be arbitrarily large) STATE from one of the eight states (-13,-11,-7,-1,1,7,11,13) I am not following how 33,334 bytes was arrived at, but I can say one thing: as the prime numbers become larger and larger in value, we will need more space to store the value of k. How, then can we fix it at 33,334 bytes?

  Read the article

• How to sort in-place using the merge sort algorithm?

  - by eSKay

  I know the question is too open. All I want is someone to tell me how to convert a normal merge sort into an in-place merge sort (or a merge sort with constant extra space overhead). All I can find (on the net) is pages saying "it is too complex" or "out of scope of this text". "The only known ways to merge in-place (without any extra space) are too complex to be reduced to practical program." (from here) Even if it is too complex, can somebody outline the basic concept of how to make the merge sort in-place?

  Read the article

• How do char arrays work in C?

  - by eSKay

  #include<stdio.h> int main() { char a[5]="hello"; puts(a); //prints hello } Why does the code compile correctly? We need six places to store "hello", correct?

  Read the article

• Is using a FSM a good design for general text parsing?

  - by eSKay

  I am reading a file that is filled with hex numbers. I have to identify a particular pattern, say "aaad" (without quotes) from it. Every time I see the pattern, I generate some data to some other file. This would be a very common case in designing programs - parsing and looking for a particular pattern. I have designed it as a Finite State Machine and structured structured it in C using switch-case to change states. This was the first implementation that occured to me. DESIGN: Are there some better designs possible? IMPLEMENTATION: Do you see some problems with using a switch case as I mentioned?

  Read the article

• How to use parallel execution in a shell script?

  - by eSKay

  I have a C shell script that does something like this: #!/bin/csh gcc example.c -o ex gcc combine.c -o combine ex file1 r1 <-- 1 ex file2 r2 <-- 2 ex file3 r3 <-- 3 #... many more like the above combine r1 r2 r3 final \rm r1 r2 r3 Is there some way I can make lines 1, 2 and 3 run in parallel instead of one after the another?

  Read the article

• How does git save space and is fast at the same time?

  - by eSKay

  I just saw the first git tutorial at http://blip.tv/play/Aeu2CAI How does git store all the versions of all the files and still be more economical in space than subversion which saves only the latest version of the code? I know this can be done using compression but that would be at the cost of speed, but this also says that git is much faster (though where is gains the max is the fact that most of its operations are offline). So, my guess is that git compresses data extensively it is still faster because uncompression + work is still faster than network_fetch + work Am I correct? even close?

  Read the article

• How does dereferencing of a function pointer happen?

  - by eSKay

  Why and how does dereferencing a function pointer just "do nothing"? This is what I am talking about: #include<stdio.h> void hello() { printf("hello"); } int main(void) { (*****hello)(); } From a comment over here: function pointers dereference just fine, but the resulting function designator will be immediately converted back to a function pointer And from an answer here: Dereferencing (in way you think) a function's pointer means: accessing a CODE memory as it would be a DATA memory. Function pointer isn't suppose to be dereferenced in that way. Instead, it is called. I would use a name "dereference" side by side with "call". It's OK. Anyway: C is designed in such a way that both function name identifier as well as variable holding function's pointer mean the same: address to CODE memory. And it allows to jump to that memory by using call () syntax either on an identifier or variable. How exactly does dereferencing of a function pointer work?

  Read the article

• What exactly is a reentrant function?

  - by eSKay

  Most of the times, the definition of reentrance is quoted from Wikipedia: A computer program or routine is described as reentrant if it can be safely called again before its previous invocation has been completed (i.e it can be safely executed concurrently). To be reentrant, a computer program or routine: Must hold no static (or global) non-constant data. Must not return the address to static (or global) non-constant data. Must work only on the data provided to it by the caller. Must not rely on locks to singleton resources. Must not modify its own code (unless executing in its own unique thread storage) Must not call non-reentrant computer programs or routines. How is safely defined? If a program can be safely executed concurrently, does it always mean that it is reentrant? What exactly is the common thread between the six points mentioned that I should keep in mind while checking my code for reentrant capabilities? Also, Are all recursive functions reentrant? Are all thread-safe functions reentrant? Are all recursive and thread-safe functions reentrant? While writing this question, one thing comes to mind: Are the terms like reentrance and thread safety absolute at all i.e. do they have fixed concrete definations? For, if they are not, this question is not very meaningful. Thanks!

  Read the article

• How do I find the median of numbers in linear time using heaps?

  - by eSKay

  Wikipedia says: Selection algorithms: Finding the min, max, both the min and max, median, or even the k-th largest element can be done in linear time using heaps. All it says is that it can be done, not how. Can you give me some start on how this can be done using heaps?

  Read the article

< Previous Page | 1 2 3  | Next Page >