Live data from Hacker News

The software development final exam: Algorithms and Data Structures

daemonology.net

91–100 of 208 posts

Re: The software development final exam: Algorithms and Data Structures

#91

"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…

damn I didn't know am so lucky for last 35 years or maybe life is different than exams ?

Re: The software development final exam: Algorithms and Data Structures

#92
post #69

Earlier 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.

He is also asking "Why?", i.e., for a proof[1] to back up your Yes/No answer. Seems like a perfectly good question.

[1] Calculation, if you prefer.

Re: The software development final exam: Algorithms and Data Structures

#93
I see a common argument in the comments here. Many of us are saying this is "Computer Science" and not "Software Development". In my opinion, knowledge of the answers to these questions will make you a better software developer. Ofcourse, without knowing any of these, you can still develop software that will work. But if you know answers to these questions (and many other similar computer science questions), you can make smart decisions on how to implement the software you are developing in a more efficient manner.

Re: The software development final exam: Algorithms and Data Structures

#95

I 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…

Did you ever need to write an algorithm to process some large volume of data, and you had to make choices related to performance, e.g. to avoid a combinatorial explosion in some searching problem which trivial implementation would be a full cartesian product of several dimensions of data (i.e. a bunch of deeply nested loops)?

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

#97

Earlier 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…

Ah thanks, I misunderstood which part was being called in to question.

Re: The software development final exam: Algorithms and Data Structures

#98
post #68

I 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…

(Shameless plug) I just wrote about this very thing on Friday: http://mattdeboard.net/2012/10/05/larry-the-software-guy/

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

#99

This 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…

I think you've accurately identified why you could have those gaps. Not that you do have them, but hourly billing enterprise software "scut work" doesn't require a whole lot of CS. I wonder if the stuff on the other side of those APIs did?

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…

Highly recommend this free online course given by Robert Sedgewick from Princeton.

https://class.coursera.org/algs4partI-2012-001/lecture/index

He covers all the questions in this, except the last one regarding graphs.

Post reply on HN