Notices

  • Formatif results & thanks

    Posted by Paul Hunter Friday 17 May 2024, 10:36:29 AM, last modified Friday 17 May 2024, 10:37:18 AM.

    Hi all,

    This should (hopefully) be the final message from me for this course. Thank you all for seeing it through to the end, it is always pleasing when the number of exam submissions is more than 90% of the number of people that started the course. I hope that you were largely satisfied with your final results for COMP4141. Quite a few of you have shown a real aptitude for this subject, and I hope that many of you continue to explore Theoretical CS. On that note, I will be continuing my "Advanced Topics in Theoretical CS" gathering next term, so please drop me an email if you are interested in being included on the email list.

    A big shout out to Ian, Simon, Mathieu, Mark, and Isaiah (and Gerald) for all the work they've done throughout the term. For anyone still around next year, I'm always on the lookout for tutors.

    I did not realise that you are unable to see your final formatif assessments (and comments) in formatif. To rectify this, I've set up a small script here:

    https://cgi.cse.unsw.edu.au/~cs4141/cgi-bin/formatif?term=24t1

    which will pull your final formatif grade and any comments the assessors had. This will require you to login with your zid & zpass.

    The forum will remain open for a couple more weeks. The exam is now (effectively) public domain, so feel free to discuss questions/solutions.

    I'd like to finish with my favourite (almost) proof from the exam, this idea for Q3b (prove that L(G)⊆L(E)) (I've elaborated a little):

    • Construct an NFA, M, for L(E)ᶜ:
      • Construct an NFA, N, for L(E)
      • Convert N to a DFA D via subset construction
      • Swap the accepting and non-accepting states of D to obtain M
    • Construct a PDA, P, for L(G)
    • Construct a PDA, Q, for L(G)∩L(E)ᶜ by taking the product construction of P and M
    • Convert Q to a CFG, G'
    • Check if L(G') is empty (e.g. via a marking+backtracking algorithm)

    Quite a nice use of results from lectures without having to dip into induction...

    Thank you all again,

    Paul


  • Final exam errata

    Posted by Paul Hunter Monday 29 April 2024, 12:27:57 PM.

    Hi all,

    I've just been made aware of a typo in the exam - notably Q8.

    The correct definition of the Transitive Reduction problem is:

    Input: Directed graph G = (V,E) and an integer k.

    Question: Is there a subset R ⊆ V×V with |R|≤k such that

    (v,w) ∈ R* if and only if there is a path from v to w in G.


    Here R* is the transitive closure of R


    I have updated the exam specification file. Please make sure you have the latest copy.

    This will be the last update to the exam - if there are any more issues found, then please use your best judgement and state clearly any assumptions you need to make.

    Paul

  • Final exam now available

    Posted by Paul Hunter Monday 29 April 2024, 09:06:29 AM.

    Hi all,

    The final exam is now available here: https://webcms3.cse.unsw.edu.au/COMP4141/24T1/reso...

    Unless I have contacted you already, your submission is due, through webCMS/give, at 9am (Sydney time) on Tuesday April 30.

    A reminder that this should be taken under exam conditions - in particular accessing active resources (e.g. contacting other people, collaborating with students, posting questions on forums) is strictly forbidden. You may access passive resources (i.e. any material existing prior to the start of the exam) with adequate referencing - but you should use these with caution as you are being assessed on your ability, understanding, and extensibility (so you should be making every effort to demonstrate these qualities with your answers). The ed forum will be set to private messages only for the duration of the exam.

    You may make as many submissions as you like - the latest submission received before the due date will be what you will be marked on. I strongly suggest making a dummy submission asap to check if there are any issues with the submission. As long as you submit a pdf you should see a message saying your submission was ACCEPTED.

    If there are any questions/issues, please contact me asap.

    Paul

  • Portfolio creation due date extended

    Posted by Paul Hunter Sunday 28 April 2024, 02:12:53 PM.

    Hi all,

    I've had a few queries about portfolio creation being disrupted because of slow formatif feedback.

    The principle I intend to adhere to is that for any submission made before April 21st AOE :

    (a) will receive feedback; and

    (b) you will have an opportunity to respond to that feedback in order to complete the task

    Submissions made before April 28th but after April 21st will be eligible for "partial completion" - that is, they will receive some feedback, but they will only provide partial evidence for overall assessment. Likewise if you choose not to respond to your feedback you may consider your task partially complete (as would be the case with an assignment where you do not have the opportunity to respond to feedback)

    Due to unforeseen circumstances among the teaching staff, (a) is playing out slower than I hoped/expected. I am pushing to get every submission through some feedback before the exam release, but the delay means that you have not had the opportunity for (b).

    While it is possible (and acceptable) to create a portfolio without including these partially processed tasks, I understand that some of you may prefer to include the later tasks rather than the earlier tasks as evidence for your grade. So you should have the opportunity to complete the task if you made a timely submission.

    As every task should have some form of feedback in the next 24 hours, and a portfolio creation is not something that needs to be done prior to the final exam:

    * Responses to feedback on timely submissions (i.e. submissions before 21st April AOE) will be accepted up to May 4 AOE .
    * Portfolios must be completed by May 5 AOE .

    Paul

  • Final exam information

    Posted by Paul Hunter Sunday 28 April 2024, 05:03:32 AM.

    Hi all,

    Sorry I didn't realise that I hadn't confirmed the details for the exam.

    The exam will be released on webCMS at 9am on Monday 29th April.

    You need to submit, through webCMS (or give), your solutions by 9am on Tuesday 30th April.

    For those students with another exam at the same time, I will be in touch with alternative arrangements.

    Paul

  • Formatif submissions

    Posted by Paul Hunter Friday 19 April 2024, 03:29:34 PM, last modified Friday 19 April 2024, 03:30:18 PM.

    Hi all,

    Just to clarify the situation with formatif.

    • Any task submitted before April 25th (AOE) will receive feedback.
    • Submissions should be considered your best attempt - because of time constraints you will only have one opportunity to improve your submission based on feedback.
    • Submissions not marked as complete by April 28th may be eligible for partial completeness
    • Solutions will be released on April 25th - submissions/responses after this time need to demonstrate originality: they should either be based on feedback of a previous submission; or significantly different from the posted solution.

    I will follow up with a post about portfolios in the next few days but the intention is:

    • You complete a portfolio by 28th April - it shouldn't take too long to complete, so this should not disrupt your exam preparation.
    • Your portfolio should consist of an estimate of the grade you believe you deserve (after self-reflection): {Top, Middle, Bottom} × {HD, D, C, P}. In addition to tasks completed, factors to consider are how much assistance you needed to complete the tasks; how well you understand your final solution; whether you completed tasks at the level expected of your estimated grade (e.g. completing tasks of lower grades at a level appropriate for your target)
    • You provide evidence supporting your estimated grade (e.g. your best solutions) - note this doesn't necessarily mean only HD-task solutions if you're aiming for an HD; an excellent solution to a C-task may be something worth including.
    • We will evaluate your formatif submissions, guided by (but not dictated by) your portfolio.

    The purpose of the portfolio creation is to provide you with some self-reflection on what you've learned over the course. It can be very instructive to look back at your own understanding of the concepts at the start of the course and see how they have changed over the past 10 weeks.

    Paul

  • Formatif due dates

    Posted by Paul Hunter Tuesday 16 April 2024, 09:52:40 PM.

    Hi all,

    Sorry I forgot to update the formatif tasks with the information I've been passing around.

    Please try to complete your formatif submissions by 21 April (AOE). This should give your tutors sufficient time to give feedback and for you to respond before the exam date. Extensions are still acceptable, but note that this may limit opportunities for feedback.

    Paul

  • End of term pizzas tomorrow!

    Posted by Paul Hunter Tuesday 16 April 2024, 09:00:03 PM.

    Hi all,

    Even though we still have two lectures to go, I thought I'd bring forward the end of term celebration to the end of tomorrow's lecture (because Wednesday's lecture always seems to be the more popular one)

    So tomorrow's lecture will conclude with pizzas! (Don't worry I'm tasking Simon with collecting them so they'll be hot)

    So if you haven't come to a lecture in person yet - make tomorrow's lecture the one you come to!

    Paul

  • Consultation tonight moved to Wednesday

    Posted by Paul Hunter Monday 15 April 2024, 03:55:36 PM.

    Hi all,

    Apologies for the late notice, but tonight's consultation will have to be delayed until Wednesday 7:30PM (AEST)

    Paul

  • Friday lecture delay

    Posted by Paul Hunter Friday 05 April 2024, 09:58:05 AM.

    Traffic today is terrible. Today's lecture will be delayed by my late arrival.

  • Online consultation

    Posted by Paul Hunter Wednesday 06 March 2024, 05:22:48 PM.

    Hi all,

    Now that term has settled down and I have a clearer picture of my commitments, I am able to arrange an online consultation time to address any questions you might have - especially questions that (for whatever reason) haven't been able to be addressed in your tutorials.

    The consultations will be on MS Teams , and will be from 7:30pm (Sydney time) on Mondays (starting next week) . The link is also available on the course website in the menu under "Links for online content".

    These are student-driven and optional. They are intended to supplement tutorials, not replace them.

    For the moment these will not be recorded (to encourage participation) - but if there is adequate student involvement to have productive sessions then this may change.

    If you would like to attend, but cannot make this time (or may be a little late) then please let me know.

    Paul

  • Welcome to COMP4141

    Posted by Paul Hunter Wednesday 14 February 2024, 06:12:42 AM.

    Hi all,

    Welcome to COMP4141 Theory of Computation. This is just a brief announcement to introduce you to various aspects of the course: the website, the learning interfaces, and the staff (me).

    I encourage you to familiarise yourself with the course website:

    http://www.cse.unsw.edu.au/~cs4141

    as it provides the starting point for all aspects of the course.

    Lectures begin today at 11am in NS Global Theatre Lectures will be recorded, and the recording will be available shortly after the lecture finishes.

    Tutorials begin today. Details of tutorials will be available on the course website presently.

    You will shortly receive an email inviting you to join the course forum on ed. The course forums also provide a platform to ask questions and discuss the course material.

    Looking forward to meeting you later today

    Paul Hunter
    (Lecturer in Charge)


Back to top

COMP4141 24T1 (Theory of Computation) is powered by WebCMS3
CRICOS Provider No. 00098G