CS 5890 Rapid Problem Solving, Spring 2018

  • Time and Place: Tue Thu 10:30 - 11:45am, Family Life 307
  • Course Website: https://sites.google.com/site/drminghuijiang/cs5890
  • Professor: Dr. Minghui Jiang
    • Contact: mjiang at cc.usu.edu, 435-797-0347
    • Office hours: Tue Thu 11:45 - 1:15pm, Main 402G (email before 9am or approach professor in class for appointment)
  • Textbook: None required.
  • Course Objectives:
    • [IDEA Objective 4 - Essential] Developing specific skills, competencies, and points of view needed by professionals in the field most closely related to this course.
      • Be able to rapidly understand the specification and requirement of a problem.
      • Be able to rapidly recognize the essential mathematical structure of a problem.
      • Be able to rapidly identify the most natural and efficient solution for a problem.
      • Be able to rapidly estimate the required effort of a potential solution to a problem and devise a systematic plan to solve as many problems as possible within time constraint.
      • Improve programming skills and become familiar with the application programming interfaces of mainstream programming languages for fundamental algorithms and data structures.
    • [IDEA Objective 3 - Important]: Learning to apply course material (to improve thinking, problem solving, and decisions).
      • Be able to apply competitive programming techniques in software projects and coding interviews.
  • Prerequisite: CS2420 or consent of instructor.
  • Grading:
    • Grade of each student is determined by the ratio, of the sum of his/her best three scores for any rated contests on CodeForces, over the class average of such sums. The professor will determine the exact dividing lines between consecutive grades at his discretion, near the end of the semester, but roughly, A 1.5 A- 1.3 B+ 1.1 B 0.9 B- 0.8 C+ 0.7 C 0.6 C- 0.5 D+ 0.45 D 0.4 D- 0.35 F. In particular, if your sum of best three scores is at least 1.5 times the class average, then you are guaranteed to receive an A grade; if your sum of best three scores is at least 0.5 times the class average, then you are guaranteed to receive no worse than a C- grade. In addition, if you solve at least one problem completely (that is, your solution passes all testcases of that problem) in at least 8 rated contests, then you are also guaranteed to receive no worse than a C- grade.
    • Read the contest rules carefully, and check for upcoming contests. There is usually at least one contest each week. The duration of each contest is typically 2 to 3 hours. Although some contests start at rather odd times in our time zone, the majority of them are in our mornings, in both weekdays and weekends. The professor is fully aware that your class schedule may conflict with some of these contests. Thus he uses only the best three scores of each student to calculate grades. Compete in as many rated contests as you can or as you wish. If after browsing through the history of past contests, you feel that you would have difficulty finding time to compete in a sufficient number of rated contests to reach your desired grade, then you should quit the class immediately. Also keep in mind that the rated contests on CodeForces tend to have very thorough system tests. Your program will very likely receive zero point if it is not perfectly correct or if its running time is too high. If you are not comfortable with this all-or-nothing contest format, then you should quit the class immediately.
    • To check your scores for rated contests, first go to your profile page, then click on the contests tab to see your contest history (you need to replace "Dukkha" by your own handle in the example urls). Follow the links in the "Rank" column to the standings page of each contest: your points for that contest is listed in the "=" column.
    • Every new contestant on CodeForces has an initial rating of 1500. After every rated contest, your rating is adjusted according to your performance relative to the other contestants. The professor will award you an instant A grade as soon as your CodeForces rating reaches 1600+ (Expert, blue).
    • The professor will list all rated contests here, in case you are not sure whether a contest is rated or not:
      • ???
      In general, educational rounds are never rated, and regular CodeForces rounds with numbers are always rated. Sometimes a contest was advertised as rated but due to some technical issues becomes unrated after the event; in such rare cases the professor may still take into account of your participation if he feels that it is reasonable to do so.
    • Besides some lectures in the traditional format, a practice contest is scheduled during the time of each lecture, consisting of a problem solving session in which each student programs on his/her own laptop computer (60-70 minutes), and then a review of solutions by the professor (5-15 minutes). The problems in these practice contests are automatically assigned as homework, and upsolving them is highly encouraged. The professor may, at his discretion, give a student a grade that is one step higher than the initial grade determined by performance in rated contests, if he observes that the student regularly attends in-class practice contests, and diligently upsolve past contest problems. On the other hand, whenever the professor reasonably suspects that a student has committed an academic integrity violation, he may report the incident, and then give the student a grade lower than the one determined by performance in rated contests.
    • Within the first week of the semester, please email the professor your handle on CodeForces, and make sure that it is included in the class list so that the professor and all students can monitor the performance of everyone in the class. Note that your profile on CodeForces is public, and all your coding activities on CodeForces have permanent records that are viewable by everyone. If you are uncomfortable with this lack of privacy, then you should quit the class immediately. Your enrollment in the class beyond the first week implies your enthusiastic consent to the grading policy described here.
  • Programming References: libc stl cppreference java python. Any programming language acceptable by CodeForces is allowed. The professor uses Java and C.
  • Schedule (subject to change, occasionally a class may be canceled if it overlaps with a rated contest):
    • Jan 9 11:
      • Lecture, Tue Jan 9.
      • Contest 0 (pair), Thu Jan 11.
    • Jan 16 18:
      • Contest 1 (solo), Tue Jan 16.
      • Contest 2 (pair), Thu Jan 18.
    • Jan 23 25:
      • Contest 3 (solo), Tue Jan 23.
      • Contest 4 (pair), Thu Jan 25.
    • Jan 30 Feb 1:
      • Lecture, Tue Jan 30.
      • Lecture, Thu Feb 1.
    • Feb 6 8:
      • Contest 5 (solo), Tue Feb 6.
      • Contest 6 (pair), Thu Feb 8.
    • Feb 13 15:
      • Contest 7 (solo), Tue Feb 13.
      • Contest 8 (pair), Thu Feb 15.
    • Feb [20] 22:
      • No class on Tue Feb 20 (Monday schedule).
      • Lecture, Thu Feb 22.
    • Feb 27 Mar 1:
      • Contest 9 (solo), Tue Feb 27.
      • Contest 10 (pair), Thu Mar 1.
    • Mar [6 8]:
      • No classes (Spring break).
    • Mar 13 15:
      • Contest 11 (solo), Tue Mar 13.
      • Contest 12 (pair), Thu Mar 15.
    • Mar 20 22:
      • Contest 13 (solo), Tue Mar 20.
      • Contest 14 (pair), Thu Mar 22.
    • Mar 27 29:
      • Lecture, Tue Mar 27.
      • Lecture, Thu Mar 29.
    • Apr 3 5:
      • Contest 15 (solo), Tue Apr 3.
      • Contest 16 (pair), Thu Apr 5.
    • Apr 10 12:
      • Contest 17 (solo), Tue Apr 10.
      • Contest 18 (pair), Thu Apr 12.
    • Apr 17 19:
      • Contest 19 (solo), Tue Apr 17.
      • Contest 20 (pair), Thu Apr 19.
    • Apr 24 26:
      • Lecture, Tue Apr 24.
      • Lecture, Thu Apr 26.