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

Dr. James Lembke

Print-Friendly Page (opens a new window)