Jingbo Shang

Jingbo Shang

Associate Professor

2021-Spring-CSE191-Introduction to Programming Contests

Undergraduate Seminar, CSE, UCSD, 2021

Class Time: Mondays 11AM to 12PM. Room: https://ucsd.zoom.us/j/92762034655. Piazza: https://piazza.com/class/kmmhpnflaoj6oh.

Online Lecturing

Due to the COVID-19, this course will be delivered over Zoom: https://ucsd.zoom.us/j/92762034655

Overview

This course introduces the algorithms and concepts necessary to compete effectively in the ACM International Collegiate Programming Contest (ICPC) and similar contests. It is highly recommended for students intending to compete in the ICPC Southern California (SoCal) Regional contest. The course requires weekly completion of short problem sets. Topics covered include standard library classes and data structures useful for programming contest problems, basic complexity analysis, dynamic programming, graph algorithms, number theory, combinatorics, computational geometry, combinatorial games, and competitive programming contest strategy.

Prerequisites

CSE 30, must have programming competency in C++, Java, or Python. (CSE 100 highly recommended)

Most importantly, eagerness to learn and practice

Office Hour

Lecture Schedule

Recording Note: Please download the recording video for the full length. Dropbox website will only show you the first one hour.

DateTopic & SlidesHomeworkAdditional Notes
03/29IntroductionProblem Set #0Solutions STL Notes
04/05Ad Hoc, Simulation & SearchProblem Set #1 
04/12Dynamic Programming (Simple)Problem Set #2 
04/19Basic Graph AlgorithmsProblem Set #3 
04/26Computational GeometryProblem Set #4 
05/03Dynamic Programming (Intermediate)Problem Set #5 
05/10Combinatorics and AlgebraProblem Set #6 
05/17Network FlowProblem Set #7 
05/24Segment TreeProblem Set #8 
05/31No Class (Memorial Day)  

Homework and Grading Policy

You are required to solve the problem on the online judge site and provide the instructor with your online judge usernames for validation of your submission. Please fill in this Google Form before you work on homework. Don’t worry if you filled wrong information. Just fill another one. Only the last one counts.

This course provides a pass/fail grade. Passing the course requires completion of at least 6 of the 9 problem sets.

Completion of a problem set requires obtaining a total score of at least 4 points for the problem set. You can calculate your score on a problem set by summing the point value next to each problem you have solved. You may not use points from one problem set to fulfill the score requirements for another. Problem sets must be completed by 11:59 PM on the last date of Spring Quarter. That is, 11:59PM Jun 11, 2021. No extensions will be given for any reason.

We encourage you to solve as many problems from each problem set as you have time to solve, even if you have completed the minimum requirements. The more practice you get in, the better your skills will become and the better you will perform during tryouts and official competitions.

Starting from Jun 4, we will calculate your grades by a web scraper and will send emails to notify you about your status at a weekly basis.

Problem Set #0: Introduction

Problem Set #1: Ad Hoc, Simulation & Search

Problem Set #2: Dynamic Programming (Simple)

Problem Set #3: Basic Graph Algorithms

MST

Shortest Path

TopoSort

Problem Set #4: Computational Geometry

Problem Set #5: Dynamic Programming (Intermediate)

Problem Set #6: Combinatorics and Algebra

Problem Set #7: Network Flow

Problem Set #8: Segment Tree

Resources

Here are the Online Judges that we may use for assignments:

Some Tutorials or Books:

Communication

We will be using a Piazza page for problem set announcements, practice contest announcements, and all course discussions. Please ask all general course questions and questions about the problem sets in the course Piazza page. Chances are, if you have the question, so does someone else. Asking in the Piazza page also allows other students to answer your question more quickly if the instructors are busy.

Please use @ucsd.edu e-mail addresses for all other course communication.

Collaboration

Discussing problems with friends is highly encouraged. In fact, we intend for you to work with small groups of other students during the regular ICPC-Club practice sessions to solve the problems from the problem sets. Remember, the ACM-ICPC is a team competition. However, you should code your own solution entirely by yourself. You will only be hurting yourself by copying someone else’s (potentially buggy) code.

Please do not post any code or solutions to problems to the Piazza page. Discussion of the problems is encouraged, but outright spoiling is frowned upon and can result in censorship from the Piazza page.

When you get stuck…

It is more than common to spend many hours solving a single problem. This is particularly true of the harder problems in each problem set. If, however, you have spent over a day seriously working on a problem and have not made any progress, follow these steps:

  • First, reread the problem statement. Did you miss something important? Are you sure you have understood what the problem is asking for? Double-check your understanding on the sample input and output.
  • Carefully go through the lecture slides. Think about which of the algorithms or techniques should be applied to the problem. For additional explanation of the algorithms, refer to Steven Halim’s Competitive Programming book.
  • Check Piazza. It is likely that someone else has asked a question about the problem already.
  • Attend the weekly ICPC-Club meeting and try to work out the problem with other students at the meeting. If necessary, ask one of the course assistants at the meeting.
  • If none of the previous steps have worked, post your question to Piazza without giving away any obvious solutions.