Other links:

Other links:

Blockchain and Cryptocurrencies

It is a CS elective course. The subject - theory of computation, comprises the fundamental mathematical properties of computer hardware, software, and certain applications thereof. In studying this subject, we seek to determine what can and cannot be computed, how quickly, with how much memory, and on which type of computational model; to see a new, simpler, and more elegant side of computers, which we normally consider to be complicated machines; to learn conceptual tools that practitioner use in computer engineering. The main topics/subtopics covered will be:

  • Automata and Languages:
  • Regular Languages: DFA, NFA, Regular Expressions
  • Context-free Languages: Context-free grammars, PDA, Deterministic Context-free grammars
  • Computability Theory:
  • The Church-Turing Thesis: Turing Machines, Algorithm definition
  • Decidability: Decidable languages, Un-decidability
  • Reducibility: Mapping Reducibility
  • Complexity Theory:
  • Time Complexity: The class P, class NP, NP-completeness
  • Intractability

Study at Ashoka

Study at Ashoka