Daemonic Dispatches

Software development final exam: Part 1

Algorithms and Data Structures

1. Is O(2^n) equal to O(3^n)? Why?
2. What is the expected run-time of quicksort? What is the worst-case run-time?
3. What is the difference between a binary tree [EDIT: that should be binary search tree] and a B-tree? When and why does this difference matter?
4. Name the heap operations used by heapsort and the asymptotic running time of each.
5. Describe an algorithm that determines if a graph is bipartite.

If you would like me to grade your answers, please send an email to cperciva-exam-part1@tarsnap.com [EDIT: I have now finished marking part 1 answers; please do not send me any more] with your answers to the above questions along with the following two:

• Do you have a degree in a computing-related field? (If yes, from which institution?)
• Are you employed as a software developer?

Please note that the questions are intended to be answered under "exam conditions", i.e., without discussion with anyone else, and without consulting Google, Wikipedia, or other sources. I'm running this as an experiment to see how much basic computer science software developers know, and in what areas, so please don't "cheat".

Part 2 of the exam — computer architecture and operating systems — is now available.