Untitled Notes

Theoretical Computer Science (CS) focuses on understanding the fundamental capabilities and limitations of computers.
Exploration covers areas such as mathematical logic, automata, computability, and complexity.
The course aims to provide foundational knowledge essential for further exploration and practical applications in CS.

Aim: To provide a robust background in theoretical computer science.
Topics Covered:
- Mathematical logic
- Automata theory
- Computability
- Complexity theory
Course Outcomes:
- Basics of logical formalisms
- Principles of computation
- Application of theoretical concepts in practical scenarios.

Midterm Grade Structure:
- Total: 60 points
- Midterm Exam: 30 points
- Home Work: 10 points
- Course Project: 15 points
- Presentation: 5 points
Final Exam: 40 points
Passing Regulations:
- Minimum Grade (MG) must be at least 27 points
- Midterm Exam: Minimum 13 points
- Home Work: Minimum 5 points
- Project: Minimum 7 points
- Presentation: Minimum 2 points
Final Exam Requirement: At least 17 points in the final exam with total MG + Final Exam (FE) must be ≥ 51 to pass the course.

Sipser, M. (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.
Selected chapters from various other texts.

Main Question: What are the fundamental capabilities and limitations of computers?
- Historical context dating back to the 1930s when mathematical logicians explored computation.
Core Subfields:
- Automata Theory: Focuses on mathematical models of computation.
- Computability Theory: Investigates problems that cannot be solved by computers.
- Complexity Theory: Classifies computational problems based on difficulty.

Deals with definitions and properties of computational models.
Examples:
- Finite Automaton: Used in text processing, compilers, hardware design.
- Context-Free Grammar: Utilized in programming languages and AI.

Influenced by the works of Kurt Gödel, Alan Turing, and Alonzo Church in the early 20th century.
Highlights that certain problems, like determining the truth of mathematical statements, cannot be executed by any computer algorithm.
Introduces concepts that are foundational to complexity theory.
Distinction between computability (solvable vs unsolvable problems) and complexity (classification of problems as easy or hard).

Varieties of Computer Problems: Easy vs. hard problems (e.g., sorting vs. scheduling).
Central Inquiry: Identification of computational difficulty across problems.
Strategies for Addressing Hard Problems:
- Understanding difficulties and altering the problem to make it easier.
- Accepting less than perfect solutions or approximations.
- Exploring alternative computation types to optimize processes, essential in fields like cryptography.

A set is a collection of objects known as elements or members.
- Denoted by symbols like A, B, C.
Set membership: Examples: 7 ∈ {7, 21, 57}, 9 ∉ {7, 21, 57}.
Subset Notations:
- A is a subset of B: $A ext{ is a subset of } B ext{ if } A au \forall a ext{ such that } a ext{ is in } A ext{ also } a ext{ is in } B$
- Proper subset: $A ext{ is a proper subset of } B ext{ notation } A ext{ ⊂ B if } A <br />\neq B$

A multiset considers the frequency of its members.
Example: {7} is equal to {7, 7} in a set, but not in a multiset.
Venn diagrams: A tool to visualize sets - e.g., natural numbers N = {1, 2, 3,…}, integers Z = {…, -2, -1, 0, 1, 2,…}.

Union: $(A \bigcup B) = ext{ the set of all elements that are in A or B.}$
Intersection: $(A \bigcap B) = ext{ the set of elements that are in both A and B.}$
Complement: $<br />\neg A = ext{ all elements not in set A.}$
Subtraction: $(B - A) = ext{ elements in B not in A.}$
Cartesian Product: $(A imes B) = ext{ set of ordered pairs }(a, b) ext{ where } a ext{ is in } A, b ext{ is in } B.$
- Example: $A = ext{{1, 2}} ext{ and } B = ext{{x, y,z}}, A imes B = ext{{(1, x), (1, y), (1,z), (2, x), (2, y), (2,z)}}$ .

A sequence is an ordered multiset, commonly referred to in computer science.
A sequence with k elements is called a k-tuple.
For example: (7, 21, 57) differs from (57, 7, 21).

A function establishes an input-output relationship, denoted as $f(a)=b$ .
Defined as a mapping: if $f(a)=b$ , we state that f maps a to b.
Domain: set of inputs where defined; Range: outputs produced by the function.
Example: f: Z
ightarrow N: |f(x)|= x ext{ absolute value}.

A predicate is a function with TRUE or FALSE range. Example: even(4)=TRUE, even(5)=FALSE.
Relation: a property between n-tuples; can be nullary, unary, binary, etc.
Example of binary relation: $R(a,b)$ can be denoted as $a R b$ (like ≤).

An undirected graph consists of vertices (nodes) connected by edges.
The degree of a node is the number of edges connected to it.
Described by sets as $G = (V, E)$ where V = vertices set, E = edges set.
- Example: Graph description with nodes and edges.
Directed graph: utilizes arrows instead of lines, with defined in-degrees and out-degrees for nodes.

Strings: sequences of symbols from an alphabet.
The alphabet: any non-empty finite set (e.g., $Σ_1 = {0, 1}, Σ_2 = {a,…,z}$ ).
Concatenation: combining strings to form a new string.
Lexicographical order closely resembles dictionary order.

Definition: A precise description of mathematical objects and notions.
Theorem: A verified statement within mathematics.
Proof: A logical argument establishing the truth of the theorem.
Strategies for Finding Proofs:
- Understand notation and rewrite in simpler terms.
- Explore examples and identify potential counterexamples.
- Employ methods like proof by construction, contradiction, or induction.

The induction principle states properties true of a base case extend to all N if preserved over successors.
Structural induction applies to inductively defined objects such as lists or trees.
Well-Founded Induction affirms if a property holds for predecessors in a well-founded relation, it holds universally.

Engage with practical and theoretical questions based on course materials to foster a deeper understanding of the topics discussed.