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.

Workshops 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 skilful 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
Consultation 1–10 Tue 14:00 - 15:00 K17 (CSE) 202
Lecture 1–10 Tue 16:00 - 18:00 K15 (Old Main) 150
Consultation 1–10 Fri 13:00 - 14:00 K17 (CSE) 202
Lecture 1–10 Fri 14:00 - 16:00 F10 (Griffith) M10

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.

Workshops and Labs

You can find the full timetable here.

Course Learning Outcomes

  1. Apply the C++ programming language to solve programming problems
  2. Adapt templated data structures and algorithms to meet the requirements of complex problems
  3. Design and implement algorithmic solutions to complex problems, particularly under short time constraints
  4. Apply algorithm design principles to evaluate programs in terms of correctness and running time

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 and recordings.
  • Weekly problem sets are hosted on vjudge. Make an vjudge account using your zID as the username but not your zPass as the password, and join our group.
  • Information on the platform for the midterm contests and the final exam will be released soon.
  • Join the Discourse forum here, using UNSW Single Sign-On.

Course Schedule

Week Tuesday Lecture Friday Lecture Workshop Problem Set Contest
1 Intro Getting Started Getting Started PS1 released Contest 1
2 Paradigms Data Structures Paradigms PS2 released  
3 Data Structures Data Structures Data Structures PS3 released  
4 Dynamic Programming Dynamic Programming Dynamic Programming PS4 released  
5 Graphs Graphs Graphs PS5 released  
6 TBA TBA No class   Contest 2 (TBC)
7 Shortest Paths Shortest Paths Shortest Paths PS6 released  
8 Flow Networks Flow Networks Flow Networks PS7 released  
9 Mathematics Mathematics Mathematics PS8 released Contest 3 (TBC)
10 Computational Geometry Computational Geometry Computational Geometry PS9 released  

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, Dynamic Programming Week 6 6%
Contest 3 Graphs, Shortest Paths, Network Flow Week 9 6%
Final Exam All topics TBC 34%

1 bonus marks will be provided for participation in any of the last four South Pacific Algorithmic Rounds (5th July, 30th July, 6th August, 9th August). This bonus mark can only be earned once.

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, and with two sets for data structures). 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 nine sets will be worth 5% of the overall course mark, and the lowest disregarded, for a total of 40%. Marks will be awarded non-linearly:

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

Thus students can score up to 42/40 in the problem sets.

Solutions must be implemented in C/C++.

Problem Diary

For each problem set, you must also produce diary entries 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.

Diary entries will be submitted on Formatif. You must make some remarks on every problem up to your target grade (even if only to not your first thoughts upon reading the problem). You are encouraged to include any progress made on problems which you did not solve. Any attempt demonstrating a genuine effort to meet the specification listed in this section will be considered satisfactory. If a diary entry is not satisfactory, you can re-attempt it without penalty as many times as necessary (within reason).

Each problem’s diary entry should be a PDF of less than one page, excluding code snippets. A document much shorter than this limit may often be sufficient!

Students are encouraged to make notes during the problem solving process and submit their diary entries contemporaneously with the problem sets. All diary entries must be submitted before the end of the exam period, and we ask that students do not leave too many diary entries this late, so as not to overload our staff with marking.

By the end of the exam period, you must submit a Learning Summary Report. This together with the diary entries will collectively be worth 8% of the total course mark, marked according to a rubric.

Please find below exemplar diary entries for the following problems (that are no longer used in Problem Set 1), graciously contributed by some former students:

Late Submissions

There are no deadlines and no late penalties for the problem sets or problem diaries. However, trying to get through a large portion of the work at the end of term will invite stress and inhibit your ability to engage in classes. If you fall behind, we are happy to discuss a catch-up plan with you, which will usually entail prioritising the easiest problems of each set in the short term. Please email me (and cc your 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 6 and 9. 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 contest 1, marks will be awarded as follows:

Score Course mark
Non-attempt 0%
0 1%
100 2%
200 3%
300 4%
400 5%
500 6%

In contests 2 and 3, marks will be awarded non-linearly as follows:

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

Students who earn zero points in a contest must retain records to verify that a serious attempt was made.

Final Exam

The final exam will be a long contest (approx 7 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, you must apply for a supplementary exam through the usual Special Consideration process.

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.
    • The only exception is that in problem sets, you may use dcc-help and dcc-sidekick to understand and fix compilation errors, with acknowledgement in the header comment and diary entry.
  • 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 more supplemental resources could be helpful, and the work was concentrated towards the end of term.

Based on their comments, we will suggest additional practice problems and set up forum threads for students and tutors to do the same, and we will add a second problem set for the Data Structures (early in the term) but drop each student’s lowest problem set score.

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.