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 Code	COMP4128
Course Title	Programming Challenges
Convenor	Raveen de Silva (r.desilva@unsw.edu.au)
Admin	Raveen de Silva (r.desilva@unsw.edu.au)
Classes	Lectures : Tuesday 4-6pm, Friday 2-4pm Timetable for all classes
Consultations	Friday 4-5pm
Units of Credit	6
Course Website	http://cse.unsw.edu.au/~cs4128/
Handbook Entry	http://www.handbook.unsw.edu.au/undergraduate/courses/current/COMP4128.html

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

Week	Tue Lecture	Tut/Lab	Fri Lecture	Problem Set	Contest	Notes
1	Introduction	Getting Started	Getting Started	Set 1 released	Contest 1	-
2	Paradigms	Paradigms	Data Structures I	Set 2 released	-	-
3	Data Structures I	Data Structures I	Dynamic Programming	Set 3 released	-	-
4	Dynamic Programming	Dynamic Programming	Graphs	Set 4 released	Contest 2	-
5	Graphs	Graphs	Shortest Paths	Set 5 released	-	-
6	TBA	-	TBA	-	-	Flexibility Week
7	TBA	Shortest Paths	Data Structures II	Set 6 released	-	-
8	Data Structures II	Data Structures II	Network Flow	Set 7 released	-	-
9	Network Flow	Network Flow	Mathematics	Set 8 released	Contest 3	-
10	Mathematics	Mathematics	Exam Revision	-	-	-

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

Assessment

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

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