Tài liệu miễn phí Toán học
Download Tài liệu học tập miễn phí Toán học
Theory of Computation: Lecture 11
Theory of Computation: Lecture 11. The main topics covered in this lesson include: undecidability of the halting problem; Russell’s paradox; reducibility; undecidable problems; linear bounded automata; acceptance problem for TMs; emptiness problem for TMs;...
4/8/2023 4:22:21 PM +00:00
Theory of Computation: Lecture 10
Theory of Computation: Lecture 10. The main topics covered in this lesson include: linear bounded automata; acceptance problem for LBAs; emptiness problem for LBAs; computation histories; emptiness problem for CFGs; an undecidable problem for CFGs; post correspondence problem;...
4/8/2023 4:22:13 PM +00:00
Theory of Computation: Lecture 9
Theory of Computation: Lecture 9. The main topics covered in this lesson include: Halting problem; undecidability of the Halting problem; diagonalization; Co-Turing recognizability; the Halting problem is not co-Turing recognizable;...
4/8/2023 4:22:06 PM +00:00
Theory of Computation: Lecture 8
Theory of Computation: Lecture 8. The main topics covered in this lesson include: the Halting problem; universal Turing machine; undecidability of the halting problem; diagonalization; galilean paradox; Hilbert hotel; countable sets; cantor diagonalization;...
4/8/2023 4:21:56 PM +00:00
Theory of Computation: Lecture 6
Theory of Computation: Lecture 6. The main topics covered in this lesson include: prove the equivalence of enumerators and TMs; dovetailing; definition of algorithm; the Church-Turing thesis; encodings; Hilbert’s 10th problem; Matijasevic’s theorem;...
4/8/2023 4:21:44 PM +00:00
Theory of Computation: Lecture 5
Theory of Computation: Lecture 5. The main topics covered in this lesson include: variants of Turing machines; k-tape TMs; show that k-tape TMs have the same power as 1-tape TMs; study enumerators; prove equivalence of enumerators and TMs; dovetailing;...
4/8/2023 4:21:37 PM +00:00
Theory of Computation: Lecture 4
Theory of Computation: Lecture 4. The main topics covered in this lesson include: quickly recall the definition of a Turing machine; look at some more examples of Turing machines; define the concept of a configuration; define what the language accepted by a Turing machines;...
4/8/2023 4:21:30 PM +00:00
Theory of Computation: Lecture 3
Theory of Computation: Lecture 3. The main topics covered in this lesson include: quickly recall the definition of a Turing machine; look at some more examples of Turing machines; define the concept of a configuration; define what the language accepted by a Turing machines;...
4/8/2023 4:21:19 PM +00:00
Theory of Computation: Lecture 2
Theory of Computation: Lecture 2. The main topics covered in this lesson include: recall some basic definitions from automata theory; alphabet, strings and languages; define a turing machine; look at simple examples of turing machines;...
4/8/2023 4:21:11 PM +00:00
Theory of Computation: Lecture 1
Theory of Computation: Lecture 1. The main topics covered in this lesson include: the story of computation; earliest models of computation; earliest algorithms; theory of computation; computability and logic; complexity theory; turing machines and algorithms;...
4/8/2023 4:21:04 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 45: Review lecture
Advanced Algorithms Analysis and Design - Lecture 45: Review lecture. In this lecture, we will review the knowledge about: model of computation; mathematical tools; asymptotic notations; dynamic programming; chain-matrix multiplication; Greedy algorithms; Graph theoretic algorithms; number theoretic algorithms;...
4/8/2023 4:02:14 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 44: NP completeness
Advanced Algorithms Analysis and Design - Lecture 44: NP completeness. In this lecture we will cover the following: NP completeness; polynomial time algorithms; decision and optimization problems; nondeterministic problems; nondeterministic algorithm; boolean combinational circuit; NP-completeness proof basis;...
4/8/2023 4:02:03 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 43: Polynomials and fast fourier transform
Advanced Algorithms Analysis and Design - Lecture 43: Polynomials and fast fourier transform. In this lecture we will cover the following: the coefficient representation; point value presentation; discrete fourier transform; complex root of unity; FFT recursive algorithm;...
4/8/2023 4:01:57 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 42: String matching
Advanced Algorithms Analysis and Design - Lecture 42: String matching. In this lecture we will cover the following: string matching problem; naive string matching algorithm; the Rabin-Karp algorithm; Horner’s rule; sequence of steps designing algorithm; string matching with finite automata;...
4/8/2023 4:01:44 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 41: RSA cryptosystem & String matching
Advanced Algorithms Analysis and Design - Lecture 41: RSA cryptosystem & String matching. In this lecture we will cover the following: Fermat theorem; Euler’s theorem and generalization of Fermat’s; RSA cryptosystem; string matching; string matching problem; naive string matching algorithm;...
4/8/2023 4:01:35 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 40: Chinese remainder theorem & RSA cryptosystem
Advanced Algorithms Analysis and Design - Lecture 40: Chinese remainder theorem & RSA cryptosystem. In this lecture we will cover the following: modular arithmetic; solving modular linear equations; Chinese remainder theorem; unique representation of a number by CRT;...
4/8/2023 4:01:28 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 39: Number theoretic algorithms (Theorems and algorithms)
Advanced Algorithms Analysis and Design - Lecture 39: Number theoretic algorithms (Theorems and algorithms). In this lecture we will cover the following: some more proofs; GCD as a linear combination; finding GCD, a recursive theorem; Euclid’s algorithm; extended Euclid’s algorithm; time complexity of Euclid’s algorithm;...
4/8/2023 4:01:17 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 38: Number theoretic algorithms (Definitions and some important results)
Advanced Algorithms Analysis and Design - Lecture 38: Number theoretic algorithms (Definitions and some important results). In this lecture we will cover the following: applications of number theory; divisibility; numbers; prime numbers; relatively prime numbers; GCD; partitioning of Integers; congruency classes; proofs of some results;...
4/8/2023 4:01:10 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 37: The Floyd-Warshall algorithm and Johnson’s algorithm
Advanced Algorithms Analysis and Design - Lecture 37: The Floyd-Warshall algorithm and Johnson’s algorithm. In this lecture we will cover the following: intermediate vertices; the Floyd-Warshall algorithm; transitive closure; Johnson’s algorithm; producing nonnegative weights by re-weighting;...
4/8/2023 4:01:04 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 36: All pairs shortest paths
Advanced Algorithms Analysis and Design - Lecture 36: All pairs shortest paths. In this lecture we will cover the following: all pairs shortest paths; algorithms - matrix multiplication, the floyd-warshall algorithm; time complexity;...
4/8/2023 4:00:57 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 35: Dijkstra’s algorithm
Advanced Algorithms Analysis and Design - Lecture 35: Dijkstra’s algorithm. In this lecture we will cover the following: problem statement; mathematical statement of problem; edge relaxation, Dijkstra’s algorithm; fibonacci heap; convergence property; predecessor subgraph property;...
4/8/2023 4:00:50 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 34: Proof: Bellman-Ford algorithm and Shortest paths in Directed acyclic graphs
Advanced Algorithms Analysis and Design - Lecture 34: Proof: Bellman-Ford algorithm and Shortest paths in Directed acyclic graphs. In this lecture we will cover the following: Bellman-Ford algorithm (analysis, proof); shortest path in directed acyclic graphs (assumptions, algorithm, analysis, proof of correctness);...
4/8/2023 4:00:44 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 33: Single-source shortest path
Advanced Algorithms Analysis and Design - Lecture 33: Single-source shortest path. In this lecture we will cover the following: road map problem; linking road map problem with graph theory; paths and shortest paths; cycles and their role in finding shortest paths; the Bellman-Ford algorithm;...
4/8/2023 4:00:35 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 32: Minimal spanning tree problem
Advanced Algorithms Analysis and Design - Lecture 32: Minimal spanning tree problem. In this lecture we will cover the following: importance of minimal spanning trees (MST); MST problem (generic solution, proofs of correctness); Kruskal’s algorithm; Prim’s algorithm;...
4/8/2023 4:00:29 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 31: Backtracking and branch & bound algorithms
Advanced Algorithms Analysis and Design - Lecture 31: Backtracking and branch & bound algorithms. In this lecture we will cover the following: component graph; vertices to SCC; correctness of SCC algorithm; branch and bound technique; assigning task to agents;...
4/8/2023 4:00:22 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 30: Proof (white path theorem) & Applications of depth first search
Advanced Algorithms Analysis and Design - Lecture 30: Proof (white path theorem) & Applications of depth first search. In this lecture we will cover the following: algorithm depth first search; classification of edges; white-path theorem; topological sort; strongly connected components;...
4/8/2023 4:00:16 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 29: Proof (Breadth first search algorithm) & Depth first search
Advanced Algorithms Analysis and Design - Lecture 29: Proof (Breadth first search algorithm) & Depth first search. In this lecture we will cover the following: depth first search techniques is discussed; algorithms is designed; correctness of depth first search is given; topological sort and its benefits; computing strongly connected components; applications and conclusion;...
4/8/2023 4:00:09 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 28: Breadth first search
Advanced Algorithms Analysis and Design - Lecture 28: Breadth first search. In this lecture we will cover the following: representation of graphs; breadth first search; supporting lemmas in the proof; proof of correctness; shortest paths, for un-weighted edges, based on breadth first search;...
4/8/2023 4:00:03 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 27: Huffman coding problem and graph theory
Advanced Algorithms Analysis and Design - Lecture 27: Huffman coding problem and graph theory. In this lecture we will cover the following: constructing a huffman codes; optimal substructure property; road trip problem; graph theoretic concepts; complete bipartite graph; isomorphic invariant;...
4/8/2023 3:59:56 PM +00:00
Advanced Algorithms Analysis and Design - Lecture 26: Huffman coding
Advanced Algorithms Analysis and Design - Lecture 26: Huffman coding. In this lecture we will cover the following: huffman problem; problem analysis; algorithm of huffman coding problem; time complexity; road trip problem; analysis and greedy algorithm;...
4/8/2023 3:59:50 PM +00:00