Jingbo Shang

Jingbo Shang

Associate Professor

2024-Fall-CSE109-Introduction to Programming Contests

Undergraduate Seminar, CSE, UCSD, 2024

Class Time: Thursdays 11AM to 11:50AM. Room: EBU3B (CSE) 2154. Piazza: piazza.com/ucsd/fall2024/cse109.

Online Lecturing for First Week

To offer waitlist students opportunities to learn more about this course, in the first week, we deliver the lecture over Zoom: https://ucsd.zoom.us/j/92762034655. The lecture will be recorded.

Overview

This seminar 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.

  • Shang Zhou and Huize Mao are the co-presidents
  • Jingbo Shang is the faculty advisor and co-coach with Qihao Ye and Shang Zhou

Office Hour

Lecture Schedule

DateTopic & SlidesHomeworkAdditional Notes
09/26IntroductionProblem Set #0Solutions STL Notes
10/08Ad Hoc, Simulation & SearchProblem Set #1 
10/15Dynamic Programming (Simple)Problem Set #2 
10/22Basic Graph AlgorithmsProblem Set #3 
10/29Computational GeometryProblem Set #4 
11/05Dynamic Programming (Intermediate)Problem Set #5 
11/12Combinatorics and AlgebraProblem Set #6 
11/19Network FlowProblem Set #7 
11/26Segment TreeProblem Set #8 
12/03String Hash  

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 Dec 14, 2024. 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 Dec 6, 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.