COMP26120: Algorithms and Imperative Programming (2018/19)


Acknowledgements: Parts of this course were developed by Joshua Knowles, Peter Jinks, Jon Shapiro, David Rydeheard, and Ian Pratt-Hartmann.


This year the course is being delivered by Giles Reger, Milan Mihajlovic and Lucas Cordeiro.

Aims

The course aims to:

The course 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: 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 cover the main algorithmic techniques and concepts but you will be required to explore these further.

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 (we provide a quick introduction in the course):

  • 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.

    • Second Core (but less referenced) text:
      Introduction to Algorithms
      by Cormen, Leiserson, Rivest and Stein
      ISBN 978-0-262-03384-8, MIT Press 2009

      Available at the University library etc

    • Main C text:
      C How to Program
      by Harvey M. Deital and Paul J. Deital
      ISBN 978-9332555310, Pearson 2015

    • List of Supplementary texts in the syllabus

    • We will provide lots of extra material in the labs for you to learn more about the topics being covered. Some of the links below may be obtainable only on the university network or via a VPN. If you ever find any additional material that you think would be useful to other students then do let us know and we will include it

    General Arrangements

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

    Laboratory sessions

    Labs are there for you to have your work marked and to ask questions to better understand the material. This year we are introducing a new marking system that will be used as follows:

    • To submit an exercise you will need to run submit from the command line as normal
    • Once this has been submitted our system will pick it up, compile it, and run some automated tests on your code to produce a report
    • You can log in to the system to view the reports of your submitted code (you can also use this to check that the submission worked)
    • In your marking session, when you want to be marked you should select request marking next to the exercise in the online system and enter your information
    • TAs will be notified that you are ready to be marked and use their version of your report (which may contain extra bits) to mark your work
    • Once the TAs submit your mark you should receive an email confirming it (if you do not please contact the course unit leader but wait a few hours first)
    • Note that the electronic marking queue aims to distribute TAs uniformly between students and gives priority to those being marked for the correct exercise in the correct marking session (if you go to the wrong marking session you will be at the end of the queue)

    Attendance in labs:

    • We will collect attendance in labs and this will appear in ARCADE
    • Attendance is not mandatory (there are no marks attached to it) but is strongly encouraged and missing a lab may lead to you not getting marked (see marking deadline below).
    • If you wish to ammend your ARCADE entry then you should talk to the lab manager in your lab session. If you miss a session for a legitimate reason (because of, for example, medical appointments, interviews, etc, or illness) and need to marked in a later session then talk to the lab manager and they will be able to remove you from the bottom of the marking queue
    • Only in exceptional circumstances contact a member of staff for these issues - ordinary messages will be ignored.

    Deadlines

    Each laboratory exercise has a standard deadline of the beginning of the next lab session. For example, if your lab sessions are 11:00-13:00 on Tuesdays then the deadline for the Week 2 lab is 11:00 on the Tuesday of Week 3. In certain cases the next lab session may not be the next week (e.g. for reading week). At the end of the Semester the next lab session is the first one of the next Semester. As per general School policy, there are no extensions and late flags should be removed via the standard mitigating circumstances procedure.

    If you decide to complete the exercise after the labs shut in the evening, it is your responsibility to make sure that you can submit remotely.

    As well as the standard submission deadline, there is a marking deadline: All exercises should be marked within 3 LABS of the submission deadline. Submissions not marked by this deadline will only be marked at the discretion of the lab manager. For example, if you submit something in week 2 you can have it marked in weeks 2, 3, or 4. The marking deadline may be relaxed if there is too much demand in labs. The best way to avoid this is to have your work marked in the week in which you submitted it. If you turn up to the lab and join the marking queue and still do not get marked then your individual marking deadline will automatically extend until the end of your next lab.

    Course schedule, lecture material and laboratory exercises

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

    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.

  • For suggested reading we use GT for Algorithm Design (core text), CLRS for Introduction to Algorithms, and DD for C How to Program. Note that for non-core-text material (CLRS and DD) this is suggested in the sense that it will help but is not core.

    All quizes are on Blackboard and will have a deadline on midnight on the Sunday at the end of the week. However, note that if there is a problem with Blackboard after 4pm on Friday you will not be able to get any help with this.

    First Semester
    weekLecturesSuggested ReadingLabsQuiz
    Welcome/Registration Week No laboratory session in Week 0 or Week 1.
    1Giles: Introduction - Algorithms and their PerformanceGT 1.1
    2Giles: From Java to C Lab 1 - Algorithm Design and Performance - some hints and tips.
    3Lucas: Pointers in C GT 2.1, DD 7 Lab 2 - Introduction to C - some necessary reading.
    4Lucas: Linked Lists in C GT 2.2, CLRS 10, DD 12 Lab 3 - Debugging; Arrays and Strings in C - some reading on debugging and pointers.
    5Lucas: Introducing Complexity Analysis GT 1.2-1.3, CLRS 2,3 Lab 4 - Linked Lists
    Reading Week GT 8.1-8.2, CLRS 4
    7Lucas: Divide and Conquer GT 9.1 Lab 5 - Iterative Sort, further information about sorting algorithms C Programming
    8Lucas: More on the Complexity of Recursive Programs GT 2.3 Lab 6 - Recursive Sort
    9Milan: Advanced Data Structures (binary trees, AVL trees, Hash tables). first lecture, second lecture, and third lecture. GT 4.2 Lab 7 - Pangolins, a bigger example of the game Complexity
    10 GT 5.3, 19.6
    11 GT 6.1-6.3 Lab 8 - Spellchecker (Deadline start of Semester 2) Data Structures
    12 Revision - overview and Lucas part
    Second Semester
    Easter break is 8th April - 29 April (between Weeks 10 and 11).
    Monday 6th May (Week 6) is a Bank Holiday so the revision lecture will be rescheduled.
    weekLecture Suggested Reading Lab Quiz
    1Milan: Graph Algorithms. Lecture 1, Lecture 2, Lecture 3 GT 13, 14 The labs this week (Week 1) are marking sessions only
    2Lab 9 - Representing Graphs (and some extension material)
    3Lab 10 - Testing the Small World Hypothesis
    4Lucas: Tractability and NP completeness. Lecture 4 Lecture 5GT 17, CLRS 34 Graphs
    5
    6Giles: Further Algorithmic Techniques GT 5 and CLRS 15,16 for Greedy and Dynamic. CLRS 29 for Linear Programming. Lab 11 - From Graph Colouring to Satisfiability Checking
    7 Lab 12 - The Knapsack Problem
    8Tractability and Techniques 1
    9
    10Giles: Number Theoretic Algorithms. Lecture 1 Lecture 2 GT 10.1-3. CLRS 31 Lab 13 - Public Key Cryptography There are no provided files for this lab, you should create your own makefile etc
    11Techniques 2 and Number Theoretic
    12Revision Lecture - Giles' Slides Lucas' Slides The labs this week (Week 12) are marking sessions only
    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% Coursework
      • Each Semester is worth 25%
        • Lab exercises = 20%
        • Blackboard Quizes = 5% (3 each semester)
      • The quizes test content covered in lectures and labs

    • 50% Exam
      • January = 15%. 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, 3 questions. 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 (broadly) covers the Divide and Conquer paradigm, Algorithmic Complexity, Sorting Algorithms, and (Advanced) Data Structures. Remember that topics from lectures and labs are examinable and some of these topics required further reading in the course textbook.

    The syllabus is defined by the distributed material, which may 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

    The examination is 2 hours in duration, with 3 sections. You are asked to answer all uestions. The sections are weighted as follows:

    • Section A: Graphs and Graph Algorithms [20 marks]
    • Section B: Complexity and NP completeness [10 marks]
    • Section C: Algorithmic Techniques and Number Theoretic Algorithms [30 marks]

    You will need to know the material from both semesters to answer the questions successfully -- Part C may make use of this material in its algorithmic design questions.

    New: find some mock revision questions for Part C here and here is the Mark scheme. These are (roughly) in the style that will be used in the exam. A marking scheme will appear here after the final revision session of the semester.

    Remedial Complexity and Maths

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