Overview: Welcome to CSE 232: Programming Skills Workshop! To fully understand the intended purpose of this course, it’s important to be aware of the ACM’s annual ICPC (International Collegiate Programming Competition; Wikipedia). The Washington University ACM has determined that we should make it our goal to win, and if not to win then to get the most out of this opportunity as possible. This class is a means to that end. We wish to train in a collaborative manner, by studying essential algorithms, problem solving skills, coding techniques, and strategy necessary to compete successfully in the ICPC. Unfortunately, not all participants of the class will be able to compete (registration has been limited in past years to 3 teams of 3 students each, at most, from each university). However, in designing this class we have aimed to distill from the oceans of related material specifically that content which we believe to be most useful and applicable to anyone in the field of computer science. Thus, while the formal goal of this class is to prepare you for the ICPC, the real value lies in our belief that the skills developed herein will benefit you in all of your pursuits as a student of computer science*.
Mini-Competitions: There will be approximately 3 small, in-house competitions held throughout the semester. All interested students, staff, and faculty are invited to attend. These competitions serve to provide a realistic practice for prospective competitors, as well as help students decide who should go to the ICPC. Also, there will be free food and it’s a great chance to practice your coding skills, learn new algorithms, and to meet other CS students. If you’re in the class, it’s a part of your grade, too. See Competitons Page.
Topics: Some topics we’d like to cover, broken up by category are listed below. Note:We will most likely not manage to cover all of these. Our hope is to at least touch on the majority of the topics listed below, and give you the tools and inspiration to learn the rest on your own, as needed. A more formal syllabus is available below with a more accurate list of topics to be covered this semester during class time. This list is more to provide a general feel for the kinds of things we’ll touch on and why they are important.
- – Base conversion, string to digit, digit to string, overflows, epsilons, properties of polynomials, logs, sequences, primes, number theory, GCD, LCM, modular arithmetics, combinatorics, etc.
- * All of these are important to be familiar with (and you probably already are); they’re likely to show up in several problems tangentially to the main algorithm.
- Backtracking/Brute Force:
- – Permutations, combinations, heuristic ideas, knowing when to use it
- * Sometimes it really is the only way, and sometimes coder time really is worth many than execution time.
- Data Structures:
- – Graph representations, priority queues, lists, maps, etc.
- * The emphasis will mostly be on how to write these quickly or use ones in the Java library, take CSE 241 for a deeper introduction to these if you haven’t seen them before. Their importance is pretty obvious, but at times making the parsing -> data representation -> data processing transition can be tricky anyway.
- – Dijkstra, max/min flow, spanning trees, BFS/DFS, modeling problems as graphs.
- * Translating seemingly unrelated problems into graph problems can provide easy solutions for a lot of problems. We want you to be able to recognize when to think “graph” and to know what to do with the graph once you’ve made that realization (common algorithms).
- Dynamic Programming
- * Possibly the scariest topic in this course, but also a source of surprisingly efficient algorithms when used properly. Take CSE 441T for a proper introduction to this domain of algorithms; our intent here is to provide a quick overview of what it means and how to use it, mostly in simpler cases.
- Computation Geometry:
- – Grids, intersections, convex hulls, sweep lines, useful equations
- * Take CSE 546 if you really want to learn this stuff. We do intend to show you the basics though and give you some food for thought, and probably a couple algorithms and data structures to snack on.
- Competition Strategy
- * Because we want to win the ICPC