Course Outline
Course Staff
- Lecturer: Raveen de Silva (z3372617)
- Tutors: Kevin Zhu (z5206576), Paula Tennent (z5255101), Angus Ritossa (z5311370)
Email me at r.desilva@unsw (complete the rest).
Thanks to Steven Fan, Tim Lambert, Greg Omelaenko and Ray Li for all their work in setting up this course and creating resources in previous years.
Class Details
| Class | Instructor | Weeks | Day and Time | ||
| Lectures | Raveen | 1–10 | Tue 13:00 - 16:00 | Zoom link | Recordings |
| Consultation | Raveen | 1–10 | Tue 17:00 - 18:00 | Zoom link | Recordings |
| Tute/Lab W13A | Kevin | 1–5, 7–10 | Wed 13:00 - 16:00 | Zoom link | Recordings |
| Tute/Lab W13B | Paula | 1–5, 7–10 | Wed 13:00 - 16:00 | Zoom link | Recordings |
| Tute/Lab F10A | Angus | 1–5, 7–10 | Fri 10:00 - 13:00 | Zoom link | Recordings |
Additional consultations will be held during the exam period, schedule TBA
Course Summary
- Introduction
- Data Structures
- Dynamic Programming
- Graphs
- Data Structures II
- Shortest Paths
- Network Flow
- Mathematics
- Dynamic Programming II
There is a tentative course schedule below.
Course Aims
This is a course designed to introduce advanced problem solving techniques to those who have already mastered the fundamentals of programming. A particular emphasis will be made on modifying existing algorithms to solve new problems in a novel way. Students will not only develop theoretical approaches to challenging problems, but also implement them.
Learning Outcomes
Upon completing this course, students will have mastery in applying various algorithms and data structures to solve competition-style problems, including implementation in C++.
Assumed Knowledge
- Students are assumed to have a thorough understanding of basic algorithms and data structures, as covered in COMP1511 and COMP2521.
- Students will benefit from having some familiarity with more advanced algorithms and data structures, as covered in COMP3121 or COMP3821.
- Students are expected to be proficient in C or C++, as all coding in this course will be in C++. A detailed understanding of C++ classes from an object-oriented perspective is not required, but we will make use of STL and structs with member functions.
Teaching Strategies
Lectures will introduce the theory behind the algorithms and data structures used in the course, as well as providing examples of applications to problems of varying difficulty.
Tute/labs will provide students further guided examples, and an opportunity to practice implementing these algorithms and receive guidance on how to solve problems using the concepts introduced in lectures.
Teaching Rationale
This course extends COMP3121/3821 to include applications of problem-solving techniques, in order to code solutions to problems, particularly in the style of programming contests. As such, the course trains students to solve problems in this field across a variety of topics, including under time constraints.
Assessment
| Problem Sets | 40% |
| Problem Diary | 8% |
| Contests | 18% |
| Final | 34% |
2 bonus marks will be provided for participation in the South Pacific Divisional contest.
Problem Sets
At the start of every week except weeks 6 and 10, a set of 5 problems will be released on vjudge, usually due two weeks later at midnight. The exact deadline will be listed in the problem set.
Each of the 8 sets will be worth 5% of the overall course mark, for a total of 40%.
Solutions must be implemented in C++.
Thanks to Jaehyun Park for advice on the problem sets.
Problem Diary
For each problem set, a diary entry should also be submitted, explaining the process by which the solution was arrived at, and reflecting on any challenges encountered. The diary should be submitted no later than 48 hours after the problem set deadline.
Each submission should be a PDF of no more than three pages, excluding code snippets. It may often be acceptable to submit a diary entry of much less than this limit!
You are encouraged to include any progress made on problems which you did not solve.
Each of the 8 diary entries will be worth 1% of the overall course mark, for a total of 8%. Any submission demonstrating sufficient effort will receive the mark.
Contests
A long contest (5 problems, 48 hours) will be held in week 1. This contest is intended to be comparable in difficulty to a COMP2521 practical exam.
Two short contests (3 problems, 3 hours) will be held in weeks 4 and 9.
Each contest will be worth 6% of the overall course mark, for a total of 18%.
Final Exam
The final exam will be a long contest (approx 8 problems, 6 hours).
If it is necessary to break ties within the same course mark to obtain rankings, e.g. for first place, ties will be broken based on ranks obtained from the final exam according to ACM-ICPC scoring rules.
Academic Honesty and Plagiarism
- For problem sets, students are encouraged, but any code must be derived and written separately, and any collaboration must be acknowledged in a header comment.
- The course materials should be sufficient to complete the problem sets. If you use external resources, they must be general in nature (i.e. not specific to the problem in question) and must also be acknowledged in a header comment.
- Problem diaries must be completed individually.
- The contests and final exam must be completed individually without any collaboration with other students or third parties.
- Copying or purchasing code from external sources is unacceptable.
- There are serious consequences for plagiarism. The university’s policy can be found here. The School policies are located here.
Student Equity and Accessibility
Please contact me (r.desilva at unsw) if you require provisions for disabilities, or if you encounter other challenges during the term, and we will do our best to accommodate your needs.
Course Schedule
| Week | Lecture | Lab | Assessments |
|---|---|---|---|
| 1 | Intro | Intro | Contest 1 |
| 2 | Data Structures I | Data Structures I | |
| 3 | Dynamic Programming | Dynamic Programming | |
| 4 | Graphs | Graphs | Contest 2 |
| 5 | Data Structures II | Data Structures II | |
| 6 | Revision Lecture | ||
| 7 | Shortest Paths | Shortest Paths | |
| 8 | Network Flow | Network Flow | |
| 9 | Mathematics | Mathematics | Contest 3 |
| 10 | Dynamic Programming II | Revision |
A problem set will be released at the start of every week except weeks 6 and 10 (TBC). Each will typically be due in 2 weeks.
Resources for Students
- The course website will contain all relevant resources, and there are no textbooks required for the course.
- The following textbooks are suitable for reference:
- Any algorithms textbook, such as Introduction to Algorithms (Cormen, Leiserson, Rivest and Stein) or Algorithm Design (Kleinberg and Tardos)
- Programming Challenges (Skiena and Revilla)
- Competitive Programming 3 (Halim). A free copy of Competitive Programming 1 can be found at CPBook
- Students may find the following online resources helpful:
- CP-Algorithms (and the more comprehensive but Russian Emaxx)
- Topcoder Tutorials
- There are many helpful blogs, particularly on Codeforces (a partial list here). Some select choices:
- Further practice problems can be found in many places, e.g:
- Students are encouraged to ask the lecturer or tutors for further resources.
Course Evaluation and Development
This course is evaluated each session using the myExperience system.
In the previous offering of this course, students reported that they liked the inclusion of subtasks in Contest 3 and wanted this extended to Contest 2.
Based on their comments, we will offer subtasks in Contest 2.