Simon Fraser University
Engaging the World

Course Outlines

Spring 2018 - CMPT 409 D100

Special Topics in Theoretical Computing Science (3)

Competitive Programming

Class Number: 10812

Delivery Method: In Person

Overview

  • Course Times + Location:

    Jan 3 – Apr 10, 2018: Mon, 1:30–2:20 p.m.
    Burnaby

    Jan 3 – Apr 10, 2018: Wed, 1:30–2:20 p.m.
    Burnaby

    Jan 3 – Apr 10, 2018: Fri, 1:30–2:20 p.m.
    Burnaby

  • Exam Times + Location:

    Apr 21, 2018
    Sat, 12:00–3:00 p.m.
    Burnaby

  • Instructor:

    Binay Bhattacharya
    binay@sfu.ca
    1 778 782-3133

  • Prerequisites:

    CMPT 307.

Description

CALENDAR DESCRIPTION:

Current topics in theoretical computing science depending on faculty and student interest.

COURSE DETAILS:

This course deals with the developments of techniques and skills needed to solve contest problems such as those appear on the ACM ICPC, Codeforces and Topcoder. These skills are valuable to prepare you for other courses, contests, job interviews etc. This course will discuss how to think about algorithms in a critical way. Many of the problems in a contest require you to design a new algorithm, not just apply a classic one. The weekly class schedule involves lectures in the classrooms and CSIL labs. Details will be discussed in the class. This course can be concurrently taken with CMPT307 by students with good academic standing. In this case, a waiver from the instructor is required.

Topics

  • Elementary data structures, string manipulations, sorting and searching,
  • Enhancing your theoretical background: arithmetic, number theory, combinatorics
  • Algorithm design techniques: Brute force, dynamic programming, data structures
  • Graph theory: Classical graph theory problems, A* search, stable marriage problem, eulerian circuits
  • Geometry: Convex hulls, plane sweep, Voronoi diagram
  • Improving your coding ability: Language considerations, testing and debugging, know your defects

Grading

NOTES:

Most of the course works involve writing programs to solve interesting contest problems and getting them evaluated using the online judges.
The details will be discussed in the class.

Materials

REQUIRED READING:

Programming Challenges The Programming Contest Training Manual,
Steven S. Skiena, Miguel Revilla,
Springer, 2003,
Edition 1
ISBN: 9780387001630

Registrar Notes:

SFU’s Academic Integrity web site http://students.sfu.ca/academicintegrity.html is filled with information on what is meant by academic dishonesty, where you can find resources to help with your studies and the consequences of cheating.  Check out the site for more information and videos that help explain the issues in plain English.

Each student is responsible for his or her conduct as it affects the University community.  Academic dishonesty, in whatever form, is ultimately destructive of the values of the University. Furthermore, it is unfair and discouraging to the majority of students who pursue their studies honestly. Scholarly integrity is required of all members of the University. http://www.sfu.ca/policies/gazette/student/s10-01.html

ACADEMIC INTEGRITY: YOUR WORK, YOUR SUCCESS