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, 4357970347

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 computerbased 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 computerbased 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):

Aug 28 30 Sep 1:

Sep [4] 6 8:

Sep 11 13 15:

Sep 18 20 22:

Sep 25 27 29:

Sorting lower bound.
Shellsort and bucketsort and radixsort.
Hash tables.

Oct 2 4 6:

Heaps and priority queues.

Oct 9 11 13:

Oct 16 18 [19]:

Class on Thursday instead of Friday.

Oct 23 25 27:

Oct 30 Nov 1 3:

Nov 6 8 10:

Nov 13 15 17:

Nov 20 [22 24]:

No classes on Wednesday and Friday (Thanksgiving).

Nov 27 29 Dec 1:

Dec 4 6 8:

Updating...
Minghui Jiang, Sep 8, 2017, 2:53 PM
Minghui Jiang, Sep 8, 2017, 5:14 PM
monk_and_chamber_of_secrets.cpp (1k) Minghui Jiang, Sep 15, 2017, 2:11 PM
Minghui Jiang, Sep 8, 2017, 2:52 PM
Minghui Jiang, Sep 8, 2017, 2:52 PM
Minghui Jiang, Sep 13, 2017, 2:31 PM
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
