"If you can't answer the majority of the questions on these four papers, and you're working or intend to work as a software developer, you should ask yourself why — most likely you're either you're missing something you really should know, or you're lucky enough to be working within a narrow area where your deficit doesn't matter." [1] I'm a self-taught front end web developer who didn't have a traditional computer s…
The software development final exam: Algorithms and Data Structures
91–100 of 208 posts
Re: The software development final exam: Algorithms and Data Structures
#92Earlier quoted context omitted.
It is perfectly well formulated. The notation O(f(n)) denotes a set of functions. The question is asking if the two sets O(2^n) and O(3^n) are the same set.
I think the OP is looking for a bit more of an answer than a simple Yes/No.
[1] Calculation, if you prefer.
Re: The software development final exam: Algorithms and Data Structures
#93Re: The software development final exam: Algorithms and Data Structures
#94Re: The software development final exam: Algorithms and Data Structures
#95I love clever algorithms, and really enjoyed algorithm and data structure classes at university. However, despite having worked for over 20 years as a programmer in several software-intense companies (big and small) in the telecommunications and VoIP field, I have almost never had a need to know the answers to these questions. In fact, it was the second biggest surprise for me when starting out as a programmer after…
Speaking of cartesian product, did you ever wrote a huge database query that you had to optimize through smart usage of join methods, indexing structure, caching (eg materialized views), decisions like subqueries versus joins versus procedural code etc.?
Did you ever had to pick a library collection -- not implement your own hashmap or tree, but just select the ideal implementation -- to allow optimal searches in a given dataset?
If answer='Y' to any of these, then you needed that knowledge, and I guess you do in a regular basis. The thing about CS theory is that it structures and formalizes these problems so they can be precisely analyzed; used as basis for further inventions and improvements; reliably predict the result of some design choice, etc. You have some empirical knowledge of things like computational complexity, but having formal knowledge would often allow to replace hunches with objective certainty, or arrive to the optimal answer to some problems much quicker and more reliably.
At least that's the theory. ;-)
Re: The software development final exam: Algorithms and Data Structures
#96Re: The software development final exam: Algorithms and Data Structures
#97Earlier quoted context omitted.
why is f(n) equal to O(g(n)).. they could have made up a new symbol to establish such a relationship... It is an equality relationship why would they need a new symbol? f(n) = O(g(n)) .. n^2 = O(n^2) and n = O(n^2), so n = n^2 which is not making any sense You are right it doesn't make any sense. Try n^2 = O(Selection_sort(n)),O(Bubble_sort(n)) = O(Selection_sort(n)), n^2 = O(Bubble_sort(n)). Nice and transitive the…
It's not an equality relationship. If it was an equality relationship it would be transitive. But as your parent points out, you have n=O(n^2), n^2=O(n^2) but not n=n^2, so transitivity doesn't hold. Another way to see that the relationship can't be equality: the left hand side is a function, the right hand side is a set of functions. Two things from different classes can't be equal. The relationship is simply set me…
Re: The software development final exam: Algorithms and Data Structures
#98I have no educational training in computer science, but I work as a software developer. I could not answer any of those questions, literally 0 out of 5. 1. Is O(2^n) equal to O(3^n)? Why? I have absolutely no idea what that means. But I did have to answer this question: why does the application crash? "Oh...that's because the developer that was pontificating yesterday about how heap operations behave asymptotically f…
Hmm, does all this imply that a blue-collar IT-workers' class is rising? When I was working during the summers at construction sites in my youth, I noted that everybody all the time complained about the impractical decisions the engineers and architects had made, and grumbling that they had to be there to fix them. Would they have been happier if they wouldn't have been needed at all? (disclaimer: I tend to change my…
Not my best writing ever but that round's already downrange. Plus there's an excellent response from Alex Feinberg in the comments.
Re: The software development final exam: Algorithms and Data Structures
#99This is the interesting bit "on each paper, at least four of the five questions relates directly to material I have needed to know during my time working on Tarsnap, " Most software jobs are far more distant from CS that Colin's. And more power to him for working fulltime on something that leverages his knowledge. (spoken as someone who spent a decade doing glue-random-apis-together-and-bill -by-the-hour enterprise s…
Re: The software development final exam: Algorithms and Data Structures
#100"If you can't answer the majority of the questions on these four papers, and you're working or intend to work as a software developer, you should ask yourself why — most likely you're either you're missing something you really should know, or you're lucky enough to be working within a narrow area where your deficit doesn't matter." [1] I'm a self-taught front end web developer who didn't have a traditional computer s…
https://class.coursera.org/algs4partI-2012-001/lecture/index
He covers all the questions in this, except the last one regarding graphs.