COMP26120: Algorithms and Imperative Programming (2019/20)


This is not the current version of this page, please go to this page for the current page.

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


This year the course is being delivered by Giles Reger, Lucas Cordeiro, and Peter Lammich

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. In addition to the General Lab Instructions (which you need to read), there are some specific 26120 instructions due to the use of the COMPjudge system form marking.

    The workflow for submission and marking is as follows:

    • Follow the general instructions for submitting via Gitlab e.g. each exercise should be completed in its own branch. In addition to these instructions, for each new exercise you should
      • To start, run git checkout ex-short-name where ex-short-name is, for example, ex3
      • Immediately after this, run ./refresh.sh - this rebases your branch on top of the original repository and ensures that the starting material is up-to-date in case any changes were made since the initial fork. Always run this at the start of each lab. Running this after you have started may require you to resolve conflicts.
      • Once you have finished (or want COMPjudge to run tests) run ./submit.sh - this script adds a tag to your last commit and pushes this. If submission is not working try reading the comments in ./submit.sh
      These two scripts should already be in the repository.

    • Once your work has been submitted, COMPjudge will pick it up, compile it, and run some automated tests on your code to produce a report. The workflow surrounding COMPjudge is as follows:
      • You can log in to COMPjudge 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
    • 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).
    • As attendance is not mandatory we will not normally update a record of missed attendance but you can talk to the lab manager if you need to do this for some reason.

    Deadlines

    Important: In this course (for the first time) we have placed the deadlines after we expect you to have completed the work and had the work marked. Our expectation is that you complete work before the next lab session and attempt to get marked in this next lab session. If you repeatedly wait until the deadline to submit you will fall behind with work and will run the risk of missing marking deadlines (see below). Therefore, the deadline is there as a final encouragement to complete work that you should already have completed.

    All lab groups share the same deadline of the end of the week following the last lab session (e.g. Friday at 6pm). In certain cases this may not be the next week (e.g. for reading week). At the end of Semester 1 we allow some overlap with the beginning of Semester 2. Check the official pages (and COMPjudge) for the actual deadlines.

    As per general School policy, we do not issue extensions for individuals but late flags may be removed via the standard mitigating circumstances procedure. In exceptional circumstances the deadline may be extended and in such cases you will be informed - see here for the rules and a link to the form.

    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 in the 3 Labs after the last lab session on that exercise. COMPjudge contains details of marking deadlines.. The reason for the marking deadline is to encourage you to get your work marked as soon after you complete it as possible and to balance time available for marking.

    Submissions not marked by this deadline will only be marked at the discretion of the lab manager. For example, if a lab has a deadline at the end of 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 at 6pm on the Friday at the end of the week. However, note that if there is a problem with Blackboard outside of core hours you will not be able to get any help with this.

    You can also access all lab material on COMPjudge

    First Semester
    weekLecturesSuggested ReadingLabsQuiz
    Welcome/Registration Week No laboratory session in Week 0 or Week 1.
    1 Lucas: Introduction - Algorithms and their Performance GT 1.1
    2 Lucas: From Java to C Lab 1 - Algorithm Design and Performance - reading material
    3 Lucas: Pointers in C GT 2.1, DD 7 Lab 2 - Introduction to C - reading material
    4 Lucas: Linked Lists in C GT 2.2, CLRS 10, DD 12 Lab 3 - Debugging; Arrays and Strings in C - reading material on pointers and arrays and debugging C programs
    5 Lucas: Introducing Complexity Analysis GT 1.2-1.3, CLRS 2,3 Lab 4 - Linked Lists
    Reading Week GT 8.1-8.2, CLRS 4 Reading Week
    7 Lucas: Divide and Conquer GT 9.1 Lab 5 - Spellchecking - reading material on sorting and a online tool to help. C Programming
    8 Lucas: More on the Complexity of Recursive Programs GT 2.3
    9 Giles: Advanced Data Structures GT 4.2 Complexity
    10 GT 6.1-6.3
    11 GT 5.3, 19.6 Lab 6 - Priority Queues
    12 Revision Data Structures
    Second Semester
    Easter break is 30th March - 17 April (between Weeks 9 and 10).
    Friday 8th May (Week 12) is a Bank Holiday.
    weekLecture Suggested Reading Lab Quiz
    1 Peter: Graph Algorithms. GT 13, 14.1-3, CLRS 22 and 24 Marking sessions (note that Lab 6 of last semester is due at the end of this week).
    2 Lab 7 - Graphs tests.sh (annotated) expected output
    3
    4 Peter: Tractability and NP completeness GT 17, CLRS 34 Graphs
    5
    6 Lab 8 - Graph Colourability (This lab is formative only e.g. whilst you are encouraged to submit for marking, it does not count towards your final grade)
    7 Peter: Algorithmic Techniques GT 10,12 and CLRS 15,16 for Greedy and Dynamic. Lab 9 - The Knapsack Problem Tractability and Techniques
    8 Giles: Due to lecture cancellations, we are releasing last year's lectures as podcasts. As last year's slides make small references to my lectures on greedy algorithms and dynamic programming I have also included these. However, Peter's lecture should be the main reference for examinable material. See podcast site for lectures, here are the slides: GT 26, CLRS 29
    9
    10 Giles: Number Theoretic Algorithms (last year's slides). GT 24.1-3. CLRS 31 Lab 10 - Public Key Cryptography
    11 Linear Programming and Number Theoretic
    12 Revision Lecture The labs this week (Week 12) are marking sessions only
    This is normally your last chance to get lab work marked

    Pointers to Additional Online Material

    This is being added to augment the last four lectures. If you have any suggestions please send to Giles.

    Linear Programming

    There are a lot of vidoes on YouTube about linear programming. Most look okay. Here are a few I watched:
    • This video gives a detailed example expressing an optimisation problem similar to the Farmer example given in the first lecture.
    • This video gives a simple overview of the graphical meaning of a linear program
    • This video focusses on how to translate an English problem into a linear programming problem (and then solving it graphically)

    Simplex Algorithm

    There are a lot of online tools that run the Simplex algorithm and show you what's going on. For example, I like this one as it has a very simple interface, although it can be a bit fragile.

    There are also a lot of videos on YouTube and the best one for you is probably personal preference. I found this video to be nice.

    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%.
        Format: 1.5 hours. This year this exam will be online for the first time
      • May/June = 35% On all the material of both semesters - except C programming.
        Format: 2 hours. Answer all questions.

    Remedial Complexity and Maths

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