I have a CS degree from a respectable CS department. I got straight A's in my major and never crammed for a CS test. I am sure I could have answered these questions in 1997. Today, I can answer the first two questions. I think I can get partial credit on the third. I believe I knew the fourth once. I don't even remember what bipartite means [see edit below]. And that's with having implemented a topological sort within the last few years.
I would like to believe that if I came across a problem where knowing this material would help solve the problem, some part of my brain would activate and put me in the position of "Oh, I know I don't know this anymore" and I'd go look it up. Vs "not knowing what I don't know" and just bumbling along ignorantly.
I guess this is a long-winded way of saying I'm glad to have a CS degree and I think it puts me a leg up over software developers who haven't studied CS, but I'm still not sure how applicable these questions are to most developers.
Edit: On most exams I've taken, the fifth question would have been asked like this: A bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; i.e. U and V are each independent sets. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. Describe an algorithm that determines if a graph is bipartite.
Frankly, asking the question either way is what I would call prejudicial. What is a scenario in which bipartite graphs occur, and why not ask how that would be dealt with?
Any n-dimensional grid (sometimes called a "Manhattan space") is a bipartite graph. You may find it useful that no odd-length cycles can exist in such a graph.
There are many reasons why you would want a maximal matching. In my case I was working on a distributed system prototype that needed to match block requests my users to cache servers. This is a maximal matching from cache servers who have these blocks available to users requesting blocks.
I would like to believe that if I came across a problem where knowing this material would help solve the problem, some part of my brain would activate and put me in the position of "Oh, I know I don't know this anymore" and I'd go look it up. Vs "not knowing what I don't know" and just bumbling along ignorantly.
I guess this is a long-winded way of saying I'm glad to have a CS degree and I think it puts me a leg up over software developers who haven't studied CS, but I'm still not sure how applicable these questions are to most developers.
Edit: On most exams I've taken, the fifth question would have been asked like this: A bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; i.e. U and V are each independent sets. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. Describe an algorithm that determines if a graph is bipartite.