P=NP

Regular Languages

Pumping Lemma

Pumping lemma for context-free languages

Undecidability

Rice’s Theorem

Turing Reducibility

Polynomial Time

Cook-Levin Theorem

Space Complexity

Regular Operations

Push-Down Automata

Chomsky Normal Form

Mapping Reducibilities

Fixed-point theorem

Savitch's Theorem

Kolmogorov complexity

Non-determinism

Minimizing DFA

Equivalence of PDAs and CFGs

Reductions

Recursion theorem

The Arithmetic Hierarchy

Non-Deterministic Turning Machines

Karp

Polynomial identity testing

Deterministic Finite Automata

Regular Expressions

Context-Free Grammars

Turing Machines

Post Correspondence Problem

Oracle Turing Machines

Time Complexity

NP-completeness

PSPACE-Completeness

15-453 - Formal Languages, Automata, and Computability Carnegie Mellon University Spring 2015 A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.  This course provides an introduction to formal languages, automata, computability, and complexity. The course consists of a traditional lecture component supported by weekly homework assignments and quizzes and a course project. There are two midterms and a final examination.

### Topics

- **Automata and Languages**: finite automata, regular languages, pushdown automata, context-free languages, pumping lemmas.
- **Computability Theory**: Turing Machines, decidability, reducibility, the arithmetic hierarchy the recursion theorem, the Post correspondence problem.
- **Complexity Theory**: time complexity, classes P and NP, NP-completeness, space complexity, PSPACE, PSPACE-completeness, the polynomial hierarchy, randomized complexity, classes RP and BPP.  15-251 or 21-228. Textbook: Introduction to the Theory of Computation (3rd Ed.) by Michael Sipser, 2012.
Errata for 3rd Edition: http://math.mit.edu/~sipser/itoc-derrs3.1.html

15-453 - Formal Languages, Automata, and Computability

Theoretical Computer Science

Java (programming language)

Class (computer programming)

Software testing

References

Recursion (computer science)

List (abstract data type)

SLLists

Nested Classes

Debugging

Array (data structure)

Array Resizing

Inheritance (object-oriented programming)

Extends

Higher-order function (HOF)

Exception handling

Object Methods

Disjoint Sets

Set (abstract data type)

Binary Search Tree (BST)

Red Black Trees

Tree traversal

Multi-Dimensional Data

Prefix Operations and Tries

Reductions and Decomposition

Quick Sort

Algorithmic Bounds

Data structure

Scope

Linked list

Shortest paths

Heap (data structure)

Sentinel Nodes

DLLists

ALists

SLists

Implements

Casting

Subtype Polymorphism

Iterators

Asymptotics

Abstract Data Type (ADT)

Map (higher-order function)

B-tree

Hashing

Priority queue (PQ)

Graph traversal

Range Searching

Software Engineering

Sorting algorithm

Radix Sorts

Compression

Static

Minimum Spanning Tree (MST)

CS 61B: Data Structures UC Berkeley Fall 2022 CS 61B focuses on software efficiency from design and runtime perspectives. It covers object-oriented programming with Java, teaching data structures and various programming concepts. The course promotes hands-on learning with optional assignments. The CS 61 series is an introduction to Computer Science, with particular emphasis on software and machines from a programmer’s point of view. CS 61A covered high-level approaches to problem-solving, providing you with a variety of ways to organize solutions to programming problems as compositions of functions, collections of objects, or sets of rules. In CS 61B, we move to a somewhat more detailed (and to some extent, more basic) level of programming by focusing particularly on the efficiency of writing programs (design) and running programs (runtime).  This class assumes you have taken CS 61A, CS 88, or E 7, or have equivalent background to a student who has taken one of these courses. The course is largely built upon the assumption that you have taken CS 61A. CS 88 and E7 students may find the beginning of the course to be a bit scarier, particularly when it comes to object oriented programming. We assume you are coming in with zero Java experience, but we will move through basic Java syntax very quickly.

We recommend all students to complete the [optional introductory assignment](https://fa22.datastructur.es/materials/hw/hw0/) by the beginning of the semester to get comfortable with Java and practice some of the programming skills expected by this class.

If you already have Java experience, great! We hope that you’ll help out your fellow students in discussion, lab, and on our class forum, particularly in the opening weeks when everyone is catching up on Java. **There is no required textbook for the class.**

There is an online textbook written by myself and a large team of former TAs. It can be found at https://joshhug.gitbooks.io/hug61b. If you find these notes insufficient, you might consider consulting [Paul Hilfinger’s (free) Java Reference](http://www-inst.eecs.berkeley.edu/~cs61b/fa14/book1/java.pdf) or [Head First Java, 2nd Edition by Sierra and Bates (O’Reilly, 2005)](https://www.google.com/search?q=head+first+java). These are not required for the course. The **optional** textbook for the weeks 5-14 of the course is Algorithms, 4th Edition by Wayne and Sedgewick.

The official description of the Java core language is available online in [The Java Language Specification](https://docs.oracle.com/javase/specs/jls/se17/html/index.html) (Java SE 17 Edition) by James Gosling, Bill Joy, Guy Steele, Gilad Bracha, Alex Buckley, Daniel Smith, and Gavin Bierman. It’s extremely thorough and precise, at the expense of being quite dense and technical. You will find the official [Java 17 documentation](ttps://docs.oracle.com/en/java/javase/17/docs/api/index.html) to be useful as well

CS 61B: Data Structures

Data Structures and Algorithms

P versus NP problem

P=NP

2 courses cover this concept

15-453 - Formal Languages, Automata, and Computability

CS 61B: Data Structures