| Course Code | COMP6721 |
| Course Title | (In-)Formal Methods: The Lost Art |
| Course Email | cs6721@cse.unsw.edu.au |
| Convenor | Carroll Morgan |
| Course Admins |
Enzo Lee Solano
,
Paula Tennent
|
| Classes | Timetable for all classes |
| Consultations | By appointment. |
| Units of Credit | 6 |
| Moodle page |
https://moodle.telt.unsw.edu.au/course/view.php?id...
|
| Ed Forum | https://edstem.org/au/courses/11825 |
| Handbook Entry | http://www.handbook.unsw.edu.au/undergraduate/courses/current/COMP6721.html |
| Course text | Formal Methods, Informally: How to write programs that work. |
This course assumes the ability to write small imperative programs. It has been designed to be compatible with COMP1511; however other introductory programming courses should provide similar skills. "Python" is the main programming language used.
The material in this course looks simple, and it is easy to believe that it is elementary. But it is not, and that is the reason for the interactive style of presentation: it helps people to realise what they do not yet know.
The Student Code of Conduct ( Information , Policy ) sets out what the University expects from students as members of the UNSW community. As well as the learning, teaching and research environment, the University aims to provide an environment that enables students to achieve their full potential and to provide an experience consistent with the University's values and guiding principles. A condition of enrolment is that students inform themselves of the University's rules and policies affecting them, and conduct themselves accordingly.
In particular, students have the responsibility to observe standards of equity and respect in dealing with every member of the University community. This applies to all activities on UNSW premises and all external activities related to study and research. This includes behaviour in person as well as behaviour on social media, for example Facebook groups set up for the purpose of discussing UNSW courses or course work. Behaviour that is considered in breach of the Student Code Policy as discriminatory, sexually inappropriate, bullying, harassing, invading another's privacy or causing any person to fear for their personal safety is serious misconduct and can lead to severe penalties, including suspension or exclusion from UNSW.
If you have any concerns, you may raise them with your lecturer, or approach the School Ethics Officer , Grievance Officer , or one of the student representatives .
Plagiarism is defined as using the words or ideas of others and presenting them as your own. UNSW and CSE treat plagiarism as academic misconduct, which means that it carries penalties as severe as being excluded from further study at UNSW. There are several on-line sources to help you understand what plagiarism is and how it is dealt with at UNSW:
Make sure that you read and understand these. Ignorance is not accepted as an excuse for plagiarism. In particular, you are also responsible that your assignment files are not accessible by anyone but you by setting the correct permissions in your CSE directory and code repository, if using. Note also that plagiarism includes paying or asking another person to do a piece of work for you and then submitting it as your own work.
UNSW has an ongoing commitment to fostering a culture of learning informed by academic integrity. All UNSW staff and students have a responsibility to adhere to this principle of academic integrity. Plagiarism undermines academic integrity and is not tolerated at UNSW. Plagiarism at UNSW is defined as using the words or ideas of others and passing them off as your own.
If you haven't done so yet, please take the time to read the full text of
The pages below describe the policies and procedures in more detail:
You should also read the following page which describes your rights and responsibilities in the CSE context:
| Name | Information | Dates |
|
Weekly Quizzes (50%)
|
The weekly quizzes are short, time-limited checks of your ability to use the skills you will be taught in the course. There will be 9 quizzes in total, i.e. one per week excluding flex week. They will be presented on Moodle, and are usually multiple-choice.
Each quiz must be finished within a fixed amount of time from starting it; but you will be allowed two attempts, from which the maximum mark will be taken. Each attempt must be completed within a fixed amount of time, typically 30 minutes. Your quiz marks will be available as the course progresses; but individuals' marks-per-question are not released. |
Released every Friday at 12pm; due the following Monday at 11:59pm.
No late submissions are allowed. |
| Assignment (40%) |
This year's assignment is different in style from last year's. It is still a programming project, but you will not be asked to hand-in code to be tested by us. Instead, you will be guided through steps that will create a small (but still intricate) program by the end of the term, using the techniques this course will have taught. You will be invited however optionally at various points to type in small program-fragments and test them yourself .
The assignment will be in 9 "portions", one per week. In each week, a prefix of the whole assignment text up to the end of that week will be available.
Students will see the assignment questions – its specification – in each week's portion, but will not see the possible (multiple-choice) answers until they open as a Moodle quiz, later in the week. You are strongly advised to think about possible answers to the portion for the current week during the week , so that you can simply pick the best multiple-choice answer(s) when you actually see them at the end of the week. If you wait until the possible answers are available, it might take you much longer to pick the correct one. More explanation of how the assignment works will be given in the first lecture (Tuesday Week 1). |
Each week's Assignment
specification
is released at 10am on Tuesday.
The Assignment's possible answers are however not opened until 12pm on the Friday of the same week, and the answers close at 11:59pm on the Monday after that. Thus the whole week is available for deciding what your answers should be; but you can only select an answer from Friday afternoon until Monday midnight. You are allowed only one attempt at giving the answers to the Assignment portion for each week. Each attempt must be completed with a fixed amount of time, typically 30 minutes. Late submissions are allowed for assignment pieces, but they will be penalised using the stardard UNSW criteria. * |
| Participation (10%) |
Participation marks are based on how much students actively engage with the lecturer, tutors and each other (eg on the course forum).
In particular, in-person attendance at lectures is expected.
Friday's lecture will however be in a tutorial style (with both tutors present as welll as the lecturer), in a setting where students will be split into small groups and given interesting problems to work on. The staff (the three of us) will answer questions. It is a good opportunity for participation. |
Students should enter every week a (small) amount of text into Moodle explaining how they participated.
The participation entries for each week opens at 10am on Tuesday, and closes at 11:59pm the following Monday. No late submissions are allowed. |
| Exam | There is no final examination for this course. |
*The standard UNSW late penalty is to take 5% off your mark for each day you have submitted late; with no submissions allowed after 5 days.
The Tuesday lecture (2 hours) is in Ainsworth 202, Wednesday's is in Old Main Building (OMB) 230 and Friday's lecture/tutorial is in Elec Eng G09.
| Week | Day | Topic (provisional unless already occured) | Slides presented in lectures | ||
| 1 | Tuesday lecture (2 hours, Ainsworth 202) | Introduction and welcome; first "what's true here" programming explanation and justification. | These will be available via Moodle after the lectures in which they are used. | ||
| Wednesday lecture (1 hour, OMB 230) | Administration issues; explanation of assessment strategy. "Summing a sequence", "Longest no-repeated letters" and other examples. | (As above, for here and all Tuesday, and Wednesdays following. The Friday lecture/tutorial will not have slides.) | |||
| Friday lecture/tutorial, with students separated into small groups (1 hour, Elec Eng G09) |
Binary-Search exercise, done in groups.
Selection from Exercises 1.4, 1.6, 1.8, 1.11, 1.14, 1.20 and Drills A.1, A.2. |
|
|||
| 2 | Tuesday | Justification for the program-checking rules; example of effectiveness of WTH approach ("No repeated letters" example, a simpler verion of text's Chapter 2); "exotic" WTH patterns (REPEAT, BREAK, CONTINUE). | |||
|
Wednesday
|
Propositional calculus (Appendix D.4). | ||||
| . | Friday | Selection of drills (A.6, A.8, A.10, A.11) and exercises (D.10,D.11) --- plus exercises reinforcing last week's material (Exx. 1.[2,3,4,9,16]). | |||
| 3 | Tuesday | Linear-time exponential (example of invariant-based reasoning); log-time exponential (eg as used in RSA). | |||
|
Wednesday
|
Historical origins (a glimpse): Floyd's paper 1967; Hoare's paper 1969; Dijkstrat's paper 1975. All three available in "This week's slides". | ||||
|
|
Friday | Likely to be Exx 1.17, 1.18, 3.1, D.14 and Drills A.12, A.14(7,8). Possible "fill in handout" (as we did for Binary Search in Wk 1). | |||
| 4 | Tuesday | Maximum segment sum (and product). | |||
|
Wednesday
|
Variants for termination. | ||||
| Friday |
Exx 4.1, 4.84.15, 4.18 on variants.
Exx 5.2,5.4 (recommended) And Ex 4.3 which I can't do myself. |
||||
| 5 | Tuesday | Binary search. Beginning of longest upsequence. | |||
|
Wednesday
|
Continuing longest upsequence. | ||||
|
|
Friday |
Another chance to fill-in Binary Search! And "All roads lead to Rome."
Drills A.4, A.5, A.17. Exercises 3.1, 3.10, 2.12, 3.22. |
|||
| Flex week |
|
||||
| 7 | Tuesday | Coupling-invariant example: Fast Fibonacci. Data-type encapsulation example: the Mean Calculator. | |||
|
Wednesday
|
Representing a set as a sequence; data-type invariants.
|
||||
|
Friday |
Q&A on Weeks 1-7 and/or assessment so far.
Exercises |
|||
| 8 | Tuesday |
|
|||
|
Wednesday
|
The Owicki-Gries method. Critical sections. Liveness and safety.
|
||||
| Friday | Q&A on Week 8, and circular buffer example. | ||||
| 9 | Tuesday |
Misra's derivation of Peterson's algorithm via a coupling invariant.
|
|||
|
Wednesday
|
Further on data refinement (extending Week 7, and treating assume). Examples, including circular buffer. | ||||
| Updated to here 230722. | Friday | ||||
| 10 | Tuesday (tentative) | Probabilistic correctness, and probabilistic variants. | |||
|
Wednesday (")
|
Automatic assertionn checking (Dafny). | ||||
| Friday |
Texts and recommended readings:
Last year the assignment was found to be (too) difficult for some of the students, and did contain an error at one point. Also, it was structured in several parts where the later ones depended too much on the earlier ones. There was a also perception among some students that the assignment was poorly worded (although it had been used in previous years and had not attracted such comments then).
Indeed the lecture slides were not themselves sufficient to use as a primary source for the course material, and were not designed to be. For that there is (and was) a textbook written especially for the course, and it is available to the students. It will be made clearer this year that they should refer to it.
There was an (unfounded) perception that lecture attendance was compulsory. It was not. But not every course is suited to online presentation only, and this is one such case. Attendance at lectures was strongly recommended last year, and remains so this year.
In summary: this year (1) a completely different style of assignment is being used; (2) there is one hour per week devoted to "problem solving" in small groups with supervision; and (3) there are two teaching assistants (instead of one, as last year) who, together with the convenor, will be organising the problem-solving session and assisting where needed.
Resource created Monday 03 April 2023, 12:41:58 PM, last modified Saturday 22 July 2023, 03:50:13 PM.