CSC 4341 - Competitive Programming

2 lecture hours 2 lab hours 3 credits

Course Description
This course provides an exploration of algorithms and data structure with a focus on their use solving problems presented in programming competitions. A brief introduction to algorithm runtime and space complexity analysis will be given in the context of constraints presented by problems in a competitive programming environment. The course will then present how competitive programming problems can be categorized and solved by recognizing the appropriate algorithm and data structure to use. Lab sessions will consist of practice in solving problems along with writing new problems. (prereq: CSC 1120) (quarter system prereq: CS 2852)

Course Learning Outcomes
Upon successful completion of this course, the student will be able to:

Analyze an algorithm and determine its runtime and space complexity
Break down a competitive programming problem and determine problem details:
Identify problem requirements (inputs and outputs)
Identify data structures and algorithms to use in the solution
Evaluate the efficiency of the solution
Create competitive programming problems
Identify the desired algorithm and data structure for the solution
Create a background story for the problem
Evaluate the limits to set to make the problem challenging

Prerequisites by Topic

Data structures: arrays, linked lists, stacks, graphs, trees
Sorting algorithms, iteration vs recursion

Course Topics

Dynamic programming
Breadth first search
Depth first search
Shortest paths
Minimum spanning tree
String searching and matching
Graphs
Binary search tree
Union-find
Segment tree
Fenwick tree
Trie
Aho-Corasick automaton

Laboratory Topics

Assorted competitive programming problems

Coordinator
Dr. James Lembke

Announcement

The Raider Return

Milwaukee School of Engineering

Connect With MSOE

CSC 4341 - Competitive Programming