This week's book giveaway is in the Open Source forum.
We're giving away four copies of Programmers Guide to Apache Thrift and have Randy Abernethy on-line!
See this thread for details.
Win a copy of Programmers Guide to Apache Thrift this week in the Open Source forum!

Petros Papatheodoru

Ranch Hand
+ Follow
since Aug 24, 2018
Cows and Likes
Cows
Total received
1
In last 30 days
1
Total given
0
Likes
Total received
0
Received in last 30 days
0
Total given
4
Given in last 30 days
1
Forums and Threads
Scavenger Hunt
expand Ranch Hand Scavenger Hunt
expand Greenhorn Scavenger Hunt

Recent posts by Petros Papatheodoru

Oh ok, so there is no way to add a string literal in the string pool at runtime because the string pool is already full with all the string literals that your program is going to use, even before it has started executing. So in an expressing like this String s = "Cat" , it doesn't make sense to say that the JVM searches the string pool to find IF the literal "Cat" exists, because it is 100% certain that it is already in there and the JVM just has to return a reference to this object. And in the expression String s = new String("Cat"), "Cat" is already in the string pool but the JVM creates a new object outside the string pool and returns a reference to that object. Did I get it now?
2 weeks ago
Hey Paul and Cambell! Thanks for your answers. I know that this information isn't super practically useful but I like knowing what is happening under the surface and as long as string pool is concerned a lot of information exists out there but many times it is contradicting. Paul suggests that:

If you create a new String object like this: String badIdea = new String("Don't do this") then yes, a new String object is created. But no, doing that doesn't affect the string pool at all.

but i recently read an article that was suggesting that String str = new String("Cat"); creates either one string object, if "Cat" is already in the string pool, or 2 string objects if "Cat" is not in the string pool. So what is actually the correct answer? haha. I am inclined to believe that Paul is right although I can't think of a way to test this.

If you create a new String object for example like this: String answer = "Yes, but " + idea then the resulting String object doesn't go into the String pool.

Paul, are you trying to say that string objects that are created with string concatenation do not go into the string pool? If yes then it makes sense, since a StringBuilder is used, but if we just had:  String answer = "Yes, but "; then it would go into the string pool, wouldn't it?
2 weeks ago
Hello! I have some questions about the String pool in Java. Correct me if I am wrong but to my understanding, string pool is a special space in the heap that belongs to the String class and at the start of the program is empty. Whenever we create a string object without the new keyword, the JVM checks inside the string pool to find if such a string already exists and if not, it adds the string literal inside the pool and returns a reference to that string, otherwise it just returns the reference. If we create a string with the new keyword, a new string object is created outside the string pool as well as inside the string pool if it doesnt already exist and the returned reference is that of the object outside the string pool. The reason of the existance of the string pool is because it is faster to return a reference to a string literal already in the string pool that create a new object each time. Do I have my facts straight guys? Also, we say that the concept of the string pool is possible because strings are immutable in Java, but why wouldn't it be possible if strings were not immutable?
2 weeks ago
After analysing again the problem statement, It seems that what was asked was not to find the minimum vertex cover, but to find a combination of vertices that cover all edges (hence the name checkIfAllEdgesAreCovered()), it was not clearly stated. The actual condition is irrelevant to what we were trying to do here though, but it is relevant when it comes to execution times: the graph had a minimum vertex cover consisting of only 4 vertices but the actual solution needed 14 vertices and it took 4.8 hours to finish hehe. What's crazy is that there seems to be an even bigger test dataset given to us, consisting of 77 vertices XD. I thank all of you personaly guys for your help and patience
3 weeks ago
The thing is though that I am not supposed to make any optimazations to the problem in the bruteforce solution. In my mind, I rephrased the problem as try to find all the combinations of k elements from n, for k in range 1 to 34 so googled just that and i found a recursive method that does this. I modified it a bit and added my condition check and I ended up with this little piece of code that seems to be doing the job! For the given input of 34 vertices, it seems to be taking forever to execute(no surprise) but I tried a custom input of 18 vertices and it finds a correct solution(consisting of 9 vertices) in half a second!
3 weeks ago
I am trying to follow you guys since I am a noob so correct me. Piet you suggested a Map<bitcount, List<Long> is this suggestion still relevant? If yes, what would I gain if a had all the longs between 1 and 2^34 - 1in a map based on their bitcount? In your latest reply you mentioned " I generate all subsets of length 1... then all subsets of length 2, etc. How do you do that though haha? Thanks for your patience guys. Also, come tell our teacher that Piet hehe
4 weeks ago
Yes you are right Mike this cannot work since I need to test all of the N elements each time before I increment the size of the subset. It only occured to me once I started implementing it. So, back to nothing
4 weeks ago

Piet Souris wrote:So you are still planning to go the brute force way?

I have some tips that may help ease the coding a little:

What I would do first is to try to reduce the size of the graph a little. Since the relation 'connected' is an equivalence relation, introducing a partition of the graph (into the maximal connected subgraphs), you can do the brute force on these (hopefully) reduced graphs (if the graph is connected, then this would fail, of course).

Also, I stated it before, if the maximal outdegree is 4, then you need at least 34 / 5 = 7 vertices, so there would be no need to investigate smaller subsets.

Lastly: I agree with Mike that using the Longs is a handy way. If you have all the Longs from 1 to 2^34 - 1, then you can create a Map<bitcount, List<Long> easily using the bitCount() method of a Long. To find which bits are set, I would turn my Long into a BitSet and use the method stream().

Happy coding!


Thanks for the tips man! The thing is though that I HAVE to use bruteforce, it is not a choice XD. I guess their point is to make us see the difference between exhaustive search and a smarter greedy algorithm (I had already implemented what you suggested in your last comment ).
4 weeks ago
Wow, the binary observation is so clever, I think i can make it work! So, I will use a byte array of length = N (34) to reprisent the subsets, by filling the array with 1s in the appropriate places (e.g. 01011 is {4,2,1}) . For every subset I generate, I will check if it satisfies the condition and then move on to generate another one, by using the same array, this way I wont have to save all the possible subsets.
4 weeks ago
Sorry, I didn't mention the empty set because it is irrelevant. What I am trying to solve is a graph problem where you have N people and each person has a number of connections with other people. I want to find the minimum vertex cover of the graph, eg. the smallest possible subset of people that together are connected with everyone, this is the condition I was talking about. Yes I know bruteforcing is a terrible solution but I am strictly asked to do it that way. Solving it using 34 for loops cannot be considered since N may vary. The thing that matters here is that I check all the subsets with the same number of elements first (in whatever order) and then increment the number of elements allowed and search again. My current solution does not find the smallest subset by quite a lot, although it finds a solution. Mike, if I understood correctly in the example you provided N was 3 and this algorithm calculates the powerset of the last 2 numbers and then adds the third from the end number to each subset, so an example with N=4 would look something like this : I see many fluctuations of the number of elements in the subset, so I think that this wouldn't work at all.
1 month ago
Hello, so I want to find a way that for a given input number N, the power set of all numbers 1,...,N is calculated. I don't want to store the powerset in memory, neither print or edit it, what i really want to do is check if each subset has a particular property and if not ,move on to calculate another subset and check for this property again. For example if N = 10, I want to start checking the subsets: {1,2,3,...,10} and if none of them satisfies my condition start checking the subsets: { {1,2}, {1,3},...{1,10}, {2,3},...,{2,10},...} and then start checking the subsets that contain 3 numbers and so on... I am basically trying to bruteforce a problem and find the smallest possible subset that satisfies a condition. I just can't think of a way to do it without having N number of for loops XD. I thnk recursion is the answer but I don't really know how to do it . Keep in mind that storing the powerset in memory and then checking each subset is not an option since N can be quite big like 34.
1 month ago
You have been really helpful guys. So, assuming I have to solve 2 exercises and use one main() the code should look like this:
1 month ago
Hello, I would like some advice about how to use the main() method in my programs, and more specifically, what to put in there. Is it better to declare everything static and work like that or is it more preferable to create an instance of the main class and call another non static method and concider the new method as main() ? Also, consider this: I am given a university assignement where I have to come up with 2 algorithms that solve 2 different problems. I am asked to provide only one main method. Should I treat this main method as a merge of what would otherwise had been 2 main methods? For example for the first problem, check the arguments, then go ahead and call some methods of the one class and print the result and then continue to do something simillar for the second problem in the same main method. Or should I create 2 instances for the 2 other classes and call a non method that takes care of everything, for each of the 2 other classes?
1 month ago
Hello, my question is more about programing than java in particular. I want to make a Java program that for given items that have a weight and a cost, fills a knapsack of capacity C with items that have exactly C weight (or as close to C as possible) with the minimum cost possible (each item can be selected only once). I want to use dynamic programing and I am having trouble finding the recursive relation for this problem. I found this article: https://www.researchgate.net/publication/308337819_An_Effective_Dynamic_Programming_Algorithm_for_the_Minimum-Cost_Maximal_Knapsack_Packing but I cant understand the recursive relation and the pseudocode with all this mathematical bs... Can you describe what the recursive relation would be for this problem, or even provide some code? Thanks is advance!
2 months ago
Hello everyone! I have the following question concerning generics in Java. Let's say that I want to generify a class(let's call the class MainClass) that has functions that use instances and functions of another class I made(let's call the other class Song). Inside Song there are methods such as        int getID() etc. If I have a method inside MainClass that uses the getID() like that: then I have to cast heap(array of T objects) to be a (Song) in order to use the method. Isn't the whole purpose of generifying the ability to put different kind of items in the class? This method will not work with nothing but Songs. Is there a solution to that and if not please explain to me what am I missing XD
5 months ago