What is Theoretical Computer Science (TCS)?

Usually, computer science seems like a practical field that involves studying, building, and working closely with computers. However, a subclass of this discipline also centers on the mathematical factors of the same. This is called theoretical computer science, and its focal point differentiates it from other branches of computer science: the rigorous mathematical approach it takes. This discipline falls under the umbrella of discrete mathematics, which is the study of countable or discontinuous mathematical structures. 

Origins of TCS

Gödel's incompleteness theorems were released publicly in the year 1931. They introduced some new implications to the field of math, both logically and philosophically. These theorems question the restrictions of the provability of mathematical statements. Gödel's theorems have greatly impacted the field of theoretical computer science, molding it into a field of interdisciplinary and mathematical issues in need of solutions.

Topics within TCS

The field of theoretical computer science is vast and contains many sub-disciplines.

Some of these sub-fields are: 

Algorithms: 

An algorithm is used to declare the steps to be followed to reach a certain result. It can be used to compute or process important data. An algorithm starts at an initial step and slowly proceeds through a sequence of precise stages, taking in inputs along the way. Finally, it reaches the last stage and derives an output. 

Algorithms can be both deterministic and randomized. A deterministic algorithm will always produce the same output when a fixed input is fed to it. On the other hand, random inputs and random results can be expected from non-deterministic algorithms. 

Common programming languages also have built-in algorithms that perform a certain function, like sorting, searching, and so on. However, to solve specific problems, programming languages are also used to write algorithms from scratch. One such basic algorithm that coders learn to implement in programming languages is Euclid's algorithm to find the Greatest Common Denominator (GCD) of any two numbers. The recursive form of the algorithm is as follows: 

GCD(a, b){ 

1. If a = 0 then return b 

2. Else return GCD(b % a, a); 

} 

An interesting application of algorithms is algorithmic game theory. In addition to the common prerequisites of conventional algorithm design, this branch combines game theory with computer science to make algorithms that solve issues arising in competitive environments (such as commerce). 

Data Structures

There are plenty of ways in which data can be structured. Data structures aim to provide the most efficient arrangement of data in order to access and apply it to a wide range of applications. A good data structure is necessary for designing useful algorithms. Programming languages utilize data structures heavily as it is the best way to organize data used by a program.

An application of data structures can be seen in the usage of indexes in database systems. Data structures often use the principles of graph theory to organize data effectively. 

Information Theory

Founded by Claude E. Shannon, information theory combines three fields: computer science, electrical engineering, and applied mathematics. It is prevalent in the field of signal processing. It can also be found in other domains like natural language processing and neuroscience. 

An understandable application of this field is data compression, such as lossy compressions like MP3 and JPEG, to lossless compressions like GIF and PNG.

Automata Theory

Automata theory is the concept of understanding theoretical or abstract machines that frame a model of computation. Intersecting the field of computer science and mathematics (discrete math), automata theory helps study virtual machines which help analyze the flow of processing inputs and outputs. 

Coding Theory

Coding theory relies heavily on domains like information theory, mathematics, and computer science. Codes are an alternative way to represent data. Coding theory tries to understand the characteristics of various codes and the applications they can help with. Mainly, codes are used in communication channels, where a lot of data is passed back and forth. To ensure the reliability of transmitted data, different kinds of error correction and redundancy removal techniques are practiced. 

Cryptography

Ensuring the reliability of communication is at the core of the study of cryptography. Combining the fields of computer science and mathematics, cryptography delves into the various factors affecting the integrity, authenticity, and confidentiality of data. Therefore, a big part of this field is devising and understanding security protocols and algorithms that are difficult to crack, thus restricting entry into crucial systems. 

There are many real-world applications of cryptography such as passwords, e-commerce, and ATMs. 

Machine Learning

Machine learning is a field that merges computer science and statistics to help conceive algorithms such that they comprehend the data fed to them and respond accordingly. A data model is built using the inputs to the algorithm, which is then used to train the algorithm into producing predictive results rather than just following straightforward instructions. 

For instance, in the case of predicting the weather, there is no way a fixed algorithm with clearly defined instructions would be practical. Instead, an algorithm that trains from a historical dataset and results in prediction and forecasting is employed. 

Neural networks are a type of machine learning algorithm modeled after the neurons in the human brain. They work just like a series of neurons; a neuron receives input and feeds an output to another neuron. The outcome of a neural network is often predictive after data processing. 

Quantum Computing

It studies the physics of data. Using the principles of physics like entanglement and super positioning, quantum computing attempts to process data. Therefore, instead of representing data in the form of bits, quantum computing postulates the usage of “Qubits”, which can take on superposition states. This field of computing research is still nascent, although theoretical models like the quantum Turing machine have been proposed. Practical demonstrations have also been done on a very small number of “Qubits”. 

Computational Number Theory

A mathematical field of study called number theory solely focuses on the study of integer values. Combining the field of computer science with this particular branch of mathematics is called computational number theory. Therefore, crafting algorithms to solve number theoretic problems is the focus of this domain. Integer factorization (breaking big numbers into smaller units) is a typical application of the field. 

Context and Applications  

This topic is significant in the professional exams for both undergraduate and graduate courses, especially for   

• Bachelors in Computer Science
• Masters in Computer Science