COMP26120: Algorithms and Imperative Programming (2017/18)


Acknowledgements: Parts of this course were developed by Joshua Knowles, Peter Jinks and Jon Shapiro.


Aims

The course aims to:

This is arranged differently from some other courses. To reflect its practical nature there is one laboratory session (2 hours) per week and one lecture (1 hour) per week.

Warning: In addition, lectures do not provide all the information you will need for the course, or to complete the laboratory exercises. You are expected to read additional material - this is part of developing algorithmic literacy. Lectures will, in the main, provide guidance on the structure of the course material, look briefly at some algorithms and algorithmic techniques, and, through invited lectures, look at areas of application of algorithms, for example in medicine and the biosciences, and in social sciences.

Resources

  • Syllabus

  • All lecture notes, laboratory exercises, examination and revision guidance, remedial mathematics material, notes etc. are available in the Activities and Assessment sections below.

  • Resources for the programming language C:

  • Algorithms:
    • Core text:
      Algorithm design: foundations, examples and internet examples
      by Goodrich, Michael T. and Roberto Tamassia
      ISBN 0471383951, Wiley 2002.

      Available as online book. To access this you need to be on the university network, or to set up a VPN (Virtual Private Network) to gain university access.

      Also available in the University library, Joule library, School library and Blackwells bookshop.

    • List of Supplementary texts in the syllabus

      Some of the links below may be obtainable only on the university network or via a VPN.

    • Material on Knapsack Problems: For laboratory exercises.
    • Material on Dijkstra's Shortest Path Algorithm: For laboratory exercises.

    General Arrangements

    Normally, there will be ONE laboratory session and ONE lecture per week. The schedule is given in detail below.

    Laboratory sessions

    Procedures for the Arcade records of your lab sessions:

    • The general rule for absences from laboratory sessions (because of, for example, medical appointments, interviews, etc, or illness), or if you wish to correct, amend or query any of your Arcade entries, is talk to the laboratory manager in your laboratory session - this is the most appropriate place and time and Arcade entries can be changed appropriately. If evidence is required to support your request, for example, a medical note, please be prepared to provide this in the laboratory session.
    • Only in exceptional circumstances contact a member of staff for these issues - ordinary messages will be ignored.

    Deadlines

    As well as the standard submission deadline, there is a marking deadline: All exercises should be marked within 2 WEEKS of the submission deadline.

    Course schedule, lecture material and laboratory exercises

    Lectures start in Week 1, Laboratory exercises in Week 2.

    Laboratory guidance

    • Policy on use of code from outside sources (downloaded from the internet, etc). Warning: Plagarism and collusion detectors may be run on your answers and disciplinary action taken.
    • Advice on debugging C programs: Debugging C programs
    • In the case where a student has not managed to get the code in a part of the exercise to run, marks will be limited to 50% of the marks awarded to a correctly running program.

    First Semester
    weekLECTURELAB
    Welcome/Registration Week No laboratory session in Week 0 or Week 1.
    1David Rydeheard: Introduction - Algorithms and their Performance
    2Milan Mihajlovic: C - Introduction, Input/Output (in PowerPoint)
    SalaryAnalysis: Java, C and diff
    David Rydeheard: Lab - Algorithm Design and Performance (Paper and pencil exercises.)
    3Milan Mihajlovic: C - Simple Data Structures (in PowerPoint), Q&A Milan Mihajlovic: Lab - Compiling & running C; Input/Output
    4Milan Mihajlovic: C - Recursive Data Structures (in PowerPoint), Q&A Milan Mihajlovic: Lab - Arrays and Strings
    5 Milan Mihajlovic: C - Coping without Classes (in PowerPoint) Milan Mihajlovic: Lab - Arrays and Memory management
    Reading Week
    7 Ian Pratt-Hartmann: Introducing Complexity. For these two lectures, you should read pp. 1--50, pp. 689-690 and pp. 695-696 of the course textbook "Algorithm Design and Applications" by Goodrich and Tamassia. Milan Mihajlovic: Lab - Pointers and Lists
    8 Ian Pratt-Hartmann: Introducing Complexity. Milan Mihajlovic: Lab - Pangolins
    9 Ian Pratt-Hartmann: Basic sorting algorithms + Sorting Movies and Interactive Animations + quicksort-learner.c, demo1.c, demo2.c, demo3.c
    10 Ian Pratt-Hartmann: Determinants and permanents Ian Pratt-Hartmann: Lab - Public-Key Cryptosystems
    11 Ian Pratt-Hartmann: How to pass the exam. Here is the paper we shall go through. Warning: on the exam this year, there are two compulsory questions.
    12(no lecture) Ian Pratt-Hartmann: Lab - Lexicographic Sorting

    Second Semester
    Easter break is 26th March - 13th April (between Weeks 8 and 9).
    Monday 7th May (Week 12) is a Bank Holiday.
    weekLECTURE LAB
    Semester 2 labs may include marks for correctness arguments.
    1Milan Mihajlovic: Data structures - Trees and Hash Tables. Correctness and complexity of algorithms. Slides 1, Slides 2, Slides 3 The labs this week (Week 1) are marking sessions only.
    2Milan Mihajlovic: Lab spellchecker
    3
    4David Rydeheard:
    Where do algorithms come from? Algorithmic techniques (1). Slides
    5David Rydeheard:
    Algorithmic techniques (2): Tractable and intractable problems. Slides
    Warning: To undertake this exercise you will need to read this material on the Knapsack problems. (See also the material in the Resources section above).

    Ian Pratt-Hartmann: Lab Application development - Knapsack problem (Examinable lab)
    6David Rydeheard. Graphs I: Applications, representations, basic algorithms, correctness and complexity. Slides
    7 Invited speaker: Prof. Martin Everett (Social Sciences): Social Network Analysis - modelling and analysis of communities using graph algorithms.
    Exam Feedback session: To be arranged in this period
    David Rydeheard. Graphs II: Traversal techniques
    8 Milan Mihajlovic: Lab Graph Representation and Traversal
    9 David Rydeheard. Graphs III: Survey of Graph Algorithms. Milan Mihajlovic: Lab Testing the small-world hypothesis (Examinable Lab).

    10Invited speaker: Prof. Andy Brass (Life Sciences and Computer Science): Genetic and protein matching - Knapsack techniques in action in life sciences and medicine.
    11 Revision lecture. Slides: Revision advice
    12A revision lecture may be arranged at a suitable time There are marking sessions this week at the usual lab times.
    This is normally your last chance to get lab work marked

    Assessment

    C programming is assessed only via the laboratory exercises.

    The full (two semester) course is assessed as follows:

    • 50% Laboratory
      • Semester 1 = 25%
      • Semester 2 = 25%

    • 50% Exam
      • January = 15%. This exam covers material on Algorithm Development, Algorithm Performance Measures and Complexity, sorting algorithms and other lectured material and that of the lab exercises. More details below.
        Format: 1.5 hours. 2 questions, answer both.
      • May/June = 35% On all the material of both semesters - except C programming. Details below.
        Format: 2 hours. Answer all questions.

    Guidance for the January Examination

    Format: 1.5 hour exam: 2 questions, answer both.

    The material covered in this exam is that of Semester 1, except that the C programming language is not examined (it is assessed in the laboratory exercises instead). Thus the exam covers Algorithm Development, Algorithm Performance Measures and Complexity, Sorting Algorithms and other lectured material and laboratory exercises in Semester 1, and related material in the course textbook.

    The syllabus is defined by the lecture slides. The slides also contain references to specific sections of the coursebook that it is necessary to read. It is expected that you do this reading. Bear in mind that lectures are for getting a general understanding of a particular topic; textbooks are for details. In a very few cases, the indicated sections of the textbook contain explanations of specific topics not addressed in the lectures. In such cases, it is reasonable to suppose that detailed questions about this material will not appear on the examination. On the other hand, understanding general techniques and method of approach is likely to be useful in answering examination questions.

    As always, the advice on scheduling revision is to start by getting a good general appreciation of the topics, and then progressively to deepen one's understanding. Never bet on a particular topic occurring: only a part of what we covered can be examined.

    Guidance for the May/June Examination

    (A) Examination Guidance

    The examination is 2 hours in duration. You are asked to answer all questions.

    Examinable topics are: Graphs and graph navigation, Trees and hashing, Optimisation and knapsack-type problems, Trees, graphs and associated algorithms. Two of the questions are based on material in laboratory exercises.

    You will need to know the material from both semesters to answer the questions successfully.

    (B) Revision Guidance

    A Revision Guidance document outlining the parts of the course textbook relevant for the summer examination should help in your revision.

    For samples of the kinds of questions you may be asked, see previous years' examination papers online (but the format may be different).

    Remedial Complexity and Maths

    Notes, questions and answers to help those who need additional mathematical support.

    Guidance for Resits

    If, after the summer examinations, you have performed poorly overall and also in this course unit, you may be asked to resit this course unit (either the laboratory exercises, the examination, or both). Here are some guidelines for your resits.

    If you have to retake laboratory exercises, marking sessions will be arranged in the resit period (see below for arrangements for resitting laboratory exercises).

    Assessment: To pass this course unit at the resit stage, your resit course-unit mark will be calculated as follows.

    50% Resit Exam mark

    Your marks from the January and May/June exams will be ignored, and you have to resit the exam even if you did well in one or both of the earlier exams.

    The resit exam will have the same scope (i.e. revise the whole year, not just one semester) as the May/June exam (see above).

    The Guidance for the summer (May/June) examination above is still relevant.

    50% Laboratory mark

    If part of the reason for you having to resit is that you failed the lab, you should try to improve your lab marks by attempting some of the lab exercises you didn't do (and/or maybe try to improve your marks for lab exercises you did badly in).

    Unless you have mitigating circumstances, late laboratory work will be limited to a maximum 40% as usual. We will apply this cut-off to the year as a whole, not to individual exercises or semesters, so one strategy would be to attempt most or all of the first semester lab exercises and perhaps also some second semester lab exercises. Remember, however, that two lab exercises (Small-world, and Knapsack) are examinable - i.e. there is an exam question relating to each of them - and it may help your revision to attempt those lab exercises.
    If you do have mitigating circumstances (e.g. medical problems), we may be able to give you full marks for extra lab work, please make sure that we are aware of this.

    If you do more lab work, you should submit it in the usual way. All resit laboratory solutions should be submitted before the resit examination period starts. This is a hard deadline.

    We will arrange a marking session around the time of the exams: look out for the announcement via email to your school account (you should make sure you read this, or forward messages to an account you read). To get your exercises marked you must attend the marking session and should be prepared to make arrangements to do so.