I'm writing this to share my experience of thesis-writing (and other aspects of PhD research) with CS710, and to help myself by trying to write it up in one place (it is in no way intended to be a substitute for reading through my CS710 course summaries, however). I may well revise this page in the future.
Much of the advice on this page comes from my supervisor, Nick Filer.
I do not intend this page to be taken as gospel. Feel free to make suggestions or alternative points of view.
Aaron Sloman's Notes on Presenting Theses is quite possibly the most useful thing I've ever read when it comes to advice on thesis-writing! It focuses on the strategic level, and covers everything that should be included in a thesis right down to the nitty-gritty details. It seems to talk to you as directly as anything could that doesn't know what your particular thesis is about. All thesis-writers must read it! Aaron Sloman is also willing to receive criticisms, comments and suggestions for improvements.
I am a PhD student in my fourth and final year. I started as a research student here in September 1997, and submitted my MPhil thesis in December 1998 - over two months late. The biggest reasons for the delay were that it was a brain-dump (I tried to write down everything I knew about my topic - I didn't know how to leave things out) and that I am a perfectionist (I won't submit anything until I'm sure I've done my utmost - most of the two months of overrun were proof-reading and editing, including moving large chunks to appendices to keep the length of the main text down). In the end, my MPhil thesis was 339 pages long - larger than most PhDs! - with about 150 pages of main text.
The lesson here is that a thesis should be focused, not an attempt to capture everything you know about your field. You have to focus on the specific problem you're trying to solve, while at the same time showing a sufficient awareness of the field in general (i.e. the literature).
I was highly successful as an undergraduate here, gaining a first-class BSc, and winning the Williams/Kilburn medal for being the outstanding final-year student. However, research is a huge struggle for me, because it's so vague - it's not like a taught course where you have concrete targets to fire your arrow at. I am so far behind now that I'm having to register full-time for a fourth year, and have strictly until 30th September 2001 to submit my PhD thesis. I started writing my PhD thesis in the December 2000 vacation, but put it on hold until April 2001 as I haven't finished my practical work.
How to structure the thesis
There are two extreme ways to structure a thesis:
Implementation-oriented: Structure the thesis around the system you've implemented, with chapters like [introduction, literature review, analysis, design, implementation, conclusion].
Contribution-oriented: Identify three or four contributions to knowledge, and write a chapter for each contribution, book-ended by an introduction chapter and a conclusion chapter. The literature review, implementation, experiments, etc., are distributed through the contribution chapters, rather than being chapters of their own, through which the contributions are distributed.
An implementation-oriented structure is appropriate for an undergraduate project report, and will even pass for an MPhil, but for a PhD you really need to adopt a contribution-oriented structure. PhD examiners do not care about the implemented system - what they really care about is the contribution to knowledge, so it's very important to identify the contributions of your work, state them clearly in the thesis, and organise your thesis around them. Everything in the thesis should relate to one of your contributions.
A contribution-oriented thesis can be visualised as a diamond structure, with lines going out from the introduction chapter to the contribution chapters, and from the contribution chapters to the conclusion chapter.
I thought I couldn't do a contribution-oriented structure at first, because my contributions are so intertwined (I have one overarching contribution and four subcontributions). You may have to question what your contributions are, and how they should be organised. Get the structure of your contributions clear before you derive the structure of your thesis.
It is instructive to take a few PhD theses, read their first and last chapters to identify the contributions, and to see how their contributions fit into their thesis structure.
Planning the thesis at the strategic level
I plan my thesis in detail before I write the actual text. I take a top-down approach: identify the chapters, identify the sections and subsections, and identify the major points to be made. Identify the preconditions and postconditions of each part, so that you know what the dependencies between the various parts are, especially if you're going to write them out of turn. Expect to have dilemmas about where things belong, and circular dependencies. You might have to move things around, and this is obviously easier to do to the plan before you write the full text.
Start by planning the conclusion chapter. Knowing what your conclusions are will help to focus the rest of the thesis and keep it coherent.
Consider writing the introduction and especially the conclusion chapter last. My supervisor insists that the introduction chapter is a very bad place to start! This is because it needs care to avoid a lot of irrelevant detail. It's particularly important that the introduction (especially the aims and objectives section) and the conclusion are coherent with each other.
Here are some hints about how to write a thesis plan:
What points are you actually going to make? For example, in a literature review, for each reference:
How does it relate to your work?
What are the good and bad points about their method, in comparison to your method?
Write down the preconditions explicitly. What do you have to know before you can write the answers to 1? What does the reader have to know before they can understand this? What assumptions are you making about the reader? What do you regard as absolutely obvious that other people might not? (This applies both at the tactical level and at the strategic level.)
When thinking about the literature/your work, think about how it relates to your work/the literature.
You may find that your plan contains circular dependencies, and that you have dilemmata about where to put things. To break a circular dependency, introduce the thing early on, leave the detail until later, and insert cross-references.
Evaluation is a crucial part of passing the PhD examination - how do you show that you have succeeded, and measure your success? This is a very difficult problem for me, and I wish CS710 would devote a week to evaluation. It's important to work out your evaluation criteria, and to make these criteria clear in the thesis - otherwise the examiners will judge you by their own, probably inappropriate criteria.
An important piece of advice I was given at my last end-of-year interview is to evaluate with respect to a specific application rather than thinking you can do some sort of generic evaluation. Who might your end-users be? Why would they be interested? What use would your work be to them?
There is thus a distinction between intrinsic evaluation (does it work?/performance measurements) and extrinsic evaluation (a demonstration that it is - or would be - useful in a specific application context). A PhD must have adequate intrinsic and extrinsic evaluation.
Know the weaknesses of your PhD. Write down a list of all the reasons you think your PhD could fail, and discuss it with your supervisor. This is a very valuable exercise because (a) if you know what the weaknesses are, you can work on them, and (b) you might find it's not as bad as you think! :-) Some things to consider for the list:
What is the area in which you wish to be examined? Are you going to find a sympathetic examiner in that area?
Is your work strong enough technically to deserve a PhD? Are your contributions adequate or superficial? You may have to reconsider what you're going to claim as your contributions - each contribution has to be adequate for a PhD (do not underclaim) and yet defendable (do not overclaim).
Have you performed an adequate intrinsic evaluation of your work, with a meaningful interpretation of the results?
Have you performed an extrinsic evaluation of your work with respect to a specific application context, that doesn't come across as merely `bolted on'?
Have you compared your results directly with the results of others? Some areas have standard test data, but this may be a major difficulty if you're working on a unique problem - you have to try to find some way of comparing your results to others.
Are there holes in your literature review? Have you considered all the relevant areas of Computer Science which overlap with yours?
Have you got your finger on the pulse of what is going on in your area(s)? Computer Science is a rapidly progressing subject, so it's all too easy to miss some major recent developments.
My tactical-level advice for technical writing
Synonyms: Identify the terms you use which may be so obvious to you that you don't think about it, but which may confuse other people. For example, in the CS710 edit of my MPhil thesis in 1998, I confused people by using the terms "model" and "schema" interchangeably - I regarded them as synonyms, but other people thought they had different meanings.
Homonyms: Be consistent in your use of terminology. Always use the same term to mean the same thing, because polysemous terms (terms with more than one meaning) confuse the reader and irritate the examiner.
Acronyms: Use acronyms and abbreviations sparingly, for those terms which have many occurrences in your thesis. For example, the main acronyms I use are CCUS (Comparative Code Understanding System), and HLC (Higher-Level Constraint). Too many different acronyms, or acronyms whose occurrences are few and far between, confuse the reader. Always define each acronym at its first occurrence in each chapter.
THE GOLDEN RULE: Always question your assumptions about the reader! They may not understand what you have written the way you understand it! This applies both at the tactical level and at the strategic level.
Be consistent in your use of spelling, hyphens, capitals, and everything! If you have a choice of alternate spellings (e.g. "lemmas", "lemmata"), choose one and stick to it consistently.
Use hyphens when two or more words modify a noun, e.g. "object-oriented programming", "case-based reasoning", "thesis-writing sessions", "32-bit words" (but note that "32 bits" is correct as a noun phrase).
Note the ambiguity when two or more words modify a noun with no hyphens (e.g. "efficient plan search"), because the way they group together is ambiguous (is it an efficient search for plans, or a search for efficient plans?). Use hyphens to group them together for the reader ("efficient plan-search" or "efficient-plan search").
Beware of chapter titles that are so long that they overflow the top line of each page, blocking the page number.
Beware of figures that overflow the page horizontally or vertically. LaTeX can resize figures to a specified height and width.
Explain any notation you use in diagrams, even if you're using a standard formalism - don't assume the reader is familiar.
Never be afraid to use bullet points, as I'm doing here. It makes the text much more readable than list-like paragraphs, and clarity can only be a good thing.
Put each term in italics where you define that term (not necessarily the first occurrence of the term). Apart from that, use italics and bold face very sparingly.
Be consistent with bold and font conventions (and so on) throughout the thesis.
Proof-read carefully for ambiguity which may confuse the reader. It helps to get someone else to proof-read.
Don't start a sentence with a symbol.
Put words that are in a programming language rather than English in teletype.
Put a space between numbers and units, e.g. 256 Mb.
Don't use "etc." - use "such as", "and so on" or "include" instead.
Number every section (e.g. 2.3), subsection (2.3.1) and subsubsection (22.214.171.124).
And don't start a sentence with a conjunctive! ;-)
Put footnotes after a comma or full stop, not before.
Let the reader know what you're building up to, so that they can see the point of what you're talking about!
Put all figures in boxes (unless a figure fills the whole page).
Avoid wishy-washy language such as "we wish to consider".
Whenever you write the word "consider", reconsider if you really mean that. You may subconsciously be trying to cover something up, or committing yourself only partially to a statement you're not confident about. A cunning examiner will expose such weaknesses.
Use "such as" rather than "like" when giving examples such as "object-oriented programming languages such as C++ and Java". If you write "object-oriented programming languages like C++ and Java", it actually means you're not considering C++ and Java themselves, but only languages which are similar to C++ and Java.
If articles ("the", "a" and "an") aren't present in your first language (some languages, such as Mandarin and Slovak, don't have articles), you have to be careful about how you use them - leaving them out when they're supposed to be there, using "the" when it should be "a", using "The" at the beginning of headings, and so on.
Long sentences are only okay if they read well!
If there are two main verbs in a sentence, use a semicolon.
Use commas to split a sentence according to its logical flow so that the reader knows when to `breathe' and what to `put on the stack' just like I haven't done in this sentence! ;-)
If you end a paragraph with a colon (`:') followed by examples, you could be accused of not ending the last sentence with a full stop.
The day-to-day process of thesis-writing
It's important to organise your time well, and try to get into a routine for thesis-writing. It's not easy because your situation will keep changing. It's a very individual activity, but I want to talk about how I do it.
I do not live at university - my house is an 80-minute journey away (walking, train, waiting, bus). That's when I do most of my reading - papers, and proof-reading my thesis (usually the bit I've just written). I generally do no work once I get home, which is usually between 21:30 and 22:00. I usually go to bed just after midnight, and I require 6h30m to 7h sleep to operate effectively.
On a good thesis-writing day (expect plenty of bad ones, though, when you just don't feel like it! ;-)), I arrive at university at 9:20 or 9:50 (depending what train I catch). It's good to start with editing the thesis according to the comments you've written on yesterday's draft (mainly tactical-level), because it's a gentle introduction to a day of thesis writing. If you don't take a comment on board immediately, insert it into the text of the thesis using special characters to delimit it, and don't forget to grep for such comments before you submit!
It's important to block out distractions, because it's easy to make excuses to put off starting work for the day, especially something as vague and difficult as research (concrete tasks are easier to get down to). My particular vice is emailing and surfing the Internet, so I have actually written a Perl script to keep me off until 17:00!
I usually do my main block of thesis-writing after lunch. Getting down to it is the hardest part, but it's possible to get on quite a roll if you're motivated, if you block out distractions, and if you're feeling alert. Unfortunately I am prone to mid-afternoon slumps, where my brain just packs in and I can't do any work. Such slumps can be combatted using coffee or stimulant drinks - I find the `V' stimulant (green can) to be most effective, and I have one every day with my lunch now. I also tend to be more alert in late afternoon/early evening, so I will often continue then (even if I have to sacrifice my Internet time! ;-)). You need to find out what works for you - what time of day you work most effectively, and how long you can work for in one sitting. If that would be working at night and sleeping from 8am to 4pm, then do it! ;-)
I record the time I spend working each day - thesis-writing, reading, programming, meetings with my supervisor, CS710-related activities, etc. I write it in my diary so that at the end of each day (and week), I can feel good if I've had a productive day, and guilty if I haven't put the effort in, so I know I have to buck up my ideas. It is good to have hobbies, and to devote a few hours a day to them, because it keeps you sane and enjoying life. It's best to leave hobbies until the end of each day, to avoid distractions, and to enjoy your hobbies without feeling "I should be working now". Interleaving hobbies with bouts of work throughout the day has the pitfall that it's easy to get sidetracked or absorbed in your hobby, so it's better to take a coffee break, have a 20-minute walk, or do something that's definitely going to be time-limited.
I go in to university on Mondays to Saturdays, and work at home on Sundays, taking copies of thesis files to work on the Mac at home (that's the joy of LaTeX, which compiles text files with embedded formatting commands rather than you have to use a special program to edit the files). If you have spreading versions of files like this, it's a good idea to put the time and date on the first line of each file every time you save it, which resolves any confusion over which version of the file is newer (it's also vital that you keep at least one regularly-updated backup of your thesis files on another file system). I also write the date on each printout (by hand).
The week-to-week process of thesis-writing
It's important to plan what you intend to achieve each week, and at the end of each week, to take stock of what you've done that week, and plan for the week(s) ahead. For this purpose, I write a weekly summary of up to one side of A4.
I'm within six months of my thesis deadline, and I have six chapters to write in that time, so I've planned to spend three weeks writing up each chapter and working on the plan for the next chapter, leaving a month before the deadline for proof-reading and editing (do not underestimate the time needed for this - that was one reason why I was two months late submitting my MPhil thesis).
When you start writing up a chapter, annotate your plan of that chapter with the date when you plan to write each section, and try to stick to your time-plan. I tend to allocate a day to each subsection. Leave some slack in the plan in case you fall behind. If time is tight and you fall behind on a day's target, it may be better to start tomorrow on the next section anyway, and go back and finish the unfinished section later - otherwise, you tend to dwell on a section or chapter too long, and end up falling behind significantly. Expect to leave some gaps as you go along anyway, because there are likely to be bits you're not ready to write right now, or that you're psyched out by.
It's important to get regular feedback from your supervisor. I generally show each chapter to my supervisor just after I've written the first draft, and the plan for the next chapter I want to write up. I'm currently writing Chapter 5 (my second full chapter to write up), and the plan for that went through several iterations over a period of two months before my supervisor said it was ready to write up. This was an incredibly frustrating and depressing period for me, but a thesis is likely to fail if it isn't written up with the right plan.
A good supervisor will discuss your thesis plan with you, asking you questions to which you may know the answers but haven't thought to include those points in the thesis, and identifying gaps that need further research before you can write them up properly.
A big dilemma for me is that students are encouraged to follow a `waterfall model' of research - finish the practical work before starting to write the thesis. I feel most uncomfortable with this, especially as I am anxious not to keep putting thesis-writing off when my back's to the wall time-wise. It's natural for someone like me to want to continue with practical work in parallel with thesis writing. The pitfall with this is that it's harder to keep the story coherent if practical work is still ongoing. Another pitfall is that you'll tend to concentrate on one for weeks at a time, while the other stagnates. If you do have to interleave thesis-writing with practical work, I think it's best to set aside specific days of the week for each activity - e.g. Mondays and Tuesdays for practical work, and the other days for thesis-writing (not forgetting CS710 on Wednesdays! ;-)). This is better than trying to do some of both each day, because you tend to spend the whole day doing one or the other.
Do not expect progress to be constant! Sometimes you might go weeks without writing anything, even if you've already written a chapter. There may also be certain times of year, such as Christmas, when you won't be doing much work. I have promised myself to take the Wimbledon fortnight off (I am an avid tennis fan). I think it helps if you identify such breaks in advance and treat them as milestones - planning to have written up Chapters X, Y and Z by then gives you something to aim for.
The final year of your PhD can be a very difficult period emotionally, when you're writing up the most important large document of your life, and you're pessimistic about the chances of passing (which could be a self-fulfilling prophecy if you allow it to affect your motivation). You might also be worried about what you'll be doing next year - pass or fail. I try to take it philosophically, and live for the moment. I've no idea what I'll be doing next year, and I'm not even going to think about getting a job until my PhD is all over. I've promised myself an indefinite break after my PhD, and looking at that time not as unemployment but as a time to indulge my hobbies gives me something to look forward to, and makes me want to make that final push for a PhD, knowing that the burden will soon be off my shoulders whether I pass or fail.
Miscellaneous advice from students' thesis presentations
When you mention things in Chapter 1, you have to decide whether to explain terms there or not. It's a matter of whether it's understandable to general Computer Science.
What is the problem you're trying to solve? (e.g. existing methods are too slow)
Implications of problem (why is what you have done important?)
Claim for solution
Support for claim (abstract should mention results, but doesn't have to be quantitative)
Wider implications (to whom might your results be useful?)
An abstract must be limited to a single page - the rule is here.
A scientific-engineering thesis needs analysis of data.
If you're doing a simulation, you need to compare your simulation either with other people's simulations, or with reality. Where's the feedback of reality into your system?
Don't hide your difficulties under a bushel. If you duck the issue, you'll leave yourself open to issues you haven't thought of.
End each section with the message you want the reader to take from that section.
Each chapter needs an introduction to say how it fits into the grand plan, and what this chapter is going to achieve. Each chapter also needs a conclusion at the end, to tie it up. Remember, people may read your chapters in any order!
Don't put private communications in the bibliography - use footnotes instead.
It's acceptable to reproduce figures from other publications, provided you state that you have done so!
Be consistent with references, and use a style that's recognised in your area. Alphabetical order is best for the reader to look up.
It's very important to establish what the problem is. Use motivating examples. Why is your tool needed? What could it be used for? Examples of where it would be useful.
What's the current state of play? What are you doing to enhance it?
It's a good idea to write Chapter 1 last, when you know what follows.
You should write the conclusion chapter second-to-last, but write the plan for the conclusion chapter before you start writing up, so you know what your conclusions are going to be!
To resolve circular dependencies, introduce the thing earlier, with details later, and use cross-references.
When describing your work, it's important to expose the concepts rather than the detailed implementation.
Beware of baring nasty branches for clarification at the viva - they could ask you to justify any statement in the thesis.
In general, you should define each term before you use it. However, it may be desirable to use a term in an introductory section and then define it later - in which case you should put a forward reference to where you define the term, or better still use a glossary.
A thesis is not required to have a glossary of terms, but it's a very good idea to include one! It doesn't take much effort if you do it as you go along, adding each new term you introduce in the thesis to the glossary. The glossary should be at the front of the thesis, before the first chapter, so that the reader knows it's there from the start.
Make sure each entry in the bibliography is correct and complete. There must be enough information for someone to locate or order each reference. In particular, don't forget to include the venue and dates of a conference; the volume number, issue number and month of a journal; and for a book, the city and country of the publisher and the ISBN number (many people don't think it's necessary to include the ISBN, but some people do, and I think it's better not to omit information when you can include it). Don't forget that conference proceedings published in Springer's Lecture Notes in Computer Science series are books as well as conference proceedings!
Any websites referred to in the thesis should be included as entries in the bibliography. The problem with the Web is that sites often tend to get deleted, moved or reorganised, resulting in broken links. Include the date that the page was last modified (or, if unavailable, the date when you last accessed it) so that readers can tell if the page has changed. Don't forget to check all the URLs in the bibliography just before you submit the thesis!
No matter how impressive your work is technically, a thesis is of no value to anybody if it doesn't tell the story in an accessible way. If you have a thesis full of mathematical definitions, theorems, lemmata and proofs, you must explain each thing intuitively - remember you're writing for humans, not machines!
More advice on the Abstract:
It should be understandable to computer scientists in general, not just those in your field. This is a problem for theses with a lot of esoteric terms.
The abstract should give the potential reader enough information for them to decide whether to read the thesis. Why is the problem you've tackled important? How does it apply outside your particular domain?
You should not italicise things in the abstract.
Do not put citations (references) in the abstract - bear in mind that the reader of the abstract may not have the whole thesis to hand! (It's okay to put people's names in the abstract.)
The table of contents should be understandable in and of itself. Avoid undefined abbreviations in headings.
Make sure you are clear about what is your work and what is the work of others! The distinction between your work and others' work should be clear from the table of contents, but in most theses I've seen, it is not. If you have separate literature-review chapters, it might be an idea to divide the chapters into Part I (background) and Part II (your work), but then again, it is better not to have separate literature-review chapters, but to distribute the literature review among contribution chapters.
Each paragraph should cover at most one `topic'. To appreciate your writing (and the writing of others) at the strategic level, it helps to jot down in the margin what each paragraph is about, and then to consider for each section whether the points in the margins fit together, are in the right order, flow well, etc. If a paragraph has two or more disconnected topics, it should be split into a paragraph per topic. It should not be split in the case where the paragraph has one overarching topic and several points refining that topic, but you should consider whether the points would be better off as bullet points. If a paragraph is excessively long (more than 12 lines, say), try to split it according to topic, or break it down into bullet points, unless neither is appropriate.
Try to finish each section with the message you want the reader to `take home' from that section. I think it's good if you can finish a section with a short, snappy, single-line paragraph (a technique often used by good sports reporters), but I've never been able to do that in academic writing.
Be careful to explain specialist terms and concepts for the benefits of general computer scientists who aren't specialists in your area - it's easy to take them for granted when you know it so well.
Avoid the passive voice, because it either avoids assigning responsibility ("mistakes were made") - which the examiners won't like - or sounds very unnatural ("mistakes were made by me").
If you have a problem you can't sort out right now, leave a comment in the text, marked with a special character so that you can search for comments at the end, and resolve them all before you submit your thesis. Don't just leave a hole - make sure you have a systematic way of searching for such gaps.
Every chapter/section heading should fit on one line (in the text, and in the table of contents). Avoid unnecessary detail in headings - they just need to bring out the contrasts with other sections.
Appendices should contain technical stuff which is necessary to reproduce your results, but which doesn't contribute to the discussion in the main text.
You can submit your published papers with the thesis - evidence of your acceptance in the scientific community. You can even put them as appendices, but I would have thought it would be better to hand them in unbound when you submit your thesis.
Chapter 1 should start with the specific problem you have solved, rather than general background. What have you done, and why is it important? Start with the essence of your thesis, and state your contributions on the first page.
Chapter 1 should be a gentle introduction, not full of technical details.
The abstract and Chapter 1 need to include a fairly wide introduction to your field, for the benefit of mainstream Computer Science.
Chapter 1 must include an aims and objectives section, in which you declare your contributions explicitly; this must be coherent with the conclusion chapter. It's also a good idea to list your contributions up front on the first page of Chapter 1, and you should definitely declare your contributions explicitly in the abstract, too.
Chapter 1 should end with an overview of the thesis - not just a potted summary of each chapter, but saying how they relate to each other, and really giving the impression of a coherent thesis. A diagram of the thesis structure is a good idea (boxes for chapters, arrows for dependencies between chapters).
Generic template for Chapter 1:
1.1 the problem you solve in this thesis
1.2 background about your area
1.3 Aims and Objectives
1.4 Thesis Overview
Generic template for the final chapter:
n.1 Thesis Summary
n.2 Conclusions (coherent with Aims and Objectives in Chapter 1)
n.3 Future Work
Bear in mind that the title sets up the reader's expectations for the abstract, the abstract sets up the expectations for the table of contents (i.e. the thesis structure), and the table of contents sets up the expectations for the rest of the thesis.
Writing serves two purposes:
to clarify things for yourself;
to communicate things to others.
That's why you need to write and rewrite.
It's a good idea to write the abstract at the start, to clarify what you're doing for your own benefit (and for the benefit of CS710!). It's only a single page (I wrote mine in about half an hour), so you can always throw it away! It may be an idea to write the abstract from scratch at the end, and then to merge the new abstract with the old abstract to get the best of both.
The main point of the abstract is to explain what you're doing! Someone who knows nothing about your work should be able to get the essence of your thesis just from reading the abstract.
Make clear the logical connections between sentences and paragraphs, to help the reader follow the flow. Use words such as "thus", "hence" and "therefore" to emphasise that what you're saying now follows from what you've just said. Use words such as "however" and "but" to deny a conclusion that the reader might have drawn from what you've just said. If you do not use such words, your writing may well come across as a bunch of disjointed sentences and paragraphs strung together at random! ;-)
Make up your mind about who your intended audience is. Make sure that every time you introduce something, it's understandable to your intended audience. I feel strongly that a PhD thesis should be understandable to general Computer Science, especially the first chapter. The first chapter must therefore explain background that people in your area take for granted. Explain to the reader what everything means.
Beware of listing things just to show that you know about them - just mentioning them in passing will raise more questions than it answers. It may not be necessary to mention them. If you're going to mention them, you need to elaborate with a brief explanation of each thing - I suggest a list of bullet points.
A thesis should not read like a novel, with paragraph after paragraph of dense, tightly-written material! You need to break it up by dividing it into sections and subsections, with figures, bullet points and so on.
Although academic writing is a very formal, tightly-constrained affair, some informal writing can be good. You tend to say what you mean when you write without the constraints of formal writing, and it also helps to create tension (in keeping with the `detective-story' model of a thesis). I'm not sure where they'd draw the line, exactly. Obviously you wouldn't get away with swearing or slang, or any form of emotional language. You should avoid facile words such as "good", "nice" and "big", fluffy words such as "basically" and "probably", and colloquial expressions such as "to hang around". I think expressions such as "in a nutshell" are okay, but I would draw the line at expressions such as "real soon now" or "to grow like topsy". "You think I don't have to cuss in this thesis to get a degree? Well I do, so **** the examiners, and **** you too!" ;->
For every contribution, you need to say why it's important, why you did what you did, why it's a contribution. How general is each contribution in your field?
You need to link your contributions to your field - have you solved the field's problem that you claim to have solved? For example, if something is too slow, and you can make it go faster - how much increase in speed is needed for the applications you claim to support? You may be drawn on this in the viva.
Another issue to consider is whether your field is going in the right direction. For example, if everyone's been concentrating on speed, but the real issue is space (if the issue is time, you can just wait it out (unless it's combinatorially explosive), but if the issue is space, the system could fall over). This is kind of justifying why you have gone into the field you're working in. Again, this could come up for discussion in the viva.
To what extent do your results generalise to other systems to the one you've worked on. Once again, this is a popular topic for the viva.
When describing your work, you should focus on your system, with plenty of pointers to what's outside. It's very important to relate your work to others, and vice versa (when reviewing the literature).
Clarity and understandability (to general Computer Science) - the Golden Rule of thesis-writing are they. There aren't too many hard-and-fast rules about how to make things clear - you have to work it out for yourself to a large extent. In general, if it makes it clearer then do it. Make it clear what the highlights are.
You don't need citations for things which are common knowledge in your field. For example, frames in AI - you don't need to refer to Minsky's original article! It's often difficult to trace where such things originated. Citing an introductory textbook is boring (I have done so a few times in my thesis, though, just to be on the safe side).
Be very wary about citing things you haven't read! It's a heinous practice, it can be tempting, but the examiners might find you out by drawing you on any of your references in the viva.
Each chapter needs to be reasonably self-contained - remember, people won't necessarily read the chapters in order, or even read all of the chapters, and they're almost certainly not going to read the whole thesis in one sitting!
Begin each chapter by saying how its contribution relates to the thesis as a whole.
At the end of each chapter, point to what's coming next.
Make clear the dependences between chapters (before the reader can read a given chapter, which previous chapters do they need to have read?).
Rhetorical questions such as ending a section with "Can we do better?" - some people frown upon this, but I think it's a good thing, especially as it's an example of a short, snappy paragraph to finish a section with, and it points to what's coming. It's a matter of personal style.
Remove all occurrences of the word "obvious" from your thesis - it indicates that you're not prepared to defend something, so it's an `obvious' thing for examiners to pick on in the viva. What is obvious to you may not be obvious to someone else, and you might have a hard sell explaining yourself, as in "why is the sky blue?"
Don't partition into chapters, sections and paragraphs according to length, partition according to concept. A 6-page `concept' chapter and a 36-page `concept' chapter are better than two 21-page chapters that blur conceptual boundaries.
Use plenty of examples, more than you think are necessary. Especially for the benefit of people outside your area. Whenever you generalise, first convey the generality with an example, and then give the generality. The reader will better understand the generality if they've had an example which gives them something concrete to hang it on. Only occasionally is it better to give the generality first.