COMS21102: Software Engineering

The lecturers for this unit are:

Instructors	Office	Hours
Bogdan Warinschi	MVB 3.13	Monday 14:00-15:00
Raphaël Clifford	MVB 3.15	Monday 15:00-16:00
Dan Page	MVB 3.10	Friday 14:00-15:00
TA: Ben Sach	MVB 3.42	Tuesday 12:00-13:00

The timetables and room allocations for this unit are here:

Textbook

The main textbook for this unit is:

T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein (referred to as CLRS in lecture notes).
Introduction to Algorithms.
MIT Press, 2001.

Support

It is important to effectively utilise the various forms of support available for this unit; see the page about communication in the department for a general introduction.

Labs and Help Desk: There are no timetabled lab sessions for this unit; this is a departmental policy in relation to study within the second and later years. The lack of lab sessions means it is even more important to utilise the other forms of support available, for example the help desk in MVB room 3.19 should be the first point of contact for programming queries.

Forum: The forum can provide a useful way for you to help each other and to get questions answered by the lecturers or lab supervisors, both of whom will take part in online discussions:

COMS21102 Forum 2007-8

Feel free to post questions and so on; we'll try to answer them as soon as possible. However, before you use the forum you should make sure you have first tried to help yourself by reading lecture slides and course texts for example. Note that forum posts from previous years might be useful for reference:

but since the unit will have changed, don't assume these old posts will always answer your question categorically.

Office Hours: The lecturers set office hours where they guarantee to be in their offices to help you. You are welcome to drop in during those times to discuss any aspect of the unit. At other times, please use the forum or contact the TA for assistance. However, do first carefully check the recommended text book (CLRS) and the online book (DPV) and also the lecture notes where you will find most answers to common questions.

Email: Email is very useful for the lecturers to contact all of you, but it isn't so useful for you to contact the lecturers. They often get completely swamped with emails, so use of the forum is preferred for any questions. Following this policy for all but vital (or personal) problems will hopefully ensure common questions and answers are quickly made available to everyone.

Feedback: Like some other units, some of the coursework assignments in this unit are automatically marked. This means the feedback will be fast but of a fairly low quality. Some assignments (in particular those with a written component) will not be automatically marked. This means the feedback will be slower but of a higher quality. In particular we aim to provide a model answer as well as individual feedback. If you need additional feedback, please seek this via the routes above.

Lecture Notes

Week	Date	Material	Date	Material	Date	Material
1	Oct 9th	Introduction	Oct 11th	Math Recap	Oct 11th	Asymptotics
2	Oct 16th	Problems Class (Asymptotics)	Oct 18th	Recurrences	Oct 18th	Problems Class (Recurrences)
3	Oct 23rd	Program Correctness	Oct 25th	Turing Machines	Oct 25th	(Un-)computability
4	Oct 30th	P, NP and intractability	Nov 1st	Probability overview	Nov 1st	Class Quiz
5	Nov 6th	Sorting revisited [slide\|print]	Nov 8th	String matching [slide\|print]	Nov 8th	FFT and multiplication [slide\|print]
6	Nov 13th	FFT and multiplication [slide\|print]	Nov 15th	Search structures [slide\|print]	Nov 15th	Search structures [slide\|print]
7	Nov 20th	Number theory [slide\|print]	Nov 22nd	Dynamic programming [slide\|print]	Nov 22nd	Dynamic prog. (DPV) [pages 168--179]
8	Nov 27th	Order statistics [slide\|print]	Nov 29th	Bellman-Ford [slide\|print]	Nov 29th	All-Pairs shortest paths [slide\|print]
9	Dec 4th	Applications: PageRank [slide\|print]	Dec 6th	Representation [slide\|print]	Dec 6th	Pre-computation [slide\|print]
10	Dec 11th	Caching [slide\|print]	Dec 13th	Restructuring [slide\|print]	Dec 13th	Arithmetic [slide\|print] (plus a bonus !)
11	Jan 8th	Parallelism [slide\|print]	Jan 10th	Unit Testing [slide\|print]	Jan 10th	Design Patterns [slide\|print]
12	Jan 15th	Applications: Chess [slide\|print]	Jan 17th	Parallel Algorithms (1) [slide\|print]	Jan 17th	Parallel Algorithms (2) [slide\|print]

Coursework Assignments

Some coursework descriptions might appear online before the advertised start date as a courtesy to you; previous years have found it useful to be able to plan their workload and generally read and think about the problems before starting. However don't take a description as being finalised until the start date: up until this date minor details might change.

Number	Week	Start Date	Real Deadline	Late Deadline	Description	Submit	Submit Resit	Solution
1	2-3	Oct 15th	Oct 30th	Nov 1st	CW1 (5%)	submit CW1	submit ResitCW1
2	4				CW2 (5%)	Class Test	Class Test
3	5-6	Nov 5th	Nov 16th	Nov 19th	CW3 (10%)	submit CW3	submit ResitCW3
4	7-8	Nov 19th	Nov 30th	Dec 3rd	CW4 (10%)	submit CW4	submit ResitCW4
5	9-10	Dec 3rd	Dec 14th	Dec 17th	CW5 (10%)	submit CW5	submit ResitCW5
6	11-12	Jan 7th	Jan 18th	Jan 24th	CW6 (10%)	submit CW6	submit ResitCW6

Links and Resources

There are a number of good online resources that will act as a refresher for various topics in the unit:

Introductory material on probability from MIT:
Introductory material on complex numbers from the University of Lancaster:
Advice on writing and reasoning about proofs.
Online tutorials for Haskell, C and Java (the "Haskell for C programmers" tutorial is particularly good).
Advice on how to be a programmer.

There are also plenty of online resources that could help you find out more about topics covered in the unit:

We have a locally mirrored copy of a brilliant quick reference guide for theoretical computer science:

S.S. Seiden.
Theoretical Computer Science Cheat Sheet.
ACM SIGACT News 27(4), 52-61, 1996.

Copies of some useful new (preprint) and old (out of print) books can be found online:

S. Dasgupta, C.H. Papadimitriou and U.V. Vazirani (referred to as DPV in lecture notes).
Algorithms.
McGraw-Hill, 2006.
A.J. Menezes, P.C. van Oorschot and S.A. Vanstone (referred to as HAC in lecture notes).
Handbook of Applied Cryptography.
CRC Press, 1996.
V. Shoup.
A Computational Introduction to Number Theory and Algebra.
Cambridge University Press, 2005.