This folder contains information from the competitive coding class taught by Andrew Carr and Mitchell Probst during the BYU Winter 2018 semester. There were two main focuses during class this semester: teaching competitive coding to prepare for the ACM and introducing students to Machine Learning and sklearn.
The class was setup with all of the competitive coding being run through Hackerrank using an e-mail account we created for this purpose:
Username: acme.coding.competition@gmail.com
Password: Ask your ACME professor.
If you are NOT part of the BYU ACME curriculum, but want access to the Hackerrank problems that were created by us, please feel free to send either one of us an e-mail at: mitchellprobst@gmail.com or andrewcarr06@gmail.com.
Future classes may choose to re-use the same contests, because Hackerrank will allow you to modify start/end times of a contest, however we found no way to erase the leaderboard, so it will become critical to closely track each user and their performance on the Vat and on the blitzes..
The class had two core components throughout the semester: Competitive Programming (The Vat) and Introduction to Machine Learning.
Although the 2017 Fall Semester wasn't a pre-requisite for this class, we did assume that most people in the class at this point had at least passed the first semester of the ACME junior core, and as such have a deeper understanding of Python in comparison to our expectations for students last semester. There was one pre-ACME student in our class who did need syntax help, but was still a bright student and performed well.
The Vat was a huge collection of problems ranging from Easy-Advanced. We made each easy problem worth 3 points, medium problems worth 6, and hard problems worth 10. There were 2 bonus advanced problems worth up to 20 points (students could earn partial credit on these assignments). Students were expected to earn 100 points by the end of the semester in order to receive full credit for the Vat. The Vat consisted of 20% of the student's grade and so the formula used to determine the amount of points was (Points Earned by Students / 5 ). Students could earn an additional 5% if they earned more than 100 points.
WARNING: Virtually every one of these problems have solutions available online. It is incredibly easy for a student to have cheated on the vat in an effort to get points. Most problems even have python solutions written in the discussion boards, so be aware that some students may attempt to copy-paste answers.
The breakdown of problems in the Vat with native hackerrank links if applicable:
- Left Rotation
- Marc's Cakewalk
- Library Fine
- Handshake
- Sherlock and Moving Tiles
- Mars Exploration
- Sherlock and The Beast
- Time Conversion
- Sparse Arrays
- Japanese Cities' Names
- Cutting Paper Squares
- Picking Cards
- Mark and Toys
- Learn and Go 3-3: Mixed Bases (From Fall 2017 Semester)
- Ema's Supercomputer
- Quicksort In-Place
- Contacts
- Lily's Homework
- Validating Credit Card Numbers
- Password Cracker
- Bonetrousle
- Bob and Ben
- Alice and Bob's Silly Game
- Snakes and Ladders: The Quickest Way Up
- One Away (Problem taken from Cracking the Coding Interview)
We stopped after going through 6 Hard problems in order to have more time to do everything else we wanted to do this semester. Solutions and relevant tips to the first 6 Hard problems are available in this repository here.
- Knights? Who Needs Knights (Self Made Problem)
- Secret Chamber at Mount Rushmore Taken from 2017 ICPC World Competition
- Xoring Ninja
- Angry Children 2
- Components in a graph
- K Factorization
- Lovely Triplets
- Reverse Shuffle Merge
Several class days were devoted to working on the first 6 Hard Problems, often together where we would give students a very strong hint to know how to solve the problem, or to understand what approach needed to be taken. We had asked students to read the problems ahead of time and to have attempted them on their own. Quizzes were used to track the students who did this.
We wanted to dedicate a portion of class giving students an opportunity to begin coding up ML Algorithms to give juniors exposure to sklearn, and to give senior's more confidence in their ability to use sklearn. We did not cover any theoretics behind these Algorithms, we simply told them what they were useful for and provided examples. During the semester we covered classification, clustering, regression, and dimensionality reduction.
Each section has a .pdf file that gives an overall explanation for what we asked students to accomplish for each task. We presented instructional material showing them examples of the method on alternative data sets, and asked students to submit a small write-up (usually through jupyter notebook) for code that they tried, and to provide supplemental information behind what decisions they chose (which features to use or how they opted to clean data).
This was worth 20% of their total grade, 5% for each type. We graded primarily based on completion, there was no strict rubric set up for these projects. The projects definitely took significantly less time than the Vat, but was worth just as much.
Classification is a fundamental tool for Machine Learning. Students were asked to take the mushrooms.csv file and try to classify if mushrooms were poisonous or edible. We provided a "Beginner" and an "Advanced" notebook, so that students who were brand new at Machine Learning had some boilerplate code to help (also essential for those who did not know pandas).
We asked students to take the "airquality" data from pydatasets and to try and regress on Ozone. This proved somewhat challenging because this dataset is so small, that it was hard to get consistent results. It did spur a great class conversation on learning how to clean data and knowing how to handle missing data. Students who felt comfortable were asked to create a jupyter notebook from scratch, for those who wanted to, a "Beginner" notebook was available that helps walk them through the basic steps and prompts learning along the way.
We gave the students an opportunity to learn how dimension reduction is possible through tools like PCA. PCA is essentially a Singular Value Decomposition for your feature data, but it can be incredibly powerful when applied to data. We used an already fairly small dataset to give them a chance to do so. Like other notebooks, a "Beginner" was available to help walk them through the process. It contains less detailed information as we assume students have a better understanding of sklearn at this point.
This is the only exposure students have to unsupervised learning. The dataset "animals" is incredibly small, and a few NaNs are missing, which we encouraged students to try and find what those values should have been by looking at resources online. We asked them to compare the inertia of different clusters and report on the results.
No competitive coding class is complete without blitzes to simulate an ACM Competition environment. We held several blitzes throughout the semester to give students additional practice.
An initial blitz that had a couple of challenging problems. We wanted to assess the strength of our coders so we gave them some problems that we knew would be more challenging. They are all probably Medium difficulty.
- largest island 1 (Problem constructed by Andrew for the competition)
- Parts of Speech (A simplified version of an interview problem Andrew received from a company)
- Queen's Attack II
- AND Product
We pulled 5 Medium problems from the Blitz to give students an opportunity to work on the problems together in groups and to encourage some competition. These are arguably some of the harder "Medium" problems in the Vat. Not many students managed to solve the problems but a lot was learned.
This blitz was identical to the Speed Blitz given last semester.
- Learn and Go 0-0: Lists (From LaG 0)
- Learn and Go 1-2: Sets (From LaG 1)
- Zipped! (From LaG 2)
- Project Euler #3: Largest prime factor (From LaG 3)
- CamelCase (From Blitz0-2 or LaG 4)
- Lonely Integer (From LaG 5)
- Learn and Go 2-1: Vending Machine 2 (See LaG 2)
- Left Rotation (From LaG 1)
- Counting Valleys (From LaG 2)
- Designer PDF Viewer (From Blitz0-2)
- "Holy" Numbers (From Blitz3-5)
- Sum vs XOR (From Blitz3-5)
This blitz was thrown together, a random assortment of problems that have no specific connection to each other. These problems are moderately challenging. It was so named because Mitchell's wife had her baby the weekend before this blitz.
The final blitz for the semester. We gave students problems that may have seemed challenging at first glance but actually have some elegant solutions that are not all that difficult.
A core component for the class is that the students participate in a coding competition. This semester, due to a scheduling conflict, the BYU ACM competition (hosted by Pariveda Solutions, link unavailable) was scheduled for the exact same day as the BYU SRC (Student Research Conference). Because of this conflict we gave students the opportunity to compete in the semi-annual Hackerrank University CodeSprint. Most of our students chose to do so, with the best student scoring 280th out of 5,000+ people. Some students still managed to compete in the ACM with the best team achieving 2nd place.
Participating in a coding competition was worth 50% of the students grade.
Near the end of the semester we spent a couple of days asking the students to set up a website through pages.github.com. We showed them Andrew's site as an example to indicate that it does not have to be incredibly flashy, but that it should look like something you are proud of.