************************************************************************** * * * The Hitchhiker's Guide to the DWE * * * * Ron Azuma Don't * * V 1.6 Panic! * * last revised August 1993; includes questions * * through the Spring '93 exam * ************************************************************************** ========================================================================== I. Introduction Student: "Isn't this the same test as last semester's?" Prof: "Yes, but it's ok: I've changed all the answers." ========================================================================== This document is primarily intended to be a guide for students who have not yet taken the DWE. It tells what the DWE is, what it covers, how you might prepare for it, and what you may want to do directly before and during the exam. It also provides an appendix listing old DWE problems listed by subject. The goal is to provide future DWE takers with a starting point for their study program and help them avoid some of the mistakes and pitfalls that I fell into while preparing for and taking the DWE. This guide is not officially sanctioned by the Department of Computer Science or the Graduate School, so all statements should be considered my own opinion and not necessarily treated as hard facts. You assume all of the risk of following the suggestions in this guide. So don't sue me. :-) ========================================================================== II. The Basics "The rules of the game, however absurd, cannot be altered by playing that game." - Arthur Koestler ========================================================================== This section briefly reviews what the DWE is and how the exam is created, given, and graded. I include this because in the past, DWE takers were usually not informed of all this information until after the exam. If you already know the score, skip this section. Offered once per semester, the Departmental Written Exam (DWE) is a set of written questions that students take to satisfy the MS comprehensive examination requirement and/or gain admission to the doctoral program. DWE questions are drawn from the nine core classes in our CS program, in contrast to some other universities that base their equivalent test on a student's research areas. DWE questions are usually different in style and substance from final exam questions in the core classes, partly because DWE questions are interdisciplinary, combining concepts from several core classes into one question. Therefore, your grades in the core classes may not correspond with your results on the DWE. The professors write the questions around the middle of the semester and submit them to senior grad students who have already passed the exam. Much of this effort is coordinated by the two graduate students serving on the DWE committee (who must have already passed the DWE at the PhD level). The student volunteers try working the problems and evaluate the questions. Their comments are often incorporated into the final version of the test. By revealing flaws in the wording of the questions and identifying inappropriate difficulty levels, student reviews help "debug" the DWE before it is given. Note: this does not insure flawless questions; it merely provides the mechanism for improving them. The quality of DWE questions depends heavily on the amount of effort the question writers and reviewers are willing to invest into the process. The DWE occurs around the 10th or 11th week of the semester, with typically about 20 students taking it. Generally more students take it in the Spring than in the Fall. The exam itself consists of 9 questions, spread over three days, with three questions offered per day. You are free to use books, notes and other reference materials, except you can't consult with other students. The DWE has no oral section. You have 3.5 hours each day to answer three questions, and you can take the test anytime between the hours of 8am and 4:30pm. (I believe the deadline is now 4:30pm rather than 5pm, since the front desk closes earlier these days.) You must take the test inside Sitterson Hall. (In the past, students were allowed to take the test at home, but a few students abused this privilege by spending extra time on the exam, then used the excuse that they got caught in traffic.) Students label their answer sheets with pseudonyms to preserve their anonymity during the grading process. After all of the answers have been collected, the professors have about two weeks to grade them. Two different professors separately grade all the answers to a single question. Because of the pseudonyms, they cannot bias the grades for or against any student. The professors who grade a question are usually different from the ones who wrote the question. Each question is worth up to 45 points. When finished, the professors compare the marks they gave to each student. If the two grades differ by a large amount (say, more than 8 points), the professors will discuss that student's answers and try to modify the grades to match more closely. Finally, the results are tallied and the professors discuss the results during a Faculty Lunch. To pass at the MS level, a student must score an overall average of at least 50%. To pass at the PhD level, the average must be at least 70% and the student must do particularly well on one or more questions. On borderline cases (say, within +/- 3%), the faculty may change the result in either direction by considering other factors like course grades, ability to do research, statements of support from professors, etc. Results vary considerably from year to year. A typical result may be 40-50% passing at the PhD level, and most of the rest passing at the MS level (see Appendix III). If the test turns out to be a massacre, the faculty may elect to reduce the percentages needed to pass. Examples of this include the Fall '90 and Spring '92 exams. On the Fall '92 test, one person passed with a 60% average! You get two chances to take the DWE. If you want a third opportunity, you must file a petition (which is not always granted). I do not know of anyone who has taken the DWE four times. ========================================================================== III. The Lineup (the 9 core classes) "When a subject becomes totally obsolete we make it a required course." - Peter Drucker ========================================================================== This section lists, in more detail than the course syllabi, the subjects the core classes cover and that you are responsible for on the DWE. Concepts that have commonly appeared in past DWEs are marked with a "<====". This will give you some idea of what you're up against. ******** 122 Algorithms and Analysis ************************************* "For every problem, there is a solution that is simple, neat, and wrong." - H. L. Mencken Comments: As the leadoff batter, 122 is tough to get out. By definition, algorithms can be on just about anything. Therefore, it's important to learn the *techniques* of solving problems, rather than just memorizing solutions of classic problems. A typical 122 DWE problem will ask you to find a "brute-force" way to solve some problem that you've never seen before in your entire life, then find a more intelligent way of solving it that takes less time or space, and then show that your performance estimates are correct by recurrence relations. Towers of Hanoi has been used at least twice so far as the basis of such a problem. If you get stuck on a 122 problem, see if you can sort it or put it into a tree. Then you can use the canonical sorting and graph algorithms to help you. Concepts you should know: * Asymptotics notation (big-Oh) * Proof techniques (especially induction) * Solving recurrence relations * Proving programs correct Show termination on all valid inputs Establish loop invariant Demonstrate that invariant implies correct result * Establishing upper and lower bounds on execution time Decision trees Adversary arguments Reduction * Divide & Conquer philosophy of recursion * Greedy algorithm philosophy * Searching & Sorting Bin search, MergeSort, QuickSort, lots of others O(n lg n) minimum in sorting by comparison of keys * Graph problems -> selected choices from: Kruskal & Prim minimum spanning trees UNION/FIND operations Dijkstra shortest path Graph coloring Traveling salesperson Depth-first and Breadth-first search Bicomponents, strongly connected graphs Graph matching Backtracking Optimal search tree Minmax search, alpha-beta pruning * Other problems -> possibilities include: String matching (brute force, KMP, BM) Strassen matrix multiplication Horner's Rule for polynomial evaluation * Dynamic programming Concepts you can probably gloss over: * Amortized analysis * Probability-based algorithms (eg Monte Carlo) ******** 151 Numerical Analysis ****************************************** "Dear kindly Dr. Pizer, you've got to understand, We all want to be wiser, but it gets out of hand! Our methods are unstable, our errors propogate! We e-ven do our assignments late!" - start of the 151 parody song, sung to the tune of "Gee, Officer Krupke" from West Side Story Comments: Although it bats second, 151 really should be put further back in the lineup because it's a true power hitter. When asked to name the core class they fear the most, most DWE takers will probably name 151. 151 covers lots of material, and most of that is fair game on the DWE. Error analysis is a commonly included topic. The Fall '88 DWE had two of the most godawful 151 problems the world has ever seen, so if you can't do them, don't worry. Almost everyone else couldn't either. Concepts you should know: * The basic problems with computation and numeric representation * Rounding, masking, cancellation * Nonlinear function solvers (Bisection, False position, Secant, Newton-Raphson) * Solving systems of equations (Gaussian elimination, Jacobi & Gauss-Seidel iteration) * Polynomial approximation methods to a set of points (ordinary polynomials, Lagrange polynomials, Barycentric form, Divided difference approaches, splines, linear discrete least-squares, finite Fourier series over equally-spaced tabular points) * Numerical integration methods (Rectangular, Trapezoidal, Simpson's, and composite versions of those) * Solving 1st order ODEs (Euler, Modified Euler, Euler-Heun methods) * Basic linear algebra * Error analysis <==== Generated error (Approximation, representation, arithmetic, bounding generated error of 1st order ODE solvers via Taylor series) Propogated error Vectorized error bounds (Sensitivity, Condition number) Overall error (generated + propogated) * Improved Numerical Methods (Runge-Kutta ODE solver, Romberg integration, Adaptive quadture integration, Aitken acceleration) * Convergence (Linear, quadratic, non-integer, supralinear) Concepts you can probably gloss over: * Pivoting in Gaussian elimination (too tedious) * Adams-Moulton ODE solver (know the order, not the details) * Stability (usually too hard or too easy, but watch for stability being a small part of a question) ******** 181 Theory of Computation *************************************** "Forget computers; it's hard enough getting humans to pass the Turing test." - David Bedno "Yes, it works well in practice, but will it work in theory?" - anonymous Comments: 181 is a class that teaches you to think in perverted ways. Prior knowledge of Godelization helps in dealing with bizarre concepts like feeding programs to themselves. 181 is one subject where the DWE questions are actually similar to those on midterms and finals, since questions about the Chomsky hierarchy, decidability and Turing machines are already sufficiently nontrivial. It's difficult to really know if you got the right answer until the grades come back. A typical 181 problem will ask you to write an expression for some language and classify where it falls inside the Chomsky hierarchy. Another typical problem will modify a basic machine model (eg a TM) and then ask you if that changes the power of the machine in any way. Concepts you should know: * Defintions (relations, functions) * Proof techniques (Induction, Pidgeonhole principle, Diagonalization, Contradiction) * Regular expressions and languages (DFAs, NFAs, equivalence of power of DFAs and NFAs, equivalence between FAs and regular grammars, closure properties, pumping lemma for FAs, Myhill-Nerode method of minimizing DFAs) * Context-Free grammars (Ambiguity, PDAs, DPDAs, equivalence of PDAs and CFGs, closure properties, pumping lemma for CFLs, Chomsky and Greibach normal forms, elimination of left-recursion in CFGs) * Parsing (Top-down vs. bottom-up, LL(k) and LR(k) grammars) * Context-Sensitive Grammars (equivalence with LBAs) * Turing Machines (variations of TMs, "compiling" TMs together, NDTMs, equivalence of TMs and general grammars, Universal TMs) * Limits of computation <==== (Church's Thesis, decidable and acceptable problems, Halting problem, enumerated languages, Rice's theorem, Post's Correspondence Problem) * Complexity <==== (Chomsky hierarchy, P vs. NP) ******** 212 Operating Systems ******************************************* "If I had to do it over again? Hmm... I guess I'd spell 'creat' with an 'e'." - Ken Thompson Comments: OS is a huge subject, but since 212 is only a 1.5 unit class, the area it covers is limited, so 212 is a bit weak to bat in the cleanup spot. Watch out for essay questions, design questions and questions that ask you to evaluate tradeoffs. Recent DWEs seem to assume that distributed systems issues are fair game, although they may not be officially covered in 212. If you haven't taken 243, it may be worth skimming through that material. Concepts you should know: * Virtual Memory (page replacement heuristics, translation buffer, thrashing) * DMA * Scheduling heuristics (optimal, FCFS, SJF, Priority, Round Robin, multi-level queues, etc. Slow-truck phenomenon. Belady's anomaly) * Paging & Segmentation (hybrid methods, locality, working set) * Concurrent processes (Classic producer-consumer model, Banker's alg, Dining Philosophers, mutual exclusion, semaphores, monitors, use of TAS to implement mutual exclusion, Dekker's alg, deadlock and how to avoid it, CPU-bound vs. I/O bound jobs) * Memory usage (Fragmentation, best-fit, worst-fit, first-fit, garbage collection) * Caching (Direct map, associative map, set-associative) * Disk scheduling (FCFS, SSTF, SCAN, C-SCAN, etc.) * Network basics Concepts you can probably gloss over: * Forget about Deitel chapter 15 * Knowledge of security issues is nice, but probably not required ******** 213 Files & Databases ******************************************* "...so the American government went to IBM to come up with a data encryption standard and they came up with..." "EBCDIC!" - from a University of Wisconsin collection of computer/math class quotes Comments: Throw away Date. Get the Elmasri/Navathe text; it's much better. Even though 213 is only a 1.5 unit class, historically one or more questions on just about every DWE is a DB question, giving it an unusual amount of emphasis. You MUST be prepared to draw E-R diagrams, design databases from scratch, and formulate queries -- this kind of DWE problem occurs again and again. Concepts you should know: * Relational databases E-R components and diagrams <==== (entities, attributes, relations, relationship types, entity keys, foreign keys) Designing a database from a description <==== * Records and files Disks (seek times, latency, capacity, double buffers, tracks, cylinders) Hashing (extensible, dynamic, linear) Indexing schemes (primary, secondary, clustering) B-trees * Relational model Relational algebra <==== Relational query languages <==== (Be sure you know the syntax of at least one query language, like QUEL or SQL, the cost of queries and how to rearrange them for efficiency) Weaknesses (Lack of transitive closure without an embedded query language) Relational calculus (equivalence of power of relational calc and relational algebra, dangers of "forall x" expression) Concepts you can probably gloss over: * Some knowledge of network & hierarchical schemes is nice, but usually not needed for the DWE ******** 214 Translators ************************************************* "As part of the conversion, computer specialists rewrote 1,500 programs -- a process that traditionally requires some debugging." - USA Today, referring to the IRS switchover to a new computer system "Never turn your back on a compiler." - Curtis Hill Comments: 214 is the front end of a full-blown compiler class. Generally it is snuck in as half of a DWE problem -- very few DWE problems concern 214 primarily. (Of course, it does happen, such as Fall '91 question #3). Calingaert's book will probably tell you all you need to know about 214, since he usually teaches the class. Concepts you should know: * The overall picture of getting your HL program down to assembly code * Assemblers (tasks, load & go, reusable and reentrant modules) * Macros * Linkers & Loaders * Interpreters * Compilers Lexical phase (tokens, FSM implementation) Syntax phase (parsing, top-down vs. bottom-up, recursive descent parsers, ambiguity, shift-reduce, precedence functions, syntax-directed definitions) Symbol tables (hashing, dealing with variable scopes) Semantic phase Code generation (storage allocation, code optimization heuristics) ******** 216 Digital Logic *********************************************** Hardware, n.: "The part of the computer that can be kicked." Comments: 216 is an oddity: a digital logic class without a lab. Personally, I think learning hardware design without actually building something is like learning how to program without compiling and debugging any code. Historically, 216 material usually got merged with 261 problems on the DWE, so 216 received very little coverage. However, the Spring '90 test reversed that trend with two DWE problems that required significant amounts of 216 material, and since then 216 has been averaging one question per test. This course is a rich field for design questions. Concepts you should know: * Boolean algebra (simplification rules, inversion & duality) * Reduction techniques (Minterm & maxterm formulations, Karnaugh maps) * Components Basic gates (NAND, NOR, NOT, AND, OR, etc.) MSI components (MUXes, decoders, counters, flip-flops, memories, shift registers, PLDs, etc.) * Organizations (Combinatorial vs. sequential, FSMs) * Applications (Adders) * Timing issues (clocking schemes, critical path) * Hazards (fan-in and fan-out) Concepts you can probably gloss over: * Implementation of components via MOS or CMOS * Moore vs. Mealy machines * Asynchronous design ******** 217 Programming Languages *************************************** "APL is a write-only language. I can write programs in APL, but I can't read any of them." - Roy Keir Comments: 217 mostly covers issues relating to procedural languages, and it seems to be a popular topic on old DWEs. Concepts you should know: * Tradeoffs in language design & implementation Expressiveness vs. maintainability vs. efficiency Interpreted vs. compiled * Abstractions Data variables Storage (static, dynamic, hybrids, storage on the stack or in the heap, garbage collection) Scope (static vs. dynamic) Types (type checking, variant records, subranges, strong type-checking, user-defined and abstract data types) Parameter passing (Call by ref, call by value, call by result, call by value-result, call by name. Aliasing problems. Procedures as parameters) Control abstraction Statement level (loops, if-then, while, etc.) Module level (functions, procedures, recursive calls) Exception handling Concurrency (Ada rendezvous, message passing, semaphores, monitors, cobegin & coend) * Functional languages Concepts you can probably gloss over: * Denotational vs. operational semantics * Programming in the large vs. programming in the small (Development environments and tools) * Program reliability & correctness ******** 261 Computer architecture *************************************** The fundamental law of computer architecture: "Good, fast, cheap: pick any two." "If you were plowing a field, what would you rather use? Two strong oxen or 1024 chickens?" - Seymour Cray (on massively parallel architectures) Comments: Although 261 bats in the pitcher's spot, you best not let your guard down. Computer architecture is a huge subject, both in depth and breadth, providing a wealth of ammo to draw on and making comprehensive preparation difficult. It also merges very well with other subjects like operating systems, numerical analysis, and digital logic, making it one of the easiest areas to write an interdisciplinary question in. 261 questions have ranged anywhere from 45 point essay questions to 45 point system design questions to multipart questions that dig deeply into one small area of computer architecture. Good luck. Concepts you should know: * Overall structures Von Neumann Parallel (SIMD, MIMD) Vector processors * Execution and control units Instruction fetch + execution Interrupts Components: IR, PC, MAR, MBR, PSW, etc. Handling branches Microcode, vertical & horizontal Microcode vs. hardwired controllers Nanoinstructions Pipelining RAW, WAR, WAW and branching problems Bit-slice * I/O Bandwidth & latency Architectures (where is I/O attached to? Bus? CPU?) Programmed I/O vs. Interrupt-driven vs. DMA Memory-mapped I/O Interrupts, vectored interrupts Serial vs. parallel * Buses Width, speed Control & arbitration Synchronous vs. asynchronous * Memory Hierarchy: tape, disk, core, cache, registers ROM & RAM, 2.5 D organization Error detection & correction techniques Interleaved memory Caches direct map, associative map, set-associative write-through vs. write back replacement strategies (LRU, FIFO, etc.) Hardware support for virtual memory Von Neumann bottleneck * Arithmetic Sign-magnitude vs. 1's complement vs. 2's complement Adders, multipliers Floating point math Use of "excess #" notation on exponents to allow integer comparisons Exceptions Overflow, underflow, NaN Precision (guard bits, rounding & truncation) * Instruction set design Opcodes & operands, formats, registers available Variable length instructions Addressing modes RISC vs. CISC * System design Amdahl's Law ******** Misc ************************************************************ The DWE assumes you can read and write code in a typical procedural language, like Pascal. It also assumes a degree of mathematical knowledge, including linear algebra and calculus. ========================================================================== IV. Preparation "If you spend too much time warming up, you'll miss the race. If you don't warm up at all, you may not finish the race." - Grant Heidrich ========================================================================== Now that you know what you're up against, how do you get ready for it? We'll discuss that in this section. I believe the best way to prepare is to form a small study group (say, 3-4 people) that starts meeting at the beginning of the semester that you take the DWE. The two reasons for a group are 1) it enforces discipline, since you have to get ready for each meeting and 2) if you've waived any classes, as most of us have, a group lets you talk with someone who actually took the classes you waived to see what was covered and where you may have to do some extra studying. If you start your group at the beginning of the semester, you'll have enough time to allocate a week per class, then have one or two weeks left for synthesis and additional studying. I tried to build both long-term memory and short-term memory by first reviewing one class per week, then all nine classes in one week, and then all nine classes in one day on the Saturday before the exam. Study groups should focus on covering material rather than doing problems. Focusing on problems treats the symptoms and not the disease. You need to work problems also, but those can be done on your own time, rather than group time. Since this is an open-book test, you'll probably want to create an extensive set of notes to help you both when reviewing the material and when you actually work problems, during practice and on the actual exam. What if you have extra time? You might want to know something about each professor's research areas. Professors write the questions, and they tend to write about what they know. A few old DWE questions look like they were inspired by research done here at UNC. Recent examples include Fall '91 question #1 and Fall '91 question #9. ========================================================================== V. Test-taking strategies "When I am working on a problem, I never think about beauty. I think only of how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." ========================================================================== In this section, I offer an assortment of comments, tips and suggestions based on my experiences (and those of others) with the DWE. * If you're a late riser and intend to take the DWE in the afternoon, check to make sure the front desk isn't going to close early. This happened during the Fall '91 exam. Otherwise, you could have less time than expected, or be left holding test sheets with no one to give them to (I don't know what happens then). * Have a decent math text sitting in your office when you take the test. You don't want to lose points just because you forgot some integration method. Do you remember what the derivative of arctangent is? That was required to answer part of question 7 on the Fall '89 exam. * The best thing that can happen when confronted with a subject is that you already know it. The second best thing is that you can look it up... fast! You do not have enough time on this test, so you don't want to waste it leafing through references scattered randomly all over your office floor. Therefore, spend some time before the test getting all your texts and notes organized so you can find stuff quickly when you need it. I also put the page numbers of topics in my notes so I could quickly look them up in textbooks. Corrolary: once you pull out a reference and you're done using it, don't waste time refiling it. Just throw it on the floor -- odds are excellent you won't need it again that day. After you've turned in your answers to the front desk, you'll have plenty of time to clean up your office and reset for the next day. * The day before the test, do something different. See a movie, go to a play, walk around the park, whatever. Clear your mind so you don't get burned out before the exam. At that stage, a few extra hours of studying probably won't do you any good, so it's more profitable to spend them relaxing and making sure you get a decent night's rest before the big day. Similarly, the most important thing to do on the nights before the other two days of the test is to get enough sleep rather than flipping through your notes one more time. * Actually, I'll qualify that last suggestion. It is helpful to do some quick reviewing directly before taking the test (e.g. during the hour before you pick up your packet) so you don't walk into the test "cold." It's the mental equivalent of stretching before you go jogging. But other than that, relax so you don't get burned out. A side effect of this strategy is that, during the three days of the test, you'll have lots of time to catch up on nonacademic things that you've probably been putting off during the semester while preparing for the exam, like doing laundry, cooking meals, cleaning the apartment, fixing the car, etc. * When you take the test, you don't want to be disturbed. Make a "Do Not Disturb" sign and tape it to your office door (the glass part only, please). Turn off your phone by hitting *6 (#6 will restore it). * Use a dark felt tip pen, rather than ballpoint or a pencil. Why? Because the professors will never see your original papers. They will only see *photocopies* of the original, and felt shows up much better than the other two do. Similarly, avoid writing within an inch of the margin on all sides of the paper, or part of your answer may not show up on the photocopy. * On the top of each page of your answers, you're supposed to write your pseudonym, the question number, the page number and the total number of pages in this answer. For example, one header might be: Zaphod Beeblebrox Q9 page 1 of 42 In the past, you did not learn your pseudonym until the first day, but I've heard that now they tell you before you start the test. While you won't know how many pages each answer takes until you've finished answering the question, the rest you can and should write before you even pick up your test packet. It may save only five minutes, but any little bit helps. I've even seen people pre-print special sheets of paper with the inch margins neatly lined and their pseudonym and question numbers typed in. This sounds a bit extreme to me, but if it makes you feel more comfortable, go for it! * Read the WHOLE question before writing down your answer. I remember more than one practice problem where I answered part a) of the question, then read part b) and discovered that what part b) asked completely invalidated my response to part a). * How long should your answers be? You must show enough work to prove to the graders that you didn't just guess the solution, but being too verbose will cost you precious time. My answers averaged 5-7 pages in length, but I left lots of white space on those pages so I'd have enough room to add stuff or make changes later. Occasionally I'd use 9 or more pages in one answer. If your page length starts rivaling War and Peace, maybe you're not approaching the solution correctly. * You may run into a situation where you're really not sure just what the question is asking, or maybe the question doesn't provide enough facts for you to solve it. In both cases, make up some reasonable assumptions, write those assumptions down and proceed from there. State your thought pattern as you go along. Do not assume that the professors who wrote the questions will be available to clarify the situation. What's worse, you may run into a situation where the question is just deeply flawed in some way (such as Fall '91 question #2 and Fall '91 question #8). In those cases, you're just going to have to improvise and write down all your assumptions. People who were fortunate enough to have extra time on the first day gave answers for *both* interpretations of Fall '91 question #2, a case of going above and beyond the call of duty. * What happens when you get the infamous 45 point essay question? You have to treat it somewhat like an English essay question. Sketch out and organize your answer before you write anything down. Explicitly answer all parts of the question: eg, if it asks you to comment on the speed, size, and cost tradeoffs of various types of architectures, clearly indicate in your response where you are dealing with those issues. Make it easy for the grader, because even though this is probably the most important exam you will take here, the professors will *not* put in a proportionally greater effort in grading the test. If they can't follow your train of thought, they'll give up and your score will get massacred. * You have 3.5 hours to solve three problems. That sounds like a lot, but it isn't. You won't have enough time to do everything that you want. So how do you organize your time? Remember that all problems have the same point value. Allocate at least 45 minutes (1 minute for each point) to each problem. If you get stuck on one, move on to another and come back later. Try to save 15 to 30 minutes for double checking at the end. When it's that close to the end, you'll probably get more points by finding and fixing dumb mistakes than in adding more details to existing answers. Use a stopwatch or something to help you keep track of the time. And for God's sake WRITE DOWN your start and stop times somewhere, just in case you forget when you have to turn the test in. That happened to me once when I forget to start my stopwatch, but I had my turn-in time written down, so all was well. * Do not leave an answer blank! Even an incomplete answer will garner some points. Some professors are generous with partial credit, but leaving something blank will earn you a big fat zero no matter who does the grading. If you don't know what the question is asking, make some assumptions. If you can't solve the stated question, solve a subset of the question. If you aren't sure, make an educated guess. Remember that you don't have to ace every question to pass -- but you do have to get above a certain average. Get points wherever you can. How much partial credit will you get? That depends heavily on who does the grading and how closely your assumptions match those of the professors who wrote the question. My experience has been that most professors want to see the question answered as stated (read: as they interpret it), so you may get clobbered if you view the question from a different perspective. There's not much you can do about that, other than giving it your best shot and then hoping for the best. * You may run into one question that you simply can't solve, one that you're sure you got clobbered on. That's ok -- don't let it get to you. Go on and focus on the other questions. Now if you get two or more such questions, then you can start worrying... * Be aware that trick questions may show up (albeit rarely) on the DWE. For example, question #3 on the Spring '89 DWE asked "what operating system modifications the interleaved writing-reading action would require." The correct answer is "none." Also, don't be constrained by real-world concerns in your solution. You're not in the real world. If your answer requires a gigabyte of memory, who cares? It's all on paper anyway, and the solutions often demonstrate a lack of real-world concerns. Pick the simplest way to do something without worrying whether you'd do it that way in industry or not. * Once you get your results back, can you appeal? It has been successfully done, but usually the results are treated as final. I'd only recommend trying it if there's a blatant, obvious error that, if fixed, will get rid of a weakness or change your level of passing. * When you need a break, look through the parody DWE questions that were circulated in early 1990. (I've got a copy, if you don't have them.) They're good for some tension-relieving laughs. * Is the Fall test harder than the Spring's? Looking at the test results of the past four years seems to suggest that trend (e.g. the Fall '90 massacre and the Fall '88 test that I consider the hardest DWE in recent memory). However, I can't believe that the professors deliberately try to make one test harder than the other. And the recent Spring '92 test was no cakewalk. You'll have to draw your own conclusions on this one. ========================================================================== VI. Conclusion "If you must play, decide three things at the start: The rules of the game, the stakes, and the quitting time." - Chinese proverb ========================================================================== The DWE is a rite of passage, an obstacle in the path leading to your ultimate goals. Overcoming this obstacle takes a considerable amount of effort and preparation. I hope this guide will be of some help as you get ready for the exam. If you don't pass at the level you want, or if this is not the first time you're taking the DWE, the only consolation I can offer is: it's easier the next time around. That comes from personal experience, because I took the DWE twice myself. Good luck. ========================================================================== Appendix I: Sample problems from old DWEs, sorted by subject "Divine inspiration is an acceptable means of solving these problems." - Kye Hedlund, teaching 122 ========================================================================== Notes: Any question labelled "from Hell" indicates an unusually difficult problem. DWE problems are usually interdisciplinary, so secondary areas are included with a plus sign. These classifications are my own; you may not agree with them, but it's a place to start. * 122 ****************************************************************** Spring '93 Q8 +151,261 Hexagonal tiling Fall '92 Q4 Minimal spanning tree "Sculptor" Spring '92 Q1 Balanced trees Fall '91 Q2 Minimal spread spanning tree (flawed) Spring '91 Q3 Convex hull Q7 +214 Recursive function; dynamic programming Fall '90 Q7 Prime factors Spring '90 Q2 +213 Plists Fall '89 Q4 Towers of Hanoi Spring '89 Q2 Unimodal lists Fall '88 Q1 Cyclic Towers of Hanoi Spring '88 Q4 Maze from Hell Q7 +181 Massively parallel machine with 2 sec. clock cycle Q9 +212 Network Fall '87 Q1 Interconnecting moving points Q7 Black-connected regions Spring '87 Q4 Program correctness Q9 +261 Ranking items in a list Spring '86 Q1 Finding points inside rectangles Fall '85 Q5 Nondecreasing 2D array * 151 ****************************************************************** Spring '93 Q2 X^(1/alpha) <= log(x) from Purgatory Fall '92 Q9 Number of bits needed to compute Harmonic series from Hell Spring '92 Q4 Exponential series, oscillations [Note: a duplicate of Spring '85 Q3 !] Fall '91 Q8 Equations for cross-sections (flawed) Spring '91 Q5 Morehead Planetarium clock correction Fall '90 Q5 2 simultaneous quadratic equations Spring '90 Q9 Linear splines Fall '89 Q2 +122 Line drawing graphics from Hell Q7 Convergence Spring '89 Q4 +261 Calculating A^(1/4) Fall '88 Q3 +212 Parallel Jacobi from Hell Q4 Euler differential equations from Hell Spring '88 Q5 +261 Square roots Fall '87 Q4 +261 Sin, cos, polar coordinates Spring '87 Q5 +261 Network for polynomial math Q6 Integration on badly behaved functions Spring '86 Q3 Function plotting Fall '85 Q10 +261 Error in fast multiplication Q11 Error in division Spring '85 Q3 Exponential series, oscillations * 181 ****************************************************************** Spring '93 Q5 Chomsky hierarchy Fall '92 Q6 "Ink" Turing machines Spring '92 Q7 Fuzzies & slimies; Tamales & cucumbers Fall '91 Q5 Specifying classes of languages Spring '91 Q4 k-turn npda's Fall '90 Q1 LL language Q6 +216 Languages, PDA stack hw implementation (NOTE: the 2nd part of this question is trivial if you took 268, but otherwise it's rather difficult, unless you're a hardware guru) Spring '90 Q7 +122 K-unary integers Fall '89 Q1 "Mountains" Spring '89 Q1 +214 NFA, DFA, PDA on filenames Q7 +214 BNF, Chomsky hierarchy Fall '88 Q5 Classifying machines that recognize striped patterns Fall '87 Q5 Write-Once TM from Hell Spring '87 Q3 +122 Lexical scan, DFA implementation Q7 Chomsky hierarchy Fall '85 Q7 Jumping machine * 212 ****************************************************************** Spring '93 Q3 +261 Multiprogramming, lightweight processes Fall '92 Q2 +213 OS services for databases Q8 +213 Files and databases and aliases Spring '92 Q5 +261 Paged virtual memory Spring '91 Q6 +214 Sharing code & data Spring '90 Q3 Implementing Hoare & Mesa monitors with semaphores Q5 +261 Memory management system for objects Fall '87 Q6 Mutual access to datafile Fall '86 Q8 Locking files with multiple access Spring '86 Q11 Monitor (vague) Fall '85 Q3 Synchronization (Bank) * 213 ****************************************************************** Spring '93 Q9 Conference DB design Spring '92 Q2 Rental cars at RDU Fall '91 Q6 Class schedule database Spring '91 Q1 Class registration database Fall '90 Q3 +212 DB design, distributed DB Spring '90 Q5 +212 DB for makefile, symbol table Fall '89 Q3 +212 DB + file system design Spring '89 Q5 Hiearchical file struct Q8 +122 3-level graph Fall '88 Q9 +212 Images across a network Spring '88 Q1 +217 Recognizing a Pascal program Fall '87 Q3 Airline reservation system Fall '86 Q2 Hiearchical file system Spring '86 Q5 File structure for DB Fall '85 Q2 Using DB to maintain symbol table for a compiler * 214 ****************************************************************** Spring '93 Q1 +217 Block structure & scoping Fall '92 Q1 +217 MAXINT Spring '92 Q8 Macro processor Fall '91 Q3 Compiling TAC intermediate code Fall '90 Q2 +122 Lexical scanner discriminating between two sets Spring '88 Q6 Parallel Pascal compiler Fall '87 Q8 Macros variations Spring '87 Q11 +181 Lexical scanning Spring '86 Q7 Binding Q10 Parsing, table driven vs. recursive descent * 216 ****************************************************************** Spring '93 Q6 Up-down counter from Purgatory Q7 +122 Serial comparator Fall '92 Q7 +181 PLA implementing DFA Spring '92 Q3 Binary -> BCD converter Fall '91 Q4 Synchronous serial min/max Spring '91 Q8 Synchronous 10-state counter Fall '90 Q8 +261 Implementing bus controller hardware (NOTE: this question, in my opinion, is on the outer fringe of what's covered in 216 and 261.) Spring '90 Q4 Implementing an FSM Fall '88 Q2 Ripple adder Spring '88 Q8 Circuit for Hamming curves from Hell * 217 ****************************************************************** Spring '93 Q4 +214 Language design decisions Spring '92 Q6 +214 Functions with arbitrary # of args Fall '91 Q7 Goto statments Spring '91 Q9 +214 One-pass compiliation of for loops Fall '90 Q9 +214 Remote procedure calls Spring '90 Q8 +214 Language for parallel processing Fall '89 Q5 +213 Extending Pascal to include relational queries Q8 Displays, static & dynamic links Spring '89 Q6 +261 Range checking Q9 Dynamic vs static scoping Fall '88 Q6 Recovering storage on a heap Q8 +151 Parameter passing Spring '88 Q2 Variant records & strong typing Fall '87 Q9 Storing records and unions Spring '86 Q6 Real variables Q9 Saving execution state * 261 ****************************************************************** Fall '92 Q5 +212 Supervisor program integrity Q3 Pipeline execution of self-modifying code Spring '92 Q9 Configuring a system Fall '91 Q1 +212 The Colab audio-visual network Q9 Parallel architecture for neural nets from Purgatory (i.e. not quite from Hell, but somewhere in between) Spring '91 Q2 +212 RISC vs CISC effects on OS Fall '90 Q4 +217 Pipelining Spring '90 Q1 +216 Controller for stack machine Fall '89 Q6 +212 RISC + cache Q9 Vector interrupts from Hell Spring '89 Q3 Specifying DMA controller at the block level Fall '88 Q7 3-stage pipeline Spring '88 Q3 RISC Fall '87 Q2 Cache & multiple processors Spring '86 Q4 Microcode controller Fall '85 Q8 Cache (write-through vs. write-back) ========================================================================== Appendix II: A short note on mental attitude "No passion so effectually robs the mind of all its powers of acting and reasoning as fear." - Edmund Burke "If you aren't fired with enthusiasm, you'll be fired with enthusiasm." - Vince Lombardi ========================================================================== In 1978, the famous tightrope walker Karl Wallenda fell 75 feet to his death. The situation was much like all the other performances in his career, except for one factor: his mental attitude. For some reason, he became obsessed with the fear that he might fall. "All Karl thought about for three straight months prior to it was *falling*," his wife said. "It was the first time he'd ever thought about that, and it seemed to me that he put all his energies into not falling rather than walking the tightrope." An article in US News & World Report (Aug 3, 1992) suggests that what separates the top professional athletes from the rest has as much to do with mental preparation as it does physical talent. The ones who are able to perform in the clutch, when the stress is greatest, are the ones able to focus their minds on the tasks needed to succeed, rather than thinking about the risks of failure. A player that enters a game believing he has no chance to win creates a self-fulfilling prophecy. In interviews with successful executives, Warren Bennis discovered a trend that ran among all of them. He never once heard the word "failure." They had setbacks, mistakes, errors, and other temporary problems, but never "failures." The most successful high-level executives jumped onto their "tightropes," always aiming and striving toward their destinations, rather than peeking down at the canyon below. To maximize your chance of success when taking the DWE, you need to focus on passing the test, not on worrying about failing it. If you enter the test thinking, "Well, I'm probably not going to pass," then you probably won't. The best mental state is to be slightly nervous (to give you the necessary focus and concentration to avoid stupid mistakes) but basically confident that you will do well overall. And how do you build confidence? The only sure way I know is the hard way: preparation. As Bobby Knight says, "The key is not the will to win... everybody has that. It is the will to *prepare* to win that is important." And how do you prepare? Well, that's what this guide is all about... ========================================================================== Appendix III: past DWE scores ========================================================================== Dr. Calingaert put together a sheet summarizing the DWE scores from the Spring '86 exam to the Spring '93 exam. I list the percentages here; you can get the full sheet by asking Dr. Calingaert for a copy. Ph.D. pass M.S. pass Fail Total # takers ---------- --------- ---- -------------- S86 77% 46% 8% 13 F86 46% 38% 15% 13 S87 65% 18% 18% 17 F87 57% 39% 4% 23 S88 56% 40% 4% 25 F88 39% 50% 11% 18 S89 38% 54% 8% 24 F89 41% 41% 18% 22 S90 52% 48% 0% 25 F90 45% 27% 27% 11 S91 43% 43% 14% 21 F91 40% 47% 13% 15 S92 40% 47% 13% 15 F92 63% 26% 11% 27 S93 32% 64% 5% 22