BYU CS Logo
Computing That Serves

CS 252

Course Offerings

Section # Semester Instructor Website Description
1 Fall 2017 Cory Barker
2 Fall 2017 Cory Barker
Section # Semester Instructor Website Description
1 Winter 2018 Dennis Ng
2 Winter 2018 Dennis Ng
1 Fall 2017 Cory Barker
2 Fall 2017 Cory Barker
1 Spring-Summer 2017 Cory Barker https://faculty.cs.byu.edu/~barker/cs252/index.php
1 Winter 2017 Dennis Ng https://learningsuite.byu.edu/.THIp/cid-4uB5d7ucFugY/home
2 Winter 2017 Dennis Ng https://learningsuite.byu.edu/.THIp/cid-4uB5d7ucFugY/home
1 Fall 2016 Cory Barker
2 Fall 2016 Cory Barker
1 Winter 2016 Dennis Ng https://students.cs.byu.edu/~cs252ng/
2 Winter 2016 Dennis Ng https://students.cs.byu.edu/~cs252ng/
1 Fall 2015 Cory Barker http://beta.cs.byu.edu/~cs252/index.php
2 Fall 2015 Cory Barker http://beta.cs.byu.edu/~cs252/index.php
1 Spring-Summer 2015 Dennis Ng https://students.cs.byu.edu/~cs252ng/
1 Winter 2015 cs grad
2 Winter 2015 Michael Jones
1 Fall 2014 Dan Ventura http://axon.cs.byu.edu/Dan/252
2 Fall 2014 Dan Ventura http://axon.cs.byu.edu/Dan/252
1 Spring-Summer 2014 Dennis Ng http://students.cs.byu.edu/~cs252ng/
1 Winter 2014 Michael Jones https://learningsuite.byu.edu/view/jRQYECwf_zgA.html
2 Winter 2014 Michael Jones https://learningsuite.byu.edu/view/jRQYECwf_zgA.html
1 Fall 2013 Dennis Ng http://students.cs.byu.edu/~cs252ng/ CS 252, Section 1 Homepage
2 Fall 2013 Dan Ventura http://axon.cs.byu.edu/Dan/252
3 Fall 2013 Dan Ventura http://axon.cs.byu.edu/Dan/252
1 Spring 2013 Dennis Ng http://students.cs.byu.edu/~cs252ng/~
1 Winter 2013 Michael Jones
2 Winter 2013 Michael Jones
1 Fall 2012 Dennis Ng http://students.cs.byu.edu/~cs252ng/
2 Fall 2012 Dennis Ng http://students.cs.byu.edu/~cs252ng/
3 Fall 2012 Dan Ventura http://axon.cs.byu.edu/Dan/252
1 Spring 2012 cs grad http://students.cs.byu.edu/~cs252ng/
1 Winter 2012 Dennis Ng http://students.cs.byu.edu/~cs252ng/
2 Winter 2012 Dennis Ng http://students.cs.byu.edu/~cs252ng/
3 Winter 2012 Dennis Ng http://students.cs.byu.edu/~cs252ng/
1 Fall 2011 Dan Ventura http://axon.cs.byu.edu/Dan/252
2 Fall 2011 cs grad http://axon.cs.byu.edu/~aaron/252
3 Fall 2011 Michael Jones http://syllabus.byu.edu/view/dh7anSoXtza8.html
1 Summer 2011 cs grad
1 Spring 2011 Michael Jones https://facwiki.cs.byu.edu/jones/cs252/index.php/Main_Page
1 Winter 2011 Michael A. Goodrich https://facwiki.cs.byu.edu/cs252winter11/index.php/Main_Page
2 Winter 2011 Michael A. Goodrich https://facwiki.cs.byu.edu/cs252winter11/index.php/Main_Page
3 Winter 2011 Michael Jones https://facwiki.cs.byu.edu/jones/cs252/index.php/Main_Page
1 Fall 2010 Dan Ventura http://axon.cs.byu.edu/Dan/252
2 Fall 2010 Dennis Ng http://students.cs.byu.edu/~cs252ng/
3 Fall 2010 Dennis Ng http://students.cs.byu.edu/~cs252ng/
1 Spring 2010 Michael Jones https://cswiki.cs.byu.edu/jones/cs252
1 Winter 2010 Michael A. Goodrich http://students.cs.byu.edu/~cs252ta/winter2010/
2 Winter 2010 Michael A. Goodrich http://students.cs.byu.edu/~cs252ta/winter2010/
3 Winter 2010 Dennis Ng http://students.cs.byu.edu/~cs252ng/
1 Fall 2009 Dan Ventura http://axon.cs.byu.edu/Dan/252
2 Fall 2009 Dan Ventura http://axon.cs.byu.edu/Dan/252
1 Spring 2009 Dennis Ng http://students.cs.byu.edu/~cs252ng/
1 Winter 2009 Michael A. Goodrich http://students.cs.byu.edu/~cs252ta/winter2009/
2 Winter 2009 Michael A. Goodrich http://students.cs.byu.edu/~cs252ta/winter2009/
3 Winter 2009 Dennis Ng http://students.cs.byu.edu/~cs252ng/
1 Fall 2008 Dan Ventura http://axon.cs.byu.edu/Dan/252/
2 Fall 2008 Dan Ventura http://axon.cs.byu.edu/Dan/252/
1 Spring 2008 cs grad http://roc.cs.byu.edu/cs252/index.php/Main_Page
1 Winter 2008 Michael A. Goodrich http://students.cs.byu.edu/~cs252ta/winter2008/
2 Winter 2008 Michael A. Goodrich http://students.cs.byu.edu/~cs252ta/winter2008/
3 Winter 2008 Dennis Ng http://students.cs.byu.edu/~cs252ng/
1 Fall 2007 Dan Ventura http://axon.cs.byu.edu/Dan/252
2 Fall 2007 Dan Ventura http://axon.cs.byu.edu/Dan/252
1 Spring 2007 Michael A. Goodrich http://students.cs.byu.edu/~cs252ta/spring2007/
1 Winter 2007 Cory Barker http://code.cs.byu.edu/~cs252/winter2007
2 Winter 2007 Dennis Ng http://students.cs.byu.edu/~cs252ng/
3 Winter 2007 Dennis Ng http://students.cs.byu.edu/~cs252ng/
1 Fall 2006 Dan Ventura http://axon.cs.byu.edu/Dan/252
2 Fall 2006 Dan Ventura http://axon.cs.byu.edu/Dan/252
2 Fall 2006 Dan Ventura http://axon.cs.byu.edu/Dan/252
1 Spring 2006 Dennis Ng http://students.cs.byu.edu/~cs252ng/
1 Winter 2006 Michael A. Goodrich http://code.cs.byu.edu/~cs252/winter2006/
2 Winter 2006 Michael A. Goodrich http://code.cs.byu.edu/~cs252/winter2006/
3 Winter 2006 Cory Barker http://code.cs.byu.edu/~cs252/winter2006/
1 Fall 2005 Dan Ventura http://axon.cs.byu.edu/Dan/252
2 Fall 2005 Dan Ventura http://axon.cs.byu.edu/Dan/252
3 Fall 2005 Cory Barker http://code.cs.byu.edu/~cs252/fall2005

Short Summary: 

Introduction to Computational Theory

Credits: 

3

Prerequisites: 

Introduction to Computational Theory

 

Finite automata, regular languages, lexical analysis; push-down automata, context-free languages, parsing; Turning machines and unrestricted grammars; computability complexity, NP-completeness. CS 236 can be taken concurrently with this course.

 

This document is not a syllabus. Instead, for ALL offerings of this course, this document states the purpose, expected objectives, and topics for the course. 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.  The “hours” for topics listed below reflect the approximate number of 50-minute class periods (or equivalent) devoted to each topic.

Purpose

CS 252 provides a mathematically sound course in the foundations of computer science that sharpens the analytical skills of our students and engenders an appreciation of our field.

Learning Outcomes

At the end of this course, students should be able to:

  1. Understand the three computing paradigms (DFAs, PDA, Turing Machine) and their language-based equivalents (regular languages,context-free languages, computable algorithms).
  2. Categorize problems into one of the existing paradigms.
  3. Understand the difference between and limitations of paradigms.
  4. Understand the difference between computable (decidable) and practically computable (tractable).
  5. Design and justify solutions to problems of decidability and tractability.

Topics

  • Introduction, Basics (2-3 hours)
  • Finite State Automata (6-8 hours)
  • Context Free Grammars (4-9 hours)
  • Turing Machines (4-8 hours)
  • (Un)computability (4-6 hours)
  • Complexity (7-10 hours)
  • Advanced topics (probabilistic algorithms, cryptography, quantum computing) (0-5 hours)