writing

TOC SummaryCompact reference of the definitions, theorems, and proof recipes of Theory of Computation: regular languages and the pumping lemma, Turing machines, decidability and recognizability, reductions, and the P, NP, and NP-completeness landscape.Theory of Computation: Lecture 8Polynomial-time mapping reductions, NP-completeness, Cook-Levin, the 3SAT reduction, and the SAT-to-INDSET construction.Theory of Computation: Lecture 9NP-completeness reduction chains for CLIQUE, VERTEX COVER, SET COVER, and SUBSET-SUM, with graph complements and pseudo-polynomial subset-sum.Theory of Computation: Lecture 7Worst-case time complexity, asymptotic notation, TIME and P, polynomial-time verification, NP, nondeterministic polynomial time, and the P versus NP question.Theory of Computation: Lecture 6Computable functions, mapping reductions, reduction-based undecidability proofs, ATM reductions to HALT and REG_TM, and unrecognizability via EQ_TM.Data Intensive Systems: Lecture 12Dynamic databases and phantom reads, predicate and index locking, SQL isolation levels, replication tradeoffs, CAP and PACELC, quorum tuning, Dynamo-style eventual consistency, and causal consistency.Data Intensive Systems: Lecture 11Concurrency control through conflict serializability, precedence graphs, two-phase locking, strict 2PL, deadlocks, prevention schemes, and multi-granularity locks.Data Intensive Systems: Lecture 10Transaction management through ACID, write-ahead logging, rollback, isolation, schedules, conflicts, and crash recovery.Data Intensive Systems: Lecture 9Query optimization as cost-based search: query transformations, catalog statistics, cardinality estimation, access-path costing, join-order enumeration, and the System R strategy.Theory of Computation: Lecture 5Encoded decision problems, decidability of DFA emptiness and equivalence, diagonalization, HALT and ATM, and the boundary between decidable, recognizable, and unrecognizable languages.Theory of Computation: Lecture 4Turing machines, configurations, recognizable and decidable languages, basic TM algorithm design, unary powers of two, and the Church-Turing thesis.Data Intensive Systems: Lecture 1Why DBMSs exist and what they guarantee, schemas and data independence, the layered DBMS architecture, and conceptual design with the ER model: entities, relationships, constraints, weak entities, ISA hierarchies, and aggregation.Data Intensive Systems: Lecture 2The relational model and its algebra: tuples and instances, the key hierarchy, integrity constraints, SQL basics, the five basic operators, compound operators including join and division, and the query trees an optimizer rewrites.Data Intensive Systems: Lecture 3Storage and access: files, pages, and records, page and record layouts, row vs column stores, file organizations and their cost, indexing (dense, sparse, clustered, secondary, multilevel, composite), and index selection.Data Intensive Systems: Lecture 4The memory hierarchy and storage hardware: disk geometry and access time, flash and the FTL, RAID levels, disk space management, the buffer pool and page table, and replacement policies including Clock, LRU-K/2Q, and sequential flooding.Data Intensive Systems: Lecture 5B+ trees in depth: node structure and fan-out, search, insertion with leaf and internal splits, deletion with redistribution and merging, range scans over clustered vs unclustered data, and latch crabbing.Data Intensive Systems: Lecture 6Hashing and sorting for data systems: static and dynamic hashing (chained, extendible, linear), open addressing with linear probing, and external merge sort.Data Intensive Systems: Lecture 7Query processing with relational operators: physical plans, iterator and materialization models, access paths, selections, projections, and join algorithm costs.Data Intensive Systems: Lecture 8Selectivity estimation and CNF in practice, then the join algorithms: index nested loops, Grace and hybrid hash join, sort-merge join, general join conditions, set operations, and aggregation.Data Intensive Systems: SQLSQL as a query language: vocabulary, single- and multi-table queries mapped onto relational algebra, the conceptual evaluation order, aggregation, grouping, and HAVING.Theory of Computation: Lecture 1Strings and languages, deterministic finite automata, state meanings, the state-characterization recipe for correctness proofs, and the first closure constructions.Theory of Computation: Lecture 2Nondeterminism, NFAs and their acceptance, the subset construction with its equivalence proof, epsilon closure, and closure under concatenation.Theory of Computation: Lecture 3Non-regular languages, the pigeonhole argument, the pumping lemma as an adversary game, closure-based reductions, and a regular surprise.