The Foundations of Computer Science Track

The Foundations of Computer Science track is intended for students who wish to develop state of the art knowledge of the theoretical foundations of Computer Science. The theory of computation plays a crucial role in providing solid foundations for all areas of Computer Science, including systems, artificial intelligence, security, and circuit design. This track will help you develop leading-edge knowledge of theoretical Computer Science and its applications.

1. Summary of Requirements

Students must complete at least a total of 30 graduate points and must maintain at least 2.7 overall GPA in order to be eligible for the MS degree in Computer Science.

  1. Foundations track requires:

    - Breadth courses
    - Required Track courses (6pts)
    - Track Electives I (3pts)
    - Track Electives II (9 pts)
    - General Electives (3pts)

  2. 2 required courses: CSOR W4231 and COMS W4236.

  3. 1 course chosen from the "Electives I" list: COMS W4203, COMS W4205, COMS W4241, COMS W4252, COMS W4261, or COMS W4281.

  4. At least 9 additional points from the "Electives II" list, excluding the course chosen from the "Electives I" list to satisfy above. At least 6 of the points must be 6000-level courses.

  5. Remaining points from any qualifying graduate course (4000- and 6000-level).

Please use the Degree Progress Check to keep track of your requirements.

2. Breadth Requirement

Students are required to satisfy the Breadth Requirement by taking 1 course from Group 1, 1 course from Group 2, 1 course from Group 3, and 1 more course from any of the three groups. Track courses taken at Columbia can also satisfy the breadth requirement.

Group  Courses
Group 1 (Systems)

All CS 41xx courses except CS 416x and CS 417x
All CS 48xx courses, and CS 4340, 4444, and 4460

Group 2 (Theory)

All CS 42xx courses including CSOR W4231

Group 3 (AI and Apps)

All CS 47xx courses, and CS 416x and CS 417x


3. Required Track Courses

Students are required to complete the following courses. Students who have taken equivalent courses in the past and received grades of at least a B may apply for waivers and take other CS courses instead.

Course ID

Title

CSOR W4231

Analysis of Algorithms I

COMS W4236

Intro. to Computational Complexity


4a. Track Program: Electives I

Students are required to complete one (1) of the following courses:

Course ID

Title

COMS W4203

Graph Theory

COMS W4205

Combinatorial Theory

COMS W4241

Numerical Algorithms and Complexity

COMS W4252

Introduction to Computational Learning Theory

COMS W4261

Introduction to Cryptography

COMS W4281

Introduction to Quantum Computing


4b. Track Program: Electives II

Students are required to complete 9 points out of the following list excluding the course already taken; at least 6 points must be at the 6000 level:

Course ID

Title

COMS W4203

Graph Theory

COMS W4205

Combinatorial Theory

COMS W4241

Numerical Algorithms and Complexity

COMS W4252

Introduction to Computational Learning Theory

COMS W4261

Introduction to Cryptography

COMS W4281

Introduction to Quantum Computing

CSEE E6180

Performance Analysis

COMS W4995

Crypto & Financial Processes

COMS E6204 

Topics in Graph Theory

COMS E6232

Analysis of Algorithms II

COMS E6253

Computational Learning Theory II

COMS E6261

Advanced Cryptography

COMS E6291

Theoretical Topics in C.S.

COMS E6901

Projects in Computer Science

COMS E6998

Adv. Topics in Comp. Geometry

COMS E6998

Adv. Topics in Complexity Theory

COMS E6998

Network Theory 

COMS E6998

Algorithmic Game Theory

COMS E6998

Adv. Topics in Machine Learning

COMS E6998

Formal Verification 

COMS E6998

Algorithms for Dealing with Massive Data

COMS E6998

Advanced topics in Programming Language/Compilers

COMS E6998

Randomness in Computing

COMS E6998

Econ of Social Networks

COMS E6998

Lower Bounds of Theoretical CS

COMS E6998

Sublinear Time Algos Learning

COMS E6998

The TSP in Theory and Practice

CSPH G4802 

Incompleteness Results in Logic

SIEO W4150

Intro. to Probability and Statistics

IEOR E4407

Game Theoretic Models of Operation

IEOR E6400

Scheduling: Deterministic Models

IEOR E6603

Combinatorial Optimization

IEOR E6606

Advanced Topics in Network Flows

IEOR E6608

Integer Programming 

IEOR E6610 

Approximation Algorithms 

IEOR E6613 

Optimization I

IEOR E6614 

Optimization II

IEOR E6711 

Stochastic Models I

IEOR E6712 

Stochastic motels II

IEOR E8100 

Doctoral Seminar on Convex Optimization

ELEN E6718

Algebraic Coding Theory

ELEN E6970

Resource Allocation and Networking Games


5. General Elective

Remaining points from any qualifying Computer Science graduate course (4000- and 6000- level). Students may take up to 3 points of non-CS/non-tech course approved by the advisor. Please complete a non-tech approval form, get your advisor's approval, and forward it to CS Student Services. 

** Known non-tech courses**

IEOR E4550y Entrepreneurial business creation for engineers

6. Track Planning

Please visit the Directory of Classes to get the updated course listings.

Please also note that not all courses are offered every semester, or even every year. A few courses are offered only once every two or three years or even less frequently. For more information, please see the SEAS Bulletin CS course-offering schedule (This schedule can change due to unforeseeable circumstances; thus, it should only be used as a reference).

7. Contact

Please direct all questions concerning the Foundations Track to Prof.

8. Graduation

Candidates preparing for graduation should submit a completed application for degree to the Registrar's Office and submit a track graduation form to CS Student Services.


Updated on 10/4/2013