Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The software development final exam: Algorithms and Data Structures

daemonology.net

Post reply on HN
Print view View original

61–70 of 208 posts

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

#61

Post by cperciva »

hobbyist wrote: post #60

I wanted to ask this question regarding big O notation. When we say f(n) = O(g(n)) all we mean to say is that f(n) <= c(g(n)) with other constraints. My question is, why do we have an equal to sign, why is f(n) equal to O(g(n)).. they could have made up a new symbol to establish such a relationship... The reason why I think so is because I see equal to as a transitive relationship.. So, if a = b and c = b, then a = c…

Writing f(n) = O(g(n)) is actually bad notation perpetuated by lazy instructors. O(g(n)) is actually a set of functions, and the correct notation is f(n) ∊ O(g(n)).

(If the unicode breaks, that's the is-a-member-of symbol.)

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

#62

Post by clinth »

mquander wrote: post #26
peteretep wrote: post #12

Earlier quoted context omitted.

Then perhaps the author shouldn't be presenting them as practical issues, and claim that people who don't know the answers either shouldn't be programmers, or work in some tiny niche. You read the context article he linked to, right?

Just to get the facts straight, the linked article had this to say: 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. The reader can judge…

> or you're lucky enough to be working within a narrow area where your deficit doesn't matter

This implies that non-algorithmic work is a narrow area. In my experience, it's the vast majority.

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

#63

Post by arethuza »

hobbyist wrote: post #60

I wanted to ask this question regarding big O notation. When we say f(n) = O(g(n)) all we mean to say is that f(n) <= c(g(n)) with other constraints. My question is, why do we have an equal to sign, why is f(n) equal to O(g(n)).. they could have made up a new symbol to establish such a relationship... The reason why I think so is because I see equal to as a transitive relationship.. So, if a = b and c = b, then a = c…

I too was slightly unhappy with an equals sign being used like that, Wikipedia suggests that I was being a bit over-literal and it is considered acceptable:

http://en.wikipedia.org/wiki/Big_O_notation#Equals_sign

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

#64

Post by cperciva »

clinth wrote: post #62
mquander wrote: post #26

Earlier quoted context omitted.

Just to get the facts straight, the linked article had this to say: 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. The reader can judge…

> or you're lucky enough to be working within a narrow area where your deficit doesn't matter This implies that non-algorithmic work is a narrow area. In my experience, it's the vast majority.

You've only seen 1/4 of the exam so far. Sure, there's plenty of software development which doesn't involve fancy algorithms or data structures... avoiding computer architecture, operating systems, mathematics, networking, databases, and distributed systems as well is a bit harder.

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

#65

Post by markmm »

I think mediocre and average programmers can get by without knowing about these concepts, the usual .NET or Ruby guys who need a runtime to wipe up after them because they can't even iterate an array without stepping over the line, or don't understand what a pointer is. Those guys will never work for Google, but they can still earn a buck churning out reams of barely working, slow bloated software.

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

#66

Post by crntaylor »

gargleblaster wrote: post #59
hermannj314 wrote: post #42

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…

I think that question 1 is not well formulated (unless that is the answer he expects). Equality makes only very limited sense for asymptotic notation.

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.

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

#67

Post by DannoHung »

I have a question: These are pretty rudimentary questions and if you have a background in the literature, you could brush up in about an hour or two on most of this stuff (aside from memorizing the catalogue of data structures and algorithms you might find in a text book [which makes me wonder why he's focusing on these questions instead of an understanding of induction, space analysis for an arbitrary data structure, or general Big-O/Big-Omega analysis]), but why don't we actually come across uses for that sort of basic stuff all that often?

I mean, I don't know if what I do is all that specialist, but I spend a lot more time working out far less interesting things about how domain knowledge works than what sort of Data Structure or Algorithm is best for storing it and using it.

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

#68

Post by dscrd »

hermannj314 wrote: post #42

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 shirt between white-collar and blue-collar [figuratively, of course] where I work)

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

#69

Post by alexkus »

crntaylor wrote: post #66
gargleblaster wrote: post #59

Earlier quoted context omitted.

I think that question 1 is not well formulated (unless that is the answer he expects). Equality makes only very limited sense for asymptotic notation.

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.

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

#70

Post by oggy »

gargleblaster wrote: post #59
hermannj314 wrote: post #42

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…

I think that question 1 is not well formulated (unless that is the answer he expects). Equality makes only very limited sense for asymptotic notation.

It's a perfectly sensible question. Knowing that both O(2^n) and O(3^n) are sets, and using the definition of set equality, it asks whether "f in O(2^n)" implies "f in O(3^n)", and vice versa. Only one of the implications holds...
Post reply on HN