Computing That Serves

CS 312

Course Offerings

Section # Semester Instructor Website Description
1 Fall 2017 Dan Ventura
2 Fall 2017 Dan Ventura
Section # Semester Instructor Website Description
1 Winter 2018 Ryan Farrell
2 Winter 2018 Ryan Farrell
1 Fall 2017 Dan Ventura
2 Fall 2017 Dan Ventura
1 Winter 2017 Ryan Farrell
2 Winter 2017 Ryan Farrell
1 Fall 2016 Dan Ventura
2 Fall 2016 Dan Ventura
1 Winter 2016 Dan Ventura
2 Winter 2016 Dan Ventura
1 Fall 2015 Tony Martinez
2 Fall 2015 Tony Martinez
1 Spring-Summer 2015 cs grad
1 Winter 2015 Eric Ringger Algorithm Design and Analysis
2 Winter 2015 Eric Ringger Algorithm Design and Analysis
1 Fall 2014 Tony Martinez
2 Fall 2014 Tony Martinez
1 Spring-Summer 2014 cs grad
1 Winter 2014 Eric Ringger
2 Winter 2014 Eric Ringger
1 Fall 2013 Tony Martinez
2 Fall 2013 Tony Martinez
3 Fall 2013 Sean Warnick
1 Summer 2013 Eric Ringger
1 Winter 2013 Sean Warnick
2 Winter 2013 Sean Warnick
3 Winter 2013 Eric Ringger
1 Fall 2012 Tony Martinez
2 Fall 2012 Tony Martinez
1 Summer 2012 cs grad
1 Spring 2012 cs grad
1 Winter 2012 Eric Ringger
2 Winter 2012 Eric Ringger
1 Fall 2011 Tony Martinez
2 Fall 2011 Sean Warnick
1 Spring 2011 cs grad
1 Winter 2011 Eric Ringger
2 Winter 2011 Eric Ringger
1 Fall 2010 Sean Warnick
2 Fall 2010 Tony Martinez
1 Spring 2010 cs grad
1 Winter 2010 Eric Ringger
2 Winter 2010 Eric Ringger
1 Fall 2009 Tony Martinez
2 Fall 2009 Jay McCarthy
1 Spring 2009 Michael Jones
1 Winter 2009 Eric Ringger
2 Winter 2009 Eric Ringger
1 Fall 2008 Sean Warnick
2 Fall 2008 Sean Warnick
1 Spring 2008 Michael Jones
1 Winter 2008 Eric Ringger
2 Winter 2008 Eric Ringger
1 Fall 2007 Sean Warnick
2 Fall 2007 Sean Warnick
1 Spring 2007 cs grad
1 Winter 2007 Michael Jones
2 Winter 2007 Michael Jones
3 Winter 2007 Eric Ringger
1 Fall 2006 Sean Warnick
2 Fall 2006 Sean Warnick
3 Fall 2006 Eric Ringger
1 Spring 2006 cs grad
1 Winter 2006 Michael Jones
2 Winter 2006 Eric Ringger
3 Winter 2006 Eric Ringger
1 Fall 2005 Sean Warnick
2 Fall 2005 Sean Warnick
3 Fall 2005 cs grad

Short Summary: 

Algorithm Design and Analysis





Windows, Visual Studio



A study of the design and analysis of algorithms as solutions to problems, including dynamic programming, linear programming, greedy algorithms, divide-and-conquer algorithms, graph algorithms, and intelligent search algorithms.


CS 312 Objectives and Topics

This document is not a syllabus. Instead, for ALL offerings of this course, this document states the expected objectives and topics for the course and the approximate number of 50-minute lectures to be devoted to each topic. Faculty members teaching this course should adhere to these objectives and topics. Students taking this course can expect to achieve the objectives and cover the topics specified, and faculty members teaching follow-on courses can expect students to have been appropriately exposed to the prerequisite material as stated.

Learning Outcomes

Fundamental Computer Algorithms

The student understands fundamental computer algorithms that can be organized in the following algorithmic paradigms: dynamic programming, linear programming, greedy algorithms, divide-and-conquer algorithms, graph algorithms, intelligent search algorithms, and --to a lesser degree--randomized algorithms. As an algorithmic problem solver, the student can formulate novel or unfamiliar problems in mathematical terms so as to elucidate a given problem's relation to known problems, choose a paradigm for solving the problem, and design an algorithm to solve the problem.


The student can analyze algorithms belonging to those algorithmic paradigms for their asymptotic worst-case behavior in terms of time and space. Furthermore, the student can analyze algorithms empirically (under simplifying assumptions) and understands the relationship of empirical analysis to average-case behavior. Also, the student can solve LTI difference equations (with geometric forcing functions and change of variable) and can use them to analyze the efficiency of recursive algorithms.


The student can make the distinction between problems and their algorithmic solutions. Moreover, the student can distinguish between efficient and inefficient solutions and can relate these distinctions to the complexity classes of problems, namely P, NP, and NP-Complete learned earlier in the curriculum (CS 252).


The student can prove the correctness of a subset of the algorithms considered in the course.


The student can independently implement selected algorithms in the context of motivating applications using C# with the Visual Studio IDE.



Review                  (the equivalent of 2 lectures scattered throughout, as concepts are encountered)
        Big Oh analysis
        recurrence relations

Divide-and-Conquer      (8 lectures)
        mergesort, binary search
        strassen matrix multiplication
        Deriving Big Oh bounds on Divide-and-Conquer algorithms

Greedy                  (8 lectures)
        job scheduling
        fractional knapsack
        heaps and disjoint sets
        minimal spanning trees- Kruskal, Prim
        deriving Big Oh bounds on greedy algorithms
        proving Greedy algorithms work
        proving Greedy algorithms fail

Dynamic Programming     (8 lectures)
        matrix chain multiplication
        longest common subsequence
        Traveling Salesperson 
        0-1 knapsack
        reduction of Big Oh bounds for some NP-complete problems

Backtracking            (8 lectures)
        Traveling Salesperson and kill rules
        colored block problem
        chess problems
        static/dynamic 0-1 knapsack backtracking
        applications to NP-complete problems

Branch-and-bound        (8 lectures)
        reduced matrices
        approximations to NP-complete problems
        memory management
        kill rules
        seed heuristics
        Big Oh bounds on heuristics

Prerequisite(s): CS 240 & CS 252; or CS 240 & Bio 365