Regular expressions are a computational language for matching text. They are extremely useful as computer scientists, giving rise to scanning and matching algorithms, as well as forming the basis for powerful search and replace features in many programming tools.
Context-Free Grammars are a language for describing other languages. They are used to define programming languages - you can read the grammars for popular languages online.
They are also used to build programming languages including compilers, and interpreters. This also includes tools that parse code such as documentation generators, IDEs etc.
This is also useful if you need to parse complex data formats such as XML or JSON.
Computability theory has to deal with what problems can and cannot be solved by computer systems.
Some problems are simply not solvable no matter how powerful a computer we have.
Complexity theory is the study of the efficiency of algorithms as the size of the input grows. We will look at different complexity classes of problems, those that can be solved in linear time, polynomial time, exponential time etc.
You will learn which problems have fast, practical solutions and which do not.
Complexity theory is also important for computer security where we don't want solutions that are easily computable.
This class builds on discrete math, and we will use all of the following concepts heavily:
You can refer to Stephen's Discrete Math course if you need a refresher on these topics!
Copyright © 2024 Ian Finlayson | Licensed under a Creative Commons BY-NC-SA 4.0 License.