Course Description

How do competitive programmers solve complex problems in a matter of minutes?

In this course, you will design and implement advanced algorithms to solve problems accurately and quickly. You will discover sophisticated applications of dynamic programming, data structures, graph algorithms, mathematics and more. Most importantly, you will learn to deconstruct a problem in order to evaluate which algorithm design techniques are appropriate, combining ideas from different contexts, and address the challenges that lie in both solving the problem conceptually and producing a C/C++ program which enacts your solution. Can you rise to the challenge?

Teaching Strategies and Rationale

Lectures will introduce students to a suite of algorithm and data structures, including their implementation in C++ and application to a variety of example problems from programming contests. This content can be supplemented by textbook readings and self-directed practice contests.

Tutorials will give students an opportunity to practice these techniques as they work in groups to solve curated problems following similar themes to the lecture content.

Labs will allow students to work on their problem set portfolio with guidance from the demonstrator and by collaborating with peers as appropriate. This allows students to learn in a relaxed and supportive environment before later showcasing their skills as they work independently and under time constraints in the assessments.

Course Aims

It is common for computing professionals to be faced with challenging problems that require both algorithmic thinking and skillful programming to solve. The aim of this course is to train students in the implementation of solutions of such problems, focusing on accuracy, efficiency and speed.

Class Details

Common

Class Weeks Day and Time Location Link
Lecture 1–10 Tue 14:00 - 16:00 E19 (O’Shane) G02 Echo360 (link TBA)
Consultation 1–10 Tue 16:00 - 17:00 K17 (CSE) 202  
Lecture 1–10 Thu 14:00 - 16:00 K15 (Old Main) G31 Echo360 (link TBA)
Consultation 1–10 Thu 16:00 - 17:00 K17 (CSE) 202  

Lectures will be delivered in hybrid mode; you can attend in person or watch the Echo360 live stream, which you can access through Moodle. The same link will also give you access to recordings of past lectures.

Please email me if you would like a consultation (likely online) outside of the specified hours.

I will hold additional consultations during the exam period, schedule TBA.

Tute/Labs

You can find the full tute/lab timetable here. The online tute/lab W14B will be conducted using Blackboard Collaborate, which you can also access through Moodle.

Course Learning Outcomes

  1. Design and implement solutions to unfamiliar problems.
  2. Demonstrate an understanding of the practical aspects of the material covered in the course.
  3. Complete all phases of solving a problem (identifying, combining and implementing approaches) under tight time constraints.

Assumed Knowledge

  • The prerequisite for this course is COMP3821/9801 (or COMP3121/9101 and 75 WAM).
  • 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, although much of the material is reintroduced.
  • 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. However, students must be able to write, test and debug relatively short programs in C, and familiarity with the C++ Standard Template Library will be developed early in the term.

Platforms

  • This course website is the central resource for everything COMP4128.
  • The Moodle site only exists to host lecture streams/recordings and the online tute/lab session W14B.
  • Weekly problem sets are hosted on vjudge. Make an vjudge account using your zID as the username, and join our group.
  • Contests and the final exam are hosted on DOMjudge. Register here using your zID as both the username and team name, and providing your full (preferred) name.
  • Join the Ed forum here, using your UNSW email address (e.g. z1234567@unsw.edu.au).

Course Schedule

Week Tuesday Lecture Thursday Lecture Tute/Lab Problem Set Contest
1 Intro Getting Started Getting Started PS1 released Contest 1
2 Paradigms Data Structures I Paradigms PS2 released  
3 Data Structures I Dynamic Programming Data Structures I PS3 released  
4 Dynamic Programming Graphs Dynamic Programming PS4 released  
5 Graphs Shortest Paths Graphs PS5 released Contest 2
6 TBA TBA No class    
7 Shortest Paths Data Structures II Shortest Paths PS6 released  
8 Data Structures II Network Flow Data Structures II PS7 released  
9 Network Flow Mathematics Network Flow PS8 released Contest 3
10 Mathematics Exam Revision Mathematics    

Assessment

Item Topics Due Weight
Problem Sets All topics Weeks 3-10+ 40%
Problem Diary All topics Weeks 3-10+ 8%
Contest 1 Getting Started Week 1 6%
Contest 2 Paradigms, Data Structures I, Dynamic Programming Week 5 6%
Contest 3 Graphs, Shortest Paths, Data Structures II, Network Flow Week 9 6%
Final Exam All topics TBC 34%

2 bonus marks will be provided for participation in the South Pacific ICPC Preliminary Contest on 3rd September 2023. You can sign up here. These bonus marks can alternatively be earned by volunteering to help run the Preliminary Contest or Regional Finals (31st September and 1st October 2023). Volunteers’ duties include setting up, marking attendance and distributing balloons. Please email me if you are interested in volunteering.

Problem Sets

A problem set will be released on vjudge at the start of each lecture topic (counting the first three lectures as one topic). Students are recommended to complete the problems within about two weeks of the release date, but all problem sets will remain open until the end of the exam period.

Each of the 8 sets will be worth 5% of the overall course mark, for a total of 40%. Marks will be awarded non-linearly:

Problems solved Course mark
0/5 0%
1/5 2%
2/5 3%
3/5 3.75%
4/5 4.5%
5/5 5%

Some problem sets will have 6 problems.

  • If you solve all 6 problems, the 6th will be counted towards your lowest other problem set instead.
  • For example 6 5 5 3 4 5 4 5 will be treated as 5 5 5 4 4 5 4 5, with the ‘bonus’ problem solved in PS1 counting as a fourth solve in PS4.

Solutions must be implemented in C/C++.

Problem Diary

For each problem set, you must also produce a diary entry to

  • explain the process by which you arrived at your solutions (not the solutions themselves),
  • reflect on any challenges encountered and how you overcame them, and
  • discuss any collaboration that you participated in with other students.

You are not required to write detailed descriptions or proofs for your algorithms as in COMP3121/3821/9101/9801.

You must make some remarks on every problem (even if only to say that you don’t know how to do the question at all). You are encouraged to include any progress made on problems which you did not solve.

Each diary entry should be a PDF of no more than three pages, excluding code snippets. A document much shorter than this limit may often be sufficient!

Each of the 8 diary entries will be worth 1% of the overall course mark, for a total of 8%. Any attempt demonstrating a genuine effort to meet the specification listed in this section will receive the mark.

  • You will be assessed for each diary entry by showing it to an instructor during lab time.
    • There is no deadline for any particular diary entry.
    • If your diary entry is not satisfactory, you can re-attempt it without penalty as many times as necessary (within reason).
  • At the end of exam period, there will be an opportunity to submit any diary entries which are still outstanding.
    • There will be no mechanism for resubmission here, but we anticipate that the requirements will be very clear by this point.
    • Please do not leave too many diary entries this late, so as not to overload our staff with marking.

Late Submissions

There are no deadlines and no late penalties for the problem sets or problem diaries. However, you should not continue to work on a problem set many weeks after it was released at the expense of more recent topics. If you encounter some interruption to your studies (such as medical or personal issues, or in some cases other major deadlines) I would generally prefer to exempt you from a problem set so that you can stay up to date with the material being covered in lectures and tute/labs. Your mark would then be estimated as the minimum of your other problem sets. Please email me (and cc your tut/lab instructors) if you are concerned about falling behind.

Contests

A long contest (5 problems, 48 hours) will be held in week 1. This contest does not test any new material, and is intended to test whether your programming fundamentals are sufficient to proceed to the later stages of the course.

Two short contests (3 problems, 3 hours) will be held in weeks 5 and 9 (TBC). Each problem will be worth 100 points with a 50 point subtask.

Each contest will be worth 6% of the overall course mark, for a total of 18%. In contests 2 and 3, marks will be awarded non-linearly:

Score Course mark
0 1%
50 2.5%
100 3.5%
150 4.5%
200 5%
250 5.5%
300 6%

Final Exam

The final exam will be a long contest (approx 8 problems, 5 hours). Each problem will be worth 100 points, and most or all problems will have one or more subtasks of various point values.

The final exam will be held in person at CSE labs. If you are unable to attend in person, please contact me by email in advance so that we can arrange an alternative for you.

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.

Marks will be scaled up. As a guide:

Mark Minimum score
50% 100-150
65% 200-250
75% 300-350
85% 400-500

The exact cutoffs will be decided after the exam is completed, taking into account the difficulty of the exam problems.

Academic Honesty and Plagiarism

  • Students are encouraged to discuss the problems in the weekly problem sets with each other, but any code must be derived and written separately, and any collaboration must be acknowledged in a header comment.
  • Students are also encouraged to share test cases for the problem sets, with acknowledgement as above.
  • 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. This can however be a place to discuss any collaboration that you participated in.
  • The contests and final exam must be completed individually, without any collaboration with other students or third parties.
  • It is unacceptable to present others’ work as your own. This includes (but is not limited to) copying or purchasing solutions to the assessment problems and copying code from external sources without attribution.
  • You are not permitted to submit code or writing generated by generative tools such as Github Copilot or ChatGPT in COMP4128.
  • There are serious consequences for plagiarism. The university’s policy can be found here. The pages below describe the policies and procedures in more detail:

Student Equity and Accessibility

Equitable Learning Services is a free and confidential service that provides practical support to ensure that your health condition doesn’t adversely affect your studies.

If you have an Equitable Learning Plan, please provide it to me by email within the first two weeks of the term.

In addition, if you encounter any challenges or hardships during the term, please email me and we will do our best to accommodate your needs.

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 4 (Halim). A free copy of Competitive Programming 1 can be found at CPBook
  • Students may find the following online resources helpful:
  • Further practice problems can be found in many places, such as:
  • Students are encouraged to ask course staff 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 lecture code could be better explained and easier to use, and that some of the problems were dated or unintuitive.

Based on their comments, we will polish some lecture code and add more explanatory comments, and continue to curate the problem sets.

Acknowledgements

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, and to Jaehyun Park for advice on the problem sets.