I don't know if I'm inept at writing code or something but it took about about 4 days straight to write a working Red-Black tree from scratch I think 3 of those days was debugging and refining the delete/remove method. I think most of the time in debugging was making sure the rotations were doing what I expected and being the correct colours
Also it's about 95 lines long with comments, 70 without, if I was to put the red traversal into a separate method it would reduce the number of lines to 35, is improving readability. When writing data structures I assume I target efficiency but for general coding I should target readability?
In retrospect I should have just used an AVL tree but writing the red black forced me to do a huge amount of debugging and new approaches whereas past coding has been kind of straight forward.
Hmm, I keep on writing most Dynamic Programming solutions recursively, they look so elegant. I assume this is probably bad when dealing when large volumes of data are involved? Anyone have tips on how to think of DP in an iterative manner or just solve it recursively then translate to an iterative approach or should I assume that machines have enough memory to deal with a recursive stack?
Modern computers are so powerful that you shouldn't concern yourself with running out of memory or such until it causes a problem. Ignore performance until performance is a problem.
This is the key to success, even when performance is really really important. The Googles, Twitters and Facebooks of the world all made their sites work first. Then after they got success, they worked on performance. Remember the Twitter fail whale? It was a thing because Twitter was garbage code. They worried about performance later, and now people don't even remember they used to suck.
Hmm, I keep on writing most Dynamic Programming solutions recursively, they look so elegant. I assume this is probably bad when dealing when large volumes of data are involved? Anyone have tips on how to think of DP in an iterative manner or just solve it recursively then translate to an iterative approach or should I assume that machines have enough memory to deal with a recursive stack?
I too really like elegant-looking recursive solutions.
Almost all of the time (unless you're specifically designing for fuckhuge data sets) you can rely on having enough stack space - and in fact, most modern compilers can "unroll" basic head and tail recursion algorithms so that the actual code is iterative anyways, so don't really worry about it.
One thing to be wary of is that elegant-looking recursive solutions can still be pretty bad for certain problems; the best example is the naive recursive algorithm for Fibonacci numbers, where you wind up calculating each lower number a bunch of times. For those, learn about memoization and how to recognize when it'll come in handy.
I try to avoid recursion wherever possible unless it's really just not worth it, or I know roughly the space needed beforehand. I don't really like to trust random PCs on being as good as mine.
I try to avoid recursion wherever possible unless it's really just not worth it, or I know roughly the space needed beforehand. I don't really like to trust random PCs on being as good as mine.
The worst computer you can expect someone to actually still be using is about the level of what we had in college. That's Pentium 4, Core Solo, AMD Athlon level with gigs of RAM. I mean, just look at the Steam Hardware Survey. What could you possibly be recursing that will cause trouble for such a computer?
Modern computers are so powerful that you shouldn't concern yourself with running out of memory or such until it causes a problem. Ignore performance until performance is a problem.
This seems to fall into line with the "don't optimise early" and getting your solution down first, I should always keep that in mind.
One thing to be wary of is that elegant-looking recursive solutions can still be pretty bad for certain problems; the best example is the naive recursive algorithm for Fibonacci numbers, where you wind up calculating each lower number a bunch of times. For those, learn about memoization and how to recognize when it'll come in handy.
This was the difficulty I was coming up against. I did a Knapsack problem in 3 lines which were super easy to read and I came up with quite quickly. I tried doing the Memoization method but it took me quite a while to make a working solution (it's also crazy hard to read and I usually go over the top to make readable code). I guess it requires practice in getting use to reading a bunch of operations and calls within array calls and assignments).
I think it's crazy that the Algorithms course I did this semester only had 1 lecture on dynamic programming yet I've needed it for every programming competitions since first year.
I try to avoid recursion wherever possible unless it's really just not worth it, or I know roughly the space needed beforehand. I don't really like to trust random PCs on being as good as mine.
The worst computer you can expect someone to actually still be using is about the level of what we had in college. That's Pentium 4, Core Solo, AMD Athlon level with gigs of RAM. I mean, just look at the Steam Hardware Survey. What could you possibly be recursing that will cause trouble for such a computer?
99% of the time it doesn't really matter, but occasionally I've managed to achieve an overflow with huge datasets. .NET isn't particularly lightweight either so it's a bit easier to manage a SO with its larger frames.
That being said you can also just increase the call stack size of course, but if I can just avoid doing that with little effort than I'll just do that.
In my case I'm prepping for intern-ship interviews where they seem to be looking for strict memory constraints in solving a problem. It's really different from interviews the last few Veterinary positions where I would usually know more than the person trying to employ me (seriously my old profession is fucked, if you're more knowledgeable and capable you're less likely to be hired or accept earning less).
With every big company I've interviewed with for some reason they always ask me DP type questions. I've also been told by more experienced interviewers (from those companies) that DP questions tend to make bad interview question. So they are kinda annoying, but you still need to be prepared for them.
Learning how to write for mobile. Starting with Android, only time I've felt as if Java's forced object orientation made sense to use.
As a side benefit I'm picking up XML and JSON which should really have been included in my Databases course (ontop of MySQL).
Feels really weird to pay attention to the UI as I code however the Material design specifications are really useful. It seems obvious but making everything scalable and having the ability to make every object relative to everything else makes things easy. (The design is very similar to what I had messed around with on Polymer).
Also having a touchscreen laptop makes the emulator natural.
The standard Android Studio kicks the shit out of Eclipse I'm switching over to the developer's (IntelliJ) general Java IDE.
Also learned the pain of dealing with current times, Gregorian Calendar, Julian Calendar.
I hope the iOS utilities are as developer friendly / straightforward when I eventually get a handle on Android.
Learning how to write for mobile. Starting with Android, only time I've felt as if Java's forced object orientation made sense to use.
As a side benefit I'm picking up XML and JSON which should really have been included in my Databases course (ontop of MySQL).
Feels really weird to pay attention to the UI as I code however the Material design specifications are really useful. It seems obvious but making everything scalable and having the ability to make every object relative to everything else makes things easy. (The design is very similar to what I had messed around with on Polymer).
Also having a touchscreen laptop makes the emulator natural.
The standard Android Studio kicks the shit out of Eclipse I'm switching over to the developer's (IntelliJ) general Java IDE.
Also learned the pain of dealing with current times, Gregorian Calendar, Julian Calendar.
I hope the iOS utilities are as developer friendly / straightforward when I eventually get a handle on Android.
I agree, I'm so sad that I have to use eclipse for school
What don't you like about eclipse? I've been using it for ~3 years now and I've had very little trouble with it, especially in the new distrobutions, then again I've really only used eclpise and visual C++, so I may not know how much greener the grass is, so to speak. Also, I've done a handful of internship interviews, and dynamic programming is stressed pretty heavily, especially in java. Since java does not have tail-recursion, it can be important especially when working with complex dp problems which can have polynomial recursive solutions to use a memoization approach, and especially iterative. I'm not sure here if you're talking about the better or worse recursive implementations (raw recursive definitions vs. top down recursive + memoization implementation), but for problems, especially knapsack, memoization and array based approaches are what seperates algorithms from being able to handle 50 inputs in fractions of a second to 50 inputs in a few million years, the difference between 2^n iterations and n^2 iterations. Mind you, memory space for the 2^n method is much less, but it also takes a lot of stack space. The memory use of the DP approach can be mitigated by only remembering the most recent calculations, which if i recall correctly can drive down memory use to closer to n (really about sqrt(n^2 + n^2) * 2 which is still O(n^2). Please feel free to correct me on anything you may not agree with, I don't have much industry experience so I'm uncertain as to how often techniques like these are used, this is the knowledge I've gained from research, classes and being a TA at my university.
My experience with Eclipse was that it was sort of a pain to do stuff in. I'm sure that I could figure it out eventually but also its a huge product that I personally find difficult to navigate. NetBeans was okay when I used it but I mostly just like using IntelliJ.
I dislike all GUI IDEs. Visual Studio is the best, but it's still bad.
What bothers me is that they make it possible for your software to fail to build even if 100% of the source code is correct.
For example, you could open Eclipse (or Visual Studio, or PyCharm, or XCode, or KDevelop, etc.) and write a hello world. Then when you press the play button, there is a good chance it won't work! Even if your hello world is perfect, that doesn't matter. There is some setting in one of the bajillion menus in the IDE that is wrong and is preventing your hello world from building and executing.
Fair enough, there were plenty of days in the lab when I had to tell students to just restart eclipse in order to fix their problems. Is there anything else out there that provides the same kind of diagnostic tools, debug functionality and module/plugin support without the added glitchiness?
Fair enough, there were plenty of days in the lab when I had to tell students to just restart eclipse in order to fix their problems. Is there anything else out there that provides the same kind of diagnostic tools, debug functionality and module/plugin support without the added glitchiness?
The command line diagnostic and debug tools are the most powerful available. You just have to learn to use them since there isn't a GUI. The idea of modules and plugins doesn't even exist for the compilers or interpreters you are using are the real deal. They take care of everything.
You might get plugins for your text editor, but that depends on which text editor you choose. Vim, emacs, there are so many choices. Just pick whichever one you like best.
That's the other main problem with IDEs. They combine two programs that have nothing to do with each other. Why should the compiler be joined at the hip to the text editor? By combining them together you hold them both back and restrict choice. By separating them you can use the best possible text editor and the best possible compiler available.
Also, the fact that you had to even ask shows how someone who only uses an IDE doesn't know what's really going on because real development tools are hidden from them.
Here's a good exercise for people who are used to IDEs. Open up a Linux/OSX/UNIX terminal. Without closing that terminal you must write, compile/interpret and execute hello world in ten different programming languages. All the programs just have to print out the words "hello world" in the terminal. All the text editing has to happen in the terminal as well. You can open a browser to do research on the syntax of the different languages.
This isn't even CS1 level. This is something I learned in middle school. But people who have only ever used IDEs can't do this. Hello World isn't just about the code. It's about learning to use the development tools.
Comments
Also it's about 95 lines long with comments, 70 without, if I was to put the red traversal into a separate method it would reduce the number of lines to 35, is improving readability. When writing data structures I assume I target efficiency but for general coding I should target readability?
In retrospect I should have just used an AVL tree but writing the red black forced me to do a huge amount of debugging and new approaches whereas past coding has been kind of straight forward.
I assume this is probably bad when dealing when large volumes of data are involved?
Anyone have tips on how to think of DP in an iterative manner or just solve it recursively then translate to an iterative approach or should I assume that machines have enough memory to deal with a recursive stack?
This is the key to success, even when performance is really really important. The Googles, Twitters and Facebooks of the world all made their sites work first. Then after they got success, they worked on performance. Remember the Twitter fail whale? It was a thing because Twitter was garbage code. They worried about performance later, and now people don't even remember they used to suck.
Almost all of the time (unless you're specifically designing for fuckhuge data sets) you can rely on having enough stack space - and in fact, most modern compilers can "unroll" basic head and tail recursion algorithms so that the actual code is iterative anyways, so don't really worry about it.
One thing to be wary of is that elegant-looking recursive solutions can still be pretty bad for certain problems; the best example is the naive recursive algorithm for Fibonacci numbers, where you wind up calculating each lower number a bunch of times. For those, learn about memoization and how to recognize when it'll come in handy.
I think it's crazy that the Algorithms course I did this semester only had 1 lecture on dynamic programming yet I've needed it for every programming competitions since first year.
That being said you can also just increase the call stack size of course, but if I can just avoid doing that with little effort than I'll just do that.
It's really different from interviews the last few Veterinary positions where I would usually know more than the person trying to employ me (seriously my old profession is fucked, if you're more knowledgeable and capable you're less likely to be hired or accept earning less).
As a side benefit I'm picking up XML and JSON which should really have been included in my Databases course (ontop of MySQL).
Feels really weird to pay attention to the UI as I code however the Material design specifications are really useful. It seems obvious but making everything scalable and having the ability to make every object relative to everything else makes things easy. (The design is very similar to what I had messed around with on Polymer).
Also having a touchscreen laptop makes the emulator natural.
The standard Android Studio kicks the shit out of Eclipse I'm switching over to the developer's (IntelliJ) general Java IDE.
Also learned the pain of dealing with current times, Gregorian Calendar, Julian Calendar.
I hope the iOS utilities are as developer friendly / straightforward when I eventually get a handle on Android.
Also, I've done a handful of internship interviews, and dynamic programming is stressed pretty heavily, especially in java. Since java does not have tail-recursion, it can be important especially when working with complex dp problems which can have polynomial recursive solutions to use a memoization approach, and especially iterative. I'm not sure here if you're talking about the better or worse recursive implementations (raw recursive definitions vs. top down recursive + memoization implementation), but for problems, especially knapsack, memoization and array based approaches are what seperates algorithms from being able to handle 50 inputs in fractions of a second to 50 inputs in a few million years, the difference between 2^n iterations and n^2 iterations. Mind you, memory space for the 2^n method is much less, but it also takes a lot of stack space. The memory use of the DP approach can be mitigated by only remembering the most recent calculations, which if i recall correctly can drive down memory use to closer to n (really about sqrt(n^2 + n^2) * 2 which is still O(n^2).
Please feel free to correct me on anything you may not agree with, I don't have much industry experience so I'm uncertain as to how often techniques like these are used, this is the knowledge I've gained from research, classes and being a TA at my university.
What bothers me is that they make it possible for your software to fail to build even if 100% of the source code is correct.
For example, you could open Eclipse (or Visual Studio, or PyCharm, or XCode, or KDevelop, etc.) and write a hello world. Then when you press the play button, there is a good chance it won't work! Even if your hello world is perfect, that doesn't matter. There is some setting in one of the bajillion menus in the IDE that is wrong and is preventing your hello world from building and executing.
On the command line you do
gcc hello.c
or
python hello.py
or
javac hello.java
java hello
And it works every time.
You might get plugins for your text editor, but that depends on which text editor you choose. Vim, emacs, there are so many choices. Just pick whichever one you like best.
That's the other main problem with IDEs. They combine two programs that have nothing to do with each other. Why should the compiler be joined at the hip to the text editor? By combining them together you hold them both back and restrict choice. By separating them you can use the best possible text editor and the best possible compiler available.
Also, the fact that you had to even ask shows how someone who only uses an IDE doesn't know what's really going on because real development tools are hidden from them.
Here's a good exercise for people who are used to IDEs. Open up a Linux/OSX/UNIX terminal. Without closing that terminal you must write, compile/interpret and execute hello world in ten different programming languages. All the programs just have to print out the words "hello world" in the terminal. All the text editing has to happen in the terminal as well. You can open a browser to do research on the syntax of the different languages.
This isn't even CS1 level. This is something I learned in middle school. But people who have only ever used IDEs can't do this. Hello World isn't just about the code. It's about learning to use the development tools.
$ makeGood enough for the Linux kernel. Good enough for anything.
Man, it is hard to write these makefiles by hand, I know, let's invent automake!
Wow, it is hard to configure automake to build the right make files. I know, let's invent autoconf!
Dang. Autoconf sure is a pain in the ass. I know! Lets....