CS 5890 Rapid Problem Solving, Spring 2018

  • Time and Place: Tue Thu 10:30 - 11:45am, Fine Arts-Visual 262
  • Course Website: https://sites.google.com/site/drminghuijiang/cs5890
  • Professor: Dr. Minghui Jiang
    • Contact: minghui.jiang at usu.edu, 435-797-0347
    • Office hours: Tue Thu 12:00 - 1:30pm, Main 402G
  • Textbook: None required.
  • Recommended Reading: pllk's Competitive Programmer's Handbook; Peak and deliberate practice; dreamoon's advices; ACRush's advices.
  • 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.
  • Course Structure and Grading Policy: Karuna
    • 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 dividing lines between consecutive grades are
      A 32 A- 43 B+ 54 B 11 B- 45 C+ 34 C 23 F.
      In particular, if your sum of best three scores is at least 3/2 times the class average, then you are guaranteed to receive an A grade; if your sum of best three scores is at least 2/3 times the class average, then you are guaranteed to receive no worse than a C grade. Moreover, if you have nonzero scores for at least three rated contests, then you are also guaranteed to receive no worse than a C grade.
    • Your score S for a rated contest depends on three numbers: your rank R, the number K of problems your solved, and the number N of registered participants:
      • To check your rank R and the number K of problems you solved in a rated contest, go to your profile page, and click on the contests tab (you need to replace the professor's handle "Dukkha" by your own handle in these example urls). They are in the "Rank" and "Solved" columns of the table. For example, the professor has rank 131 and solved 5 problems in Hello 2018.
      • The number of registered participants of a rated contest is the number shown in the rightmost column in the "Past contests" table on the contests page. For example, there are 9432 registered participants in Hello 2018.
      If K = 0, then S = 0. Otherwise, S = (1 - R / N) * 100, which yields a number between 0 and 100. For example, (1 - 131 / 9432) * 100 = 98.61 is the professor's score for Hello 2018.
    • Every new contestant on CodeForces has an initial rating of 1500. After every rated contest, your rating will be adjusted according to your performance relative to the other contestants. The professor will award you an instant A grade as soon as your rating reaches 1600+ (Expert, blue).
    • Only rated contests from Jan 8 to Apr 27, 2018 are considered for grade. You can check all upcoming contests here. The professor will keep a list of rated contests updated in the following: Sometimes a contest might be advertised as rated but due to some technical issues become unrated after the event; in such rare cases the professor may still consider your score for grade if he deems it reasonable to do so.
    • There is usually at least one rated 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 CodeForces contests tend to have very thorough system tests: your submission will receive zero point unless it passes all tests within the time limit. If you are not comfortable with this all-or-nothing contest format, then you should quit the class immediately.
    • All students are expected to follow CodeForces contest rules and work independently in all rated contests. Once the professor has determined that an academic violation has occurred and that a sanction (such as a grade lower than the one determined by performance in rated contests) is appropriate, he will report the violation by submitting an academic integrity violation form. Refer to USU Student Code Article 6 for more details on university regulations regarding academic integrity:
      • Academic Integrity - "The Honor System": Each student has the right and duty to pursue his or her academic experience free of dishonesty. The Honor System is designed to establish the honest conduct expected and required of all Utah State University students. To enhance the learning environment at Utah State University and develop student academic integrity, each student agrees to the following Honor Pledge: "I pledge, on my honor, to conduct myself with the foremost level of academic integrity." A student who lives by the Honor Pledge is a student who does more than not cheat, falsify, or plagiarize. A student who lives by the Honor Pledge espouses academic integrity as an underlying and essential principle of the Utah State University community, understands that each act of academic dishonesty devalues every degree that is awarded by this institution, and is a welcomed and valued member of Utah State University.
      • Plagiarism: Plagiarism includes knowingly "representing by paraphrase or direct quotation, the published or unpublished work of another person as one's own in any academic exercise or activity without full and clear acknowledgment. It also includes the unacknowledged use of materials prepared by another person or agency engaged in the selling of term papers or other academic materials." The penalties for plagiarism are severe. They include warning or reprimand, grade adjustment, probation, suspension, expulsion, withholding of transcripts, denial or revocation of degrees, and referral to psychological counseling.
    • 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.
    • Within the first week of the semester, please email the professor your handle (user name) on CodeForces. In your email, also let the professor know whether you would like to join a class list called Karuna (read more about the list feature here). Note that this class list and your profile on CodeForces are public, and moreover all coding activities associated with your profile have permanent records that are viewable by everyone. If you wish to be anonymous to the rest of the class and to the public, you can elect to not have your handle included in the Karuna list, not display your name in your Codeforces profile, and select a handle with a mysterious air that does not reveal your real identity. Even if you are not on Karuna list, your scores will still be properly recorded by the professor as long as he knows your handle.
    • Your enrollment in the course beyond the first week implies your enthusiastic consent to the grading policy described here.
  • Programming Languages and Algorithmic Topics: The professor uses only C, C++, Java, and Python, but you can use any programming language supported by CodeForces. By solving CodeForces contest problems, you may gradually learn a wide range of algorithmic techniques for rapid problem solving, such as 2-sat, binary search, bitmasks, brute force, chinese remainder theorem, combinatorics, constructive algorithms, data structures, dfs and similar, divide and conquer, dp, dsu, expression parsing, fft, flows, games, geometry, graph matchings, graphs, greedy, hashing, implementation, math, matrices, meet-in-the-middle, number theory, probabilities, schedules, shortest paths, sortings, string suffix structures, strings, ternary search, trees, two pointers, and possibly more.
  • Prerequisite and Repeatability: At least 2.5 GPA and grade of C- or better in CS2420 are required. This course aims at improving problem solving skills rather than gaining a fixed body of knowledge. The contest problems used in this course are guaranteed to be completely different from semester to semester. The students are encouraged to take this course repeatedly for continual improvement and additional credits.
  • Schedule (subject to change; occasionally a class would overlap with a rated contest and as such may be canceled if demanded by majority of students):
    • Jan 9 11:
      • Lecture, Tue Jan 9.
      • Practice Contest 0 (pair), Thu Jan 11. 837 status
    • Jan 16 18:
      • Practice Contest 1 (solo), Tue Jan 16. 835 status
      • Practice Contest 2 (pair), Thu Jan 18. 834 status
    • Jan 23 25:
      • Practice Contest 3 (solo), Tue Jan 23. 900 status
      • Practice Contest 4 (pair), Thu Jan 25. 894 status
    • Jan 30 Feb 1:
    • Feb 6 8:
      • Practice Contest 5 (solo), Tue Feb 6. 887 status
      • Practice Contest 6 (pair), Thu Feb 8. 839 status
    • Feb 13 15:
      • Practice Contest 7 (solo), Tue Feb 13. 864 status
      • Practice Contest 8 (pair), Thu Feb 15. 816 status
    • Feb [20] 22:
      • No class on Tue Feb 20 (Monday schedule).
      • Lecture, Thu Feb 22. 932A 932B 816C 760B
    • Feb 27 Mar 1:
      • Practice Contest 9 (solo), Tue Feb 27. 890 status
      • Practice Contest 10 (pair), Thu Mar 1. 872 status
    • Mar [6 8]:
      • No classes (Spring break).
    • Mar 13 15:
      • Practice Contest 11 (solo), Tue Mar 13. 876 status
      • Practice Contest 12 (pair), Thu Mar 15. 854 status
    • Mar 20 22:
      • Practice Contest 13 (solo), Tue Mar 20. 861 status
      • Practice Contest 14 (pair), Thu Mar 22. 851 status
    • Mar 27 29:
    • Apr 3 5:
      • Practice Contest 15 (solo), Tue Apr 3. 844 status
      • Practice Contest 16 (pair), Thu Apr 5. 811 status
    • Apr 10 12:
      • Practice Contest 17 (solo), Tue Apr 10. 810 status
      • Practice Contest 18 (pair), Thu Apr 12. 794 status
    • Apr 17 19:
      • Practice Contest 19 (solo), Tue Apr 17. 807 status
      • Practice Contest 20 (pair), Thu Apr 19. 805 status
    • Apr 24 26:
  • Academic Freedom and Professional Responsibilities: Academic freedom is the right to teach, study, discuss, investigate, discover, create, and publish freely. Academic freedom protects the rights of faculty members in teaching and of students in learning. Freedom in research is fundamental to the advancement of truth. Faculty members are entitled to full freedom in teaching, research, and creative activities, subject to the limitations imposed by professional responsibility. USU Policy 403 further defines academic freedom and professional responsibilities.
  • Sexual Harassment: Sexual harassment is defined by the Affirmative Action/Equal Employment Opportunity Commission as any "unwelcome sexual advances, requests for sexual favors, and other verbal or physical conduct of a sexual nature." If you feel you are a victim of sexual harassment, you may talk to or file a complaint with the Affirmative Action/Equal Employment Opportunity Office located in Old Main, Room 161, or call the AA/EEO Office at (435) 797-1266.
  • Students with Disabilities: The Americans with Disabilities Act states: "Reasonable accommodation will be provided for all persons with disabilities in order to ensure equal participation within the program.” If a student has a disability that will likely require some accommodation by the instructor, the student must contact the instructor and document the disability through the Disability Resource Center (435) 797-2444, preferably during the first week of the course. Any request for special consideration related to attendance, pedagogy, taking of examinations, etc., must be discussed with and approved by the instructor. In cooperation with the Disability Resource Center, course materials will be provided in alternative format (e.g. large print, audio, diskette, or Braille) upon request.
  • Additional University Policies and Procedures: here.