BS Computer Science – Theory Thread

Discover the theoretical foundations underlying a wide range of computing disciplines.

The Theory thread is where computing models and addresses scaling. Theory quantifies, in mathematical terms, the efficiency by which problems are solved, as problem instances grow in size. 

In the Theory thread, students study abstractions of universal computational models, complexity classes within which many natural problems fall, and abstract methods to design efficient algorithms and analyze algorithmic performance. Early preparation includes introduction to programming, discrete math, proof techniques, algorithms and complexity. The student who pursues the Theory thread will eventually learn to formally quantify and improve performance either within theoretical computer science, or within an applied area of computer science, or in another science with a clear computational component (such as computational biology, physics, economics, mathematics, optimization etc).

A student can combine Theory with Information Internetworks to enhance and quantify the performance of networks or databases or pursue security and cryptography, or with Systems & Architecture to design programming languages or build provably efficient systems and software, or with Modeling & Simulation to solve, with proven rigor, a wide range of real-world large scale problems. A student who pursues Theory can combine it with any other thread and enhance those skills with a deep quantitative understanding of performance of the objects studied in the other thread. In addition, in any application related work environment, from a research or development lab, to a consulting firm or the stock market, ability to design tools, reason about them formally, and quantify performance is a skill that greatly enhances one's vita. 

A student who pursues the theory thread at Georgia Tech is also an excellent candidate for a Ph.D. in theoretical computer science.

Theory

Early Preparation

  • Fundamentals of programming
  • Discrete structures
  • Proofs and proof techniques
  • Calculus, linear algebra, probability and statistics
  • Algorithms and Complexity theory

Knowledge Goals

  • Advanced efficient algorithms and their analysis
  • Complexity classes, and hardness of computation
  • Computational problem solving in selected application domains (e.g. theoretical computer science, an applied computer science domain, or another science with a clear computational component).

Skill Outcomes

  • Ability to develop and analyze advanced algorithms taking into account fundamental limits.
  • Ability to quantify performance of systems that arise in computer science or other sciences.



Resources and Role Models

 

If you are following one of the BSCS Threads study plans implemented before Summer 2012 or one of the BSCS study plans that were in place prior to Threads, click here.

Required Courses (For Students in the Program of Study that begins in Summer 2012)

View the course prerequisites for the Theory Thread.

Honors versions of CS, MATH, and ISYE courses are encouraged, but not required, unless explicitly specified.

Programming, Mathematics and Theoretical Computer Science

  • CS1301 Introduction to Computing and Programming, 3
  • CS1331 Introduction to Object-Oriented Programming, 3
  • CS1332 Data Structures and Algorithms, 3
  • CS2050 or CS2051 Introduction to Discrete Math for CS, 3
  • CS2110 Computing Organization and Programming, 4
  • CS2340 Objects and Design, 3
  • CS4510 Automata and Complexity Theory, 3
  • CS4540 Advanced Algorithms, 3
  • MATH2406 Abstract Vector Spaces, 3 (Requires MATH1502 or MATH1512)

Pick 1 of Introduction to Algorithms:

  • CS3510 Design and Analysis of Algorithms, 3
  • CS3511 Design and Analysis of Algorithms, Honors, 3

Pick 1 of Advanced Mathematics:

  • MATH4022 Introduction to Graph Theory, 3
  • MATH4032 Combinatorial Analysis, 3
  • MATH4150 Introduction to Number Theory, 3

Elective Courses (pick and choose whatever courses you wish)

Free Electives (9 hours)

  • FREE-FND1 Free Elective-Foundations, 3
  • FREE-FND2 Free Elective-Foundations, 3
  • FREE-FND3 Free Elective-Foundations, 3

Advanced Algorithms and Complexity

  • CS3240 Languages and Computation, 3
  • CS4520 Approximation Algorithms, 3 (Prereq CS3510 or 3511)
  • CS4530 Randomized Algorithms, 3 (Prereq CS3510 or 3511)
  • CS6520 Computational Complexity, 3 (Prereq CS3510 or 3511)

Mathematics with Computer Science Applications

  • MATH3770 Statistics and Applications, 3 (Requires MATH2401 or 2411. Cross-listed with ISYE and CE)
  • MATH4012 Algebraic Structures for Coding Theory, 3 (Requires MATH1502 or 1512)
  • MATH4150 Introduction to Number Theory and Cryptography, 3 (Requires MATH2406)
  • MATH4107 Abstract Algebra I, 3 (Requires MATH2406)
  • MATH4255 Monte Carlo Methods, 3 (Requires MATH3215 or MATH3225 or MATH3770)
  • MATH4280 Introduction to Information Theory, 3 (Requires MATH3215 or MATH3225)
  • MATH4305 Topics in Linear Algebra, 3 (Requires MATH1502 or MATH1512 or MATH1522)
  • MATH4580 Linear Programming, 3 (Requires MATH1502 or MATH1512)
  • MATH4640 Numerical Analysis I, 3 (Requires MATH2403 or MATH2413 or MATH 2602)
  • MATH4782 Quantum Information and Quantum Computation, 3

Examples of Computer Science Applications involving Algorithms and Complexity

  • CS3251 Computer Networking I, 3
  • CS4400 Introduction to Database Systems, 3
  • CS4235 Introduction to Information Security, 3
  • CS3210 Design of Operating Systems, 3
  • CS3451 Computer Graphics, 3 (Must come after MATH2605 and 2110 or 2260)
  • CS4496 Computer Animation, 3
  • CS3600 Introduction to Artificial Intelligence, 3
  • CS4641 Machine Learning, 3
  • CS4140 Computational Modeling Algorithms, 3
  • CS4335 Modeling and Simulation: Fundamentals and Implementation, 3