Jingbo Shang

Jingbo Shang

Assistant Professor

2022-Spring-CSE109-Introduction to Programming Contests

Undergraduate Seminar, CSE, UCSD, 2022

Class Time: Mondays 12PM to 12:50PM. Room: WLH 2204. Piazza: piazza.com/ucsd/spring2022/cse109.

Additonal Course Policy for COVID-19

While the university does not close, we are still in a pandemic. Here are some additional policies specifically designed to better protect our students in this course from COVID-19 risks.

  • First-week lectures online. We will deliver the first-week lectures online, as the students on the super-long waitlist may want to attend the first lecture too and we will likely flood the physical classroom.
  • Attendance is optional. Podcast is enabled. You can also check out my previous offering, which has Zoom videos.

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

UCSD ICPC Club

UCSD ICPC Club is a student-org organized to help students learn techniques for solving problems with computer algorithms and to compete in algorithmic programming competitions. - Jingbo Shang is the faculty advisor and coach - Zihan Wang is the president and student co-coach.

Guest Lecturer

  • Zihan Wang
    • Zihan is our co-coach at UCSD-ICPC Club.
    • Zihan will contribute some guest lectures to the seminar.

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/28IntroductionProblem Set #0Solutions STL Notes
04/04Ad Hoc, Simulation & SearchProblem Set #1 
04/11Dynamic Programming (Simple)Problem Set #2 
04/18Basic Graph AlgorithmsProblem Set #3 
04/25Computational GeometryProblem Set #4 
05/02Dynamic Programming (Intermediate)Problem Set #5 
05/09Combinatorics and AlgebraProblem Set #6 
05/16Network FlowProblem Set #7 
05/23Segment TreeProblem Set #8 
05/30No 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 ONLY. Passing the course requires completion of at least 6 of the 9 problem sets. [Warning] If you select this course for grade, you will only receive a B for Pass.

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 10, 2022. 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 3, 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.