Theory Thread

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. Computers can store very large datasets and compute at speeds inconceivable to the human mind. The introduction of computers in the 20th century brought to the front of science fundamental questions, such as: “Is everything computable?” “Do different computational problems possess distinct, inherent complexity limitations?” “Are there general techniques that evaluate and improve the efficiency of algorithms?” Beyond computers, these questions touch fundamentals in other sciences, such as: “How does nature compute? How do proteins fold efficiently? How do markets stabilize efficiently?” “How fast do stochastic processes converge?” In fact, it is this particular issue of quantifying scaling that justifies computer science as a “science”, as opposed to yet another engineering field.

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 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. The student can combine theory with information internetworking to enhance and quantify the performance of networks or databases or pursue security and cryptography, or with platforms to design programming languages or build provably efficient systems and software, or with computational modeling to solve, with proven rigor, a wide range of real-world large scale problems, or with intelligence to naturally address the modeling and algorithmic issues of artificial intelligence, or with devices to provide algorithms for robotics, or with people to have a unique quantitative perspective of dynamic networks of on-line communities, or with media. A student who pursues the theory thread at Georgia Tech is also an excellent candidate for a Ph.D. in theoretical computer science.

Resources and Role Models

• Theory at Georgia Tech
  

• Algorithms, Combinatorics and Optimization (ACO) Program at Georgia Tech
• Algorithms & Randomness Center and ThinkTank (ARC ThinkTank) at Georgia Tech

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

Required Courses

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

Fundamentals in Programming

• CS1171 Introductory Computing in Matlab, 1
• CS1301 Introduction to Computing and Programming, 3
• CS1331 Introduction to Object-Oriented Programming, 3
• CS1332 Data Structures and Algorithms, 3
• CS2110 Computing Organization and Programming, 4
• CS2340 Objects and Design, 3

Algorithms and Complexity

• CS1050 Understanding and Constructing Proofs, 3
• CS3511 Design and Analysis of Algorithms, Honors, 3

Pick 1 of Computational Complexity:

• CS3240 Languages and Computation, 3
• CS4510 Automata and Complexity Theory, 3

Mathematics

• Pick 1 of Mathematics related to Computer Science
• MATH2406 Abstract Vector Spaces, 3 (Requires MATH1502 or MATH1512)
• MATH4032 Combinatorial Analysis, 3 (Requires MATH3012)

Computer Science Applications involving Algorithms and Complexity

Pick 1 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
• CSE4140 Computational Science and Engineering Algorithms, 3
• CSE4330 Modeling and Simulation: Fundamentals and Implementation, 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
• CS4510 Automata and Complexity Theory, 3
• CS4540 Advanced Algorithms, 3 (Prereq CS3510 or 3511)
• CS6520 Computational Complexity, 3 (Prereq CS3510 or 3511)
• CS4520 Approximation Algorithms, 3 (Prereq CS3510 or 3511)
• CS4530 Randomized Algorithms, 3 (Prereq CS3510 or 3511)
• Mathematics with Computer Science Applications
• MATH2406 Abstract Vector Spaces, 3 (Requires MATH1502 or MATH1512)
• 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)
• MATH4260 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
• 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)

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
• CSE4140 Computational Science and Engineering Algorithms, 3
• CSE4330 Modeling and Simulation: Fundamentals and Implementation, 3

Computational Methods in the Sciences

• BIOL2400 Mathematical Models in Biology, 3 (Requires MATH1502 or MATH1512)
• BIOL4755 Mathematical Biology, 3 (Requires CS1301 and BIOL3332 and MATH1502)
• PHYS3151 Mathematical Physics, 3 (Requires MATH2403 and PHYS2212)
• PHYS3266 Computational Physics, 4 (Requires PHYS2212)
• ISYE4231 Optimization (Requires CS1322 and Math 2602)
• MGT3076 Investments, 3 (Requires MGT3062)
• MGT3078 Finance and Investments, 3
• MGT3084 Derivative Securities, 3 (Requires MGT3062 or MGT3078)
• ECON3110 Advanced Microeconomic Analysis, 3 (Requires ECON2100 or ECON2105 and ECON2106)
• ECON3120 Advanced Macroeconomic Analysis, 3 (Requires ECON2100 or ECON2105 and ECON2106)