BYU CS Logo
Computing That Serves

CS 312

Course Offerings

Section # Semester Instructor Website Description
1 Fall 2017 Dan Ventura http://axon.cs.byu.edu/Dan/312/
2 Fall 2017 Dan Ventura http://axon.cs.byu.edu/Dan/312/
Section # Semester Instructor Website Description
1 Winter 2018 Ryan Farrell
2 Winter 2018 Ryan Farrell
1 Fall 2017 Dan Ventura http://axon.cs.byu.edu/Dan/312/
2 Fall 2017 Dan Ventura http://axon.cs.byu.edu/Dan/312/
1 Winter 2017 Ryan Farrell https://cs.byu.edu/CS312%3A%20https%3A//faculty.cs.byu.edu/~farrell/courses/CS31...
2 Winter 2017 Ryan Farrell https://cs.byu.edu/CS312%3A%20https%3A//faculty.cs.byu.edu/~farrell/courses/CS31...
1 Fall 2016 Dan Ventura http://axon.cs.byu.edu/Dan/312
2 Fall 2016 Dan Ventura http://axon.cs.byu.edu/Dan/312
1 Winter 2016 Dan Ventura http://axon.cs.byu.edu/Dan/312
2 Winter 2016 Dan Ventura http://axon.cs.byu.edu/Dan/312
1 Fall 2015 Tony Martinez http://axon.cs.byu.edu/~martinez/classes/312/
2 Fall 2015 Tony Martinez http://axon.cs.byu.edu/~martinez/classes/312/
1 Spring-Summer 2015 cs grad https://learningsuite.byu.edu/view/AH7n7XGEm63U.html
1 Winter 2015 Eric Ringger http://wiki.cs.byu.edu/cs-312/start Algorithm Design and Analysis
2 Winter 2015 Eric Ringger http://wiki.cs.byu.edu/cs-312/start Algorithm Design and Analysis
1 Fall 2014 Tony Martinez http://axon.cs.byu.edu/~martinez/classes/312/
2 Fall 2014 Tony Martinez http://axon.cs.byu.edu/~martinez/classes/312/
1 Spring-Summer 2014 cs grad http://1drv.ms/1mfnmex
1 Winter 2014 Eric Ringger https://facwiki.cs.byu.edu/cs312ringger/
2 Winter 2014 Eric Ringger https://facwiki.cs.byu.edu/cs312ringger/
1 Fall 2013 Tony Martinez
2 Fall 2013 Tony Martinez
3 Fall 2013 Sean Warnick
1 Summer 2013 Eric Ringger https://facwiki.cs.byu.edu/cs312ringger
1 Winter 2013 Sean Warnick
2 Winter 2013 Sean Warnick
3 Winter 2013 Eric Ringger https://facwiki.cs.byu.edu/cs312ringger/index.php/Main_Page
1 Fall 2012 Tony Martinez http://axon.cs.byu.edu/~martinez/classes/312/
2 Fall 2012 Tony Martinez http://axon.cs.byu.edu/~martinez/classes/312/
1 Summer 2012 cs grad https://facwiki.cs.byu.edu/cs312sum2012/index.php/Main_Page
1 Spring 2012 cs grad http://students.cs.byu.edu/~drackaer/CS312/index.html
1 Winter 2012 Eric Ringger https://facwiki.cs.byu.edu/cs312ringger
2 Winter 2012 Eric Ringger https://facwiki.cs.byu.edu/cs312ringger
1 Fall 2011 Tony Martinez http://axon.cs.byu.edu/~martinez/classes/312/
2 Fall 2011 Sean Warnick http://idealabs.byu.edu/courses/index.htm
1 Spring 2011 cs grad https://facwiki.cs.byu.edu/cs312sp2011/
1 Winter 2011 Eric Ringger https://facwiki.cs.byu.edu/cs312ringger
2 Winter 2011 Eric Ringger https://facwiki.cs.byu.edu/cs312ringger
1 Fall 2010 Sean Warnick http://idealabs.byu.edu/courses/index.htm
2 Fall 2010 Tony Martinez http://axon.cs.byu.edu/~martinez/classes/312/
1 Spring 2010 cs grad
1 Winter 2010 Eric Ringger https://cswiki.cs.byu.edu/cs312ringger
2 Winter 2010 Eric Ringger https://cswiki.cs.byu.edu/cs312ringger
1 Fall 2009 Tony Martinez http://axon.cs.byu.edu/~martinez/classes/312/
2 Fall 2009 Jay McCarthy http://faculty.cs.byu.edu/~jay/courses/2009/fall/312/course/index.html
1 Spring 2009 Michael Jones https://cswiki.cs.byu.edu/jones/cs312/index.php/Main_Page
1 Winter 2009 Eric Ringger http://faculty.cs.byu.edu/~ringger/CS312/
2 Winter 2009 Eric Ringger http://faculty.cs.byu.edu/~ringger/CS312/
1 Fall 2008 Sean Warnick http://idealabs.byu.edu/courses/index.htm
2 Fall 2008 Sean Warnick http://idealabs.byu.edu/courses/index.htm
1 Spring 2008 Michael Jones http://cswiki.cs.byu.edu/jones/
1 Winter 2008 Eric Ringger http://faculty.cs.byu.edu/~ringger/CS312/
2 Winter 2008 Eric Ringger http://faculty.cs.byu.edu/~ringger/CS312/
1 Fall 2007 Sean Warnick https://blackboard.byu.edu/webapps/portal/frameset.jsp
2 Fall 2007 Sean Warnick https://blackboard.byu.edu/webapps/portal/frameset.jsp
1 Spring 2007 cs grad http://rivit.cs.byu.edu/~bprice/CS312/index.html
1 Winter 2007 Michael Jones http://cs312.pbwiki.com/
2 Winter 2007 Michael Jones http://cs312.pbwiki.com/
3 Winter 2007 Eric Ringger http://faculty.cs.byu.edu/~ringger/CS312/
1 Fall 2006 Sean Warnick
2 Fall 2006 Sean Warnick
3 Fall 2006 Eric Ringger http://faculty.cs.byu.edu/~ringger/Fall2006-CS312.3/
1 Spring 2006 cs grad http://vv.cs.byu.edu/cs312-spring2006/
1 Winter 2006 Michael Jones http://vv.cs.byu.edu/cs312/
2 Winter 2006 Eric Ringger http://vv.cs.byu.edu/cs312/
3 Winter 2006 Eric Ringger http://vv.cs.byu.edu/cs312/
1 Fall 2005 Sean Warnick
2 Fall 2005 Sean Warnick
3 Fall 2005 cs grad

Short Summary: 

Algorithm Design and Analysis

Credits: 

3

Prerequisites: 

Platform: 

Windows, Visual Studio

Language: 

C#

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.

Analysis

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.

Efficiency

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).

Correctness

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

Implementation

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

 

Topics

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

Divide-and-Conquer      (8 lectures)
        mergesort, binary search
        quicksort
        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