1 of 10

Introduction

Competitive Programming II (Spring 2020)

​

Ninghui Li (Purdue University)

2 of 10

Why Taking CP Courses

  1. Become a better programmer / problem solver.
    1. Lots of practice of applying data structures and algorithmic ideas.
    2. Working on interesting and carefully selected problems, many have been extensively tested.
    3. Read others’ code, solution ideas. Many problems have many submissions and discussions on line.
  2. Help prepare for job interviews.
  3. Prepare to compete in ICPC (The International Collegiate Programming Contest).
  4. Have fun.

3 of 10

Course Pages

Schedule and links to slides available through

https://www.cs.purdue.edu/homes/ninghui/courses/390_Spring20/

Problem sets on

https://purdue.kattis.com/courses/CS390-CP2/Spring2020

​

4 of 10

Course Structure

Three Units, each has three lecture weeks and one contest week

  • Each lecture week has a problem set of 4 problems on purdue.kattis.com
  • The contest week has a contest on HackerRank

Grading Policy

  • Each lecture week has a maximum of 9 pts. For a total of 9*9=81 pts.
    • 2pts for solving each problem, and 1 pt for attendance
    • No signup sheet for Jan 16. Everyone gets 1pt attendance.
  • Contest 1 and 2 each has 3 problems and a maximum of 15 pts.
    • 5 pts for each problem. 3 pts if solved outside classroom contest.
  • Final Contest has 4 problems and a maximum of 20 pts.
    • 5 pts for each problem. 3 pts if solved outside classroom contest.

5 of 10

Grading Policy for CP2

  • Maximum number of pts: 81+50 = 131
  • Scale: 100 or higher = A+ 80 or higher = A 74 or higher A- 68 or higher B+ 60 or higher = B 54 or higher B- 48 or higher C+ 40 or higher = C

6 of 10

Problem Sets

  • Problem Sets will be on purdue.kattis.com
  • Our competitions will be on hackerrank.com.
  • Ask for help on the course piazza page.
    • This is the primary channel of communication.
    • Mark your post as private if posting code segments with TAs.
  • For competition, cheating is defined as obtaining help from any other person, posting problems anywhere, or sharing solutions in any way. Code may be checked for similarities.

7 of 10

Sources of Problems Used in the Course

LeetCode

  • Some problems have solution explanation.
  • The discuss page for each problem has many solutions posted by users.
  • The page for each of your submission contains figures showing time and space distribution, clicking shows sample solutions. (Can check what do the fastest solutions do.)

Kattis

  • Most problems used in this course taken from the Methods to Solve webpage, which is associated with the Competitive Programming book.
  • That page has a one-line hint for the problems. First try solving it without hints.

8 of 10

Sources of Problems Used in the Course

​

USACO

  • Three levels (Bronze, Silver, Gold) before the 2015-2016 season
  • Four levels (Bronze, Silver, Gold, Platinum) since December 2015
  • This course mostly use the old Bronze or Silver (new mostly Silver) problems.
  • After creating an account (anyone can do this) and logging in, one can submit solutions (except for the 2011-2012 season)
  • The contest page includes test data and solution
  • If one fails a test case, one can download and examine the data.
  • One can read solution discussion and code.

9 of 10

CPU Club

  • The competitive programming club is for anyone who is interested in competitive programming
  • The primary focus of CPU Club this Fall is to participate in ICPC.
  • It is more accelerated and will focus on working in a team to solve programming problems in the ICPC format.

10 of 10

The Big-O Notation

  • We consider the running time (or space consumption) of a piece of code (or an algorithm) as a function of its input size, typically denoted by N.
  • The exact number would depends on the units one is using, and factors such as computer speed, compilers, …
  • To abstract away from that, we use O(f(N)), which f(N) is a function of N.
  • Typical complexity include O(N), O(N^2), O(N logN), O(N^2 logN), O(2^N), O(N!), etc.
  • Time complexity O(N) means that for whatever units of measuring time, and run-time environment, there exists a constant C such that the running time in input of size N is no more than C*N.