Course Outline

Contents

• Course Details
• Course Summary
• Assumed Knowledge
• Student Learning Outcomes
• Teaching Strategies
• Teaching Rationale
• Student Conduct
• Assessment
• Course Schedule
• Resources for Students
• Course Evaluation and Development

Course Details

Course Summary

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.

Assumed Knowledge

The pre-requisite for this course is COMP3821/9801 (or COMP3121/9101 and 75 WAM). Familiarity with the algorithms and data structures presented in either Algorithms course will aid students in this course, although much of the material is reintroduced.

All code in COMP4128 is in C++. Expert knowledge of C++ 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.

Course Learning Outcomes

Upon completing this course, students will be able to:

• design and implement solutions to unfamiliar problems,
• demonstrate an understanding of the practical aspects of the material covered in the course, and
• work on all phases of solving a problem (identifying, combining and implementing approaches) under tight time constraints.

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, including implementation in C++.
• 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/9101/9801 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.

Course Schedule

Of the three TBA lectures, at least one will be a revision lecture.

Assessment

2 bonus marks will be provided for participation in the South Pacific Divisional contest on October 15th. You can sign up here .

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)
• 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:
  • Range Trees
  • Dynamic Programming on Trees
  • Geometry
  • Dynamic Programming Optimizations

Further practice problems can be found in many places, e.g:

• Codeforces
• AtCoder
• Topcoder
• CodeChef
• USACO

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 three-hour lectures were too long and made it difficult to focus.

Based on their comments, we will run two two-hour lectures each week instead