CS 2420 Algorithms and Data Structures, Fall 2017

  • Time and Place: Mon Wed Fri 1:30 - 2:20 pm at Huntsman Hall 222 (Section 1) and 2:30 - 3:20 pm at Widtsoe Hall 007 (Section 2)
  • Course Website: https://sites.google.com/site/drminghuijiang/cs2420
  • Professor: Dr. Minghui Jiang
    • Contact: mjiang@cc.usu.edu, 435-797-0347
    • Office hours: Mon Wed Fri 3:20 - 4:00pm, Main 402G (by appointment only, email professor before noon or approach professor in class)
  • Teaching Assistants: Jiyao Li (Section 1) and Kaige Zhang (Section 2).
    • Contact: jiyao.li@aggiemail.usu.edu (Jiyao); kg.zhang@aggiemail.usu.edu (Kaige)
    • Office hours: Tue Fri 10:30 - 12:00 noon, Main 422 (Jiyao); Mon Thu 10:00 - 11:30am, Main 422 (Kaige)
    • Please note that the two sections have a total enrollment of around 200 students. The professor tries to respond to all emails in a timely manner, but suggests that you seek help from the teaching assistants first.
  • Textbook: Data Structures and Algorithm Analysis in C++ (4th Edition) (required) or Java (3rd Edition) (optional) by M. A. Weiss.
  • 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.
      • Gain knowledge on a variety of common computational problems and their algorithmic solutions.
      • Develop programming skills in implementing standard data structures and algorithms to solve computational problems.
    • [IDEA Objective 2 - Important] Learning fundamental principles, generalizations, or theories.
      • Learn theoretical concepts for analyzing the time and space complexities of an algorithm.
  • ABET Student Outcomes:
    • [C] An ability to design, implement, and evaluate a computer-based system, process, component, or program to meet desired needs;
    • [J] An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices.
  • University Policies and Procedures: here.
  • Course Fee: There is a course fee of $60 for teaching assistants.
  • Prerequisite: 2.0 GPA; grade of C- or better in CS 1410.
  • Grading: Canvas ( Section 1 Section 2 )
    • Three programming websites are heavily used: CodeChef, HackerRank, and HackerEarth. The professor's profile pages on these websites are dukkha, Dukkha, and Dukkha. In each lecture, the professor either solves practice problems on these websites (live programming on big screen together with the students), or reviews solutions to problems from recent contests. The practice problems covered in the two sections are similar in style but not necessarily identical. All problems covered in either section are posted here on the course homepage as homework for both sections. Although the practice problems for homework are not graded, it is important that you work on them persistently to master the algorithmic concepts. You are encouraged to consult the professor's solutions, to discuss with your classmates, and to ask the teaching assistants and the professor for help, if you have difficulty solving these homework problems or any other practice problems on these websites.
    • Please register on all three websites and submit (on Canvas) urls of your profile pages within the first week of the semester. You can choose any sequence of symbols allowed by the respective website as your handle, but the name displayed on your profile pages must be either your real name, or empty if you prefer to be anonymous to the public. For the convenience of the professor and the TAs, it is highly recommended that you enter "Utah State University" as "Organisation" or "Institution" or "School" on CodeChef, as "School" on HackerRank, and as "Education" on HackerEarth. Select or type "Utah State University" precisely, not other variations such as "Utah State University, Logan" or "utah state university". Then your contest standing on leaderboard can be filtered by "Utah State University" (for example, here and here).
    • Instead of quizzes and exams, you are expected to participate in the following rated programming contests throughout the semester:
      • CodeChef Long Challenge (typically 10 problems in 10 days for each contest): SEPT17, OCT17, NOV17, and maybe DEC17.
      • HackerRank Week of Code (typically 6 problems in 7 days for each contest): w35, w36, w37, and maybe w38.
      • HackerEarth Circuits (typically 8 problems in 9 days for each contest): September, October, November, and maybe December.
      To acquaint yourself with the various contest platforms, you can practice on some easy problems on each website here, here, here, and read FAQs here, here, here.
    • Only the contests listed above are considered for grades. There are around 10 such contests during September, October, November, and December. Please follow the contest rules and work independently. Do not cheat. Do not ask the professor or any other person for help on problems in live contests. Do not help the professor or any other person on problems in live contests (yes the professor himself competes in these contests too). Do not discuss strategies on solving live contest problems. Keep in mind that these websites have plagiarism detectors and code of conduct. Keep in mind that Utah State University has regulations regarding academic integrity.
    • As soon as a contest is over, all problems in the contest automatically become homework problems. Then you are encouraged to consult the professor's solutions, to discuss with your classmates, and to ask the teaching assistants and the professor for help if necessary, in order to solve the problems that you didn't solve, or to improve your solutions to the problems that you did solve. This is called upsolving and it is an effective way to improve your performance in future contests. The first lecture after the completion of each contest is usually an analysis session, in which the professor demonstrates his own solutions to the contest problems.
    • You can use any programming languages supported by the three websites to solve contest and practice problems. The professor often solves the same problem multiple times using up to four different languages, in the order of C++ (C++14), Java (Java 8), C (ANSI C), and Python (Python 3), to illustrate the same algorithmic ideas. The professor puts emphasis on C++, and exposes students to the other three languages only if time permits. Reading tutorials listed in the Programming References section of this webpage and solving problems in HackerRank language tracks is a quick way to learn these languages.
    • If you get x points in any contest with y total points, then you get 100(x/y) scaled point (a real number between 0 and 100). Your grade depends on the ratio, of your total scaled points from all contests, over the class average of all students in the two sections. The professor will determine the exact dividing lines between consecutive grades at his discretion, 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 total number of scaled points is at least 1.5 times the class average, then you are guaranteed to receive an A grade; if your total number of scaled points 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 participate in all contests and solve at least one problem completely (that is, your solution passes all testcases of that problem) in each of these contests, then you are also guaranteed to receive no worse than a C- grade.
    • The professor may give a student a grade that is one step higher than the initial grade determined by contest standing, if he observes that the student regularly attends lectures, actively participates in classroom discussions, and diligently solve practice problems for homework. 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 contest standing.
  • Topics:
    • basics HE HE HR; bit manipulation HE HR; strings HE HR; recursion HE HR; brute force HR.
    • linear data structures (Chapter 3): arrays HE HR, linked lists HE HR, stacks HE HR, queues HE HR.
    • sorting and searching (Chapter 7): HE HE HR HR.
    • trees and hash tables (Chapter 4 and Chapter 5): HE HE HE HR
    • heaps and priority queues (Chapter 6): HE HR.
    • disjoint sets (Chapter 8): HE HR.
    • greedy algorithms (Section 10.1): HE HR.
    • graph algorithms (Chapter 9): HE HR HR.
    • dynamic programming (Section 10.3): HE HR.
  • Programming References:
  • Schedule (subject to change):
ċ
gcd.cpp
(0k)
Minghui Jiang,
Sep 8, 2017, 2:53 PM
ċ
gcd_strings.cpp
(0k)
Minghui Jiang,
Sep 8, 2017, 5:14 PM
ċ
monk_and_chamber_of_secrets.cpp
(1k)
Minghui Jiang,
Sep 15, 2017, 2:11 PM
ċ
mystery_30.cpp
(0k)
Minghui Jiang,
Sep 8, 2017, 2:52 PM
ċ
mystery_31.cpp
(0k)
Minghui Jiang,
Sep 8, 2017, 2:52 PM
ċ
n_queens.cpp
(1k)
Minghui Jiang,
Sep 13, 2017, 2:31 PM
ċ
sort.cpp
(2k)
Minghui Jiang,
Sep 20, 2017, 1:20 PM
ċ
subham_and_binary_strings.cpp
(0k)
Minghui Jiang,
Sep 6, 2017, 2:29 PM
ċ
the_football_fest.cpp
(1k)
Minghui Jiang,
Sep 15, 2017, 1:05 PM
ċ
the_football_fest2.cpp
(0k)
Minghui Jiang,
Sep 15, 2017, 1:17 PM