Jingbo Shang

Jingbo Shang

Assistant Professor

2020-Winter-CSE191-Introduction to Competitive Algorithmic Programming

Undergraduate Seminar, CSE, UCSD, 2020

Class Time: Mondays 11AM to 12PM. Room: CSE 2154. Piazza: piazza.com/ucsd/winter2020/cse191cap

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

Lecture Schedule

(tentative)

DateTopic & SlidesHomeworkPractice ContestAdditional Notes
01/06IntroductionProblem Set #0 Solutions STL Notes
01/13Ad Hoc, Simulation & SearchProblem Set #1  
01/20No Class (MLK Day)   
01/27Dynamic Programming (Simple)Problem Set #2  
02/03Basic Graph AlgorithmsProblem Set #3  
02/10Computational GeometryProblem Set #4  
02/17No Class (Presidents’ Day) NAC this week! 
02/24Dynamic Programming (Intermediate)Problem Set #5  
03/02Combinatorics and AlgebraProblem Set #6  
03/09Network FlowProblem Set #7  

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 8 problem sets, with the possibility of substituting up to 2 problem sets with practice contests — you have to solve at least one problem in these “substituting” practice contests.

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 Winter Quarter. That is, 11:59PM March 21, 2020. 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 Mar 2, 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

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.