New Computer Science Lectures
Hello everyone! This month I've found a bunch of new computer science lectures. They include: Geometric folding algorithms, Advanced algorithms and data structures, Design and analysis of algorithms, Practical UNIX, and Compiler techniques. Enjoy!
Geometric Folding Algorithms: Linkages, Origami, Polyhedra (MIT, 6.849, Erik Demaine)
Geometric Folding Algorithms Course Website
Geometric Folding Algorithms Video Lectures
Course description:
Whenever you have a physical object to be reconfigured, geometric folding often comes into play. This class is about algorithms for analyzing and designing such folds. Motivating applications include: automated design of new and complex origami, transforming robots by self-folding sheets or chains, how to fold robotic arms without collision, how to bend sheet metal into desired 3D shapes, understanding how proteins fold. Major progress have been made in recent years in many of these directions, thanks to a growing understanding of the mathematics and algorithms underlying folding. Nonetheless, many fundamental questions remain tantalizingly unsolved. This class covers the state-of-the-art in folding research, including a variety of open problems, enabling the student to do research and advance the field.
Course topics:
Origami intro: Piece of paper, crease pattern, mountain-valley assignment. Simple folds: Folding any shape (silhouette or gift wrapping), 1D flat-foldability characterization, 2D map-folding algorithm. Single-vertex crease patterns: Characterizations of flat-foldable crease patterns and mountain-valley patterns, combinatorics of the latter, local flat foldability is easy. Tree method of origami design: Introduction, uniaxial base, demo. Efficient origami design: Tree method, TreeMaker, uniaxial base, active path, rabbit-ear molecule, universal molecule, Margulis Napkin Problem; cube folding, checkerboard folding; Origamizer, watertight, tuck proxy. Universal hinge patterns: box pleating, polycubes; orthogonal maze folding. NP-hardness: introduction, reductions; simple foldability; crease pattern flat foldability; disk packing (for tree method). Artistic origami design: sampling of representational origami art; tree method and its use (guest lecture by Jason Ku). Fold and one cut: history, straight-skeleton method, disk-packing method, simple folds, higher dimensions, flattening polyhedra. Folding motions: folded states vs. motions; universal foldability of polygonal paper. Linkages to sign your name: graphs vs. linkages vs. configurations, configuration space; Kempe Universality Theorem, original proof, bug, corrections, generalizations and strengthenings. Rigidity theory: Rigidity, generic rigidity, minimal generic rigidity, Henneberg characterization, Laman characterization, polynomial-time algorithm, convex polyhedra. Rigidity theory: Infinitesimal rigidity, rigidity matrix. Tensegrity theory: tensegrities, equilibrium stress, duality, polyhedral lifting, Maxwell-Cremona Theorem. Locked linkages: Carpenter's Rule Theorem. Locked linkages: Algorithms for unfolding 2D chains, pseudotriangulation, energy; rigid folding of single-vertex origami; locked trees, infinitesimally locked linkages, Rules 1 and 2; locked 3D chains, knitting needles. Hinged dissections: Locked and unlocked chains of planar shapes, adorned chains, slender adornments, slender implies not locked, Kirszbaun's Theorem, locked triangles with apex angle > 90°; existence of hinged dissections, refinement. Polyhedron unfolding: Edge unfoldings, general unfoldings, big questions, curvature, general unfolding of convex polyhedra, source unfolding, star unfolding, edge-unfolding special convex polyhedra, fewest nets, edge-ununfoldable nonconvex polyhedra. Polyhedron unfolding: Vertex unfolding, facet paths, generally unfolding orthogonal polyhedra, grid unfolding, refinement, Manhattan towers, orthostacks, orthotubes, orthotrees. Polyhedron folding: Cauchy's Rigidity Theorem, Alexandrov's uniqueness of folding. Polyhedron folding: Decision problem, enumeration problem, combinatorial problem, nonconvex solution, convex polyhedral metrics, Alexandrov gluings, Alexandrov's Theorem, Bobenko-Izmestiev constructive proof, pseudopolynomial algorithm, ungluable polygons, perimeter halving, gluing tree, rolling belts. Polyhedron folding: Combinatorial type of gluing, exponential upper and lower bounds for combinatorially distinct gluings, polynomial upper bound for polygons of bounded sharpness, dynamic program for edge-to-edge gluing, including polynomial-time decision, exponential-time dynamic program for general gluing; case studies of Latin cross, equilateral triangle, and square. Polyhedron refolding: Dissection-like open problem, regular tetrahedron to box, Platonic solids to tetrahedra, box to box, polycubes, orthogonal unfoldings with nonorthogonal foldings. Smooth polyhedron folding: Smooth Alexandrov, D-forms, ribbon curves. Smooth polyhedron unfolding: Smooth prismatoids. Smooth origami: wrapping smooth surfaces with flat paper, Mozartkugel, contractive mapping, Burago-Zalgaller Theorem (crinkling/crumpling), stretched path, stretched wrapping, source wrapping, strip wrapping, petal wrapping, comb wrapping, Pareto curve. Protein folding: Fixed-angle linkages, tree, and chains; span; flattening; flat-state connectivity, disconnectivity of orthogonal partially rigid trees, connectivity of orthogonal open chains; locked fixed-angle chains; producible protein (fixed-angle) chains, ribosome, β-producible chains, helix-like canonical configuration, flat states are producible, producible states are connected. Protein folding: HP model of protein folding, NP-hardness and approximation, unique optimal foldings, protein design. Interlocked 3D chains: Lubiw's problem, unlocking 2-chains, unlocking two 3-chains and 2-chains, interlocking 3-chains, interlocking 3-chain with 4-chain, interlocking 4-chain with triangle, interlocking 3-chain with quadrangle, topological vs. geometric arguments, rigid and fixed-angle variations. Maekawa and Kawasaki's Theorems Revisited and Extended: Maekawa's Theorem, Kawasaki's Theorem, history (Justin, Huffman, Husimi), Robertson's 1977 paper, manifolds without boundary, strata, volumes, degree of map, higher dimensions, Justin's Theorem, Gauss-Bonnet Theorem, tessellations on a sphere (guest lecture by Thomas Hull). Flips and friends: Pockets, flips, “Erdős-Nagy Theorem”, false and correct proofs; flipturns; deflations; pops. 4D linkages: Chains, trees. Pleat folding: “Hyperbolic paraboloid”, circular pleat, self-folding origami, plastic deformation and elastic memory; triangulation, interval arithmetic; how paper folds between creases, ruled surfaces, torsal, straight creases stay straight, polygons stay flat; nonexistence. Inflation: Teabag problem, inflating polyhedra. Curved creases: Recreating David Huffman's curved-crease folding. Architectural Origami: Origamizer, Freeform Origami, Rigid Origami Simulator, cylindrical origami, thick origami (guest lecture by Tomohiro Tachi).
Advanced Data Structures (MIT, 6.851, Erik Demaine)
Advanced Data Structures Course Website
Advanced Data Structures Video Lectures
Course description:
Data structures play a central role in modern computer science. You interact with data structures even more often than with algorithms (think Google, your mail server, and even your network routers). In addition, data structures are essential building blocks in obtaining efficient algorithms. This course covers major results and current directions of research in data structures: TIME TRAVEL We can remember the past efficiently (a technique called persistence), but in general it's difficult to change the past and see the outcomes on the present (retroactivity). So alas, Back To The Future isn't really possible. GEOMETRY When data has more than one dimension (e.g. maps, database tables). DYNAMIC OPTIMALITY Is there one binary search tree that's as good as all others? We still don't know, but we're close. MEMORY HIERARCHY Real computers have multiple levels of caches. We can optimize the number of cache misses, often without even knowing the size of the cache. HASHING Hashing is the most used data structure in computer science. And it's still an active area of research. INTEGERS Logarithmic time is too easy. By careful analysis of the information you're dealing with, you can often reduce the operation times substantially, sometimes even to constant. We will also cover lower bounds that illustrate when this is not possible. DYNAMIC GRAPHS A network link went down, or you just added or deleted a friend in a social network. We can still maintain essential information about the connectivity as it changes. STRINGS Searching for phrases in giant text (think Google or DNA). SUCCINCT Most “linear size” data structures you know are much larger than they need to be, often by an order of magnitude. Some data structures require almost no space beyond the raw data but are still fast (think heaps, but much cooler).
Course topics:
Temporal: class overview, pointer machine, partial persistence, full persistence, confluent persistence, functional. Temporal: partial retroactivity, full retroactivity, nonoblivious retroactivity. Geometric: point location via persistence, dynamic via retroactive; orthogonal range queries, range trees, layered range trees, dynamizing augmentation via weight balance, fractional cascading. Geometric: O(log n) 3D orthogonal range searching via fractional cascading; kinetic data structures. Dynamic optimality: binary search trees, analytic bounds, splay trees, geometric view, greedy algorithm. Dynamic optimality: independent rectangle, Wilber, and Signed Greedy lower bounds; key-independent optimality; O(lg lg n)-competitive Tango trees. Memory hierarchy: models, cache-oblivious B-trees. Memory hierarchy: ordered-file maintenance, list labeling, order queries, cache-oblivious priority queues. Memory hierarchy: distribution sweeping via lazy funnelsort; cache-oblivious orthogonal 2D range searching: batched and online. Dictionaries: universal, k-wise independent, simple tabulation hashing; chaining, dynamic perfect hashing, linear probing, cuckoo hashing. Integer: models, predecessor problem, van Emde Boas, x-fast and y-fast trees, indirection. Integer: fusion trees: sketching, parallel comparison, most significant set bit. Integer: predecessor lower bound via round elimination. Integer: sorting in linear time for w = O(lg2+ε n), priority queues. Static trees: least common ancestor, range minimum queries, level ancestor. Strings: suffix tree, suffix array, linear-time construction for large alphabets, suffix tray, document retrieval. Succinct: rank, select, tries. Succinct: compact suffix arrays and trees. Dynamic graphs: link-cut trees, heavy-light decomposition. Dynamic graphs: Euler tour trees, decremental connectivity in trees in O(1), fully dynamic connectivity in O(lg2 n), survey. Dynamic graphs: Ω(lg n) lower bound for dynamic connectivity.
Design and Analysis of Algorithms (CS 161, Stanford)
Design and Analysis of Algorithms Course Website
Course description:
Introduction to fundamental techniques for designing and analyzing algorithms, including asymptotic analysis; divide-and-conquer algorithms and recurrences; greedy algorithms; data structures; dynamic programming; graph algorithms; and randomized algorithms.
Course topics:
INTRODUCTION. Why are you here? Example: Internet Routing. Shortest-Path Algorithms. Example: Sequence Alignment. Beating Brute Force Search. Administrivia. Recursive Algorithms for Integer Multiplication. Gauss's Trick. 2. BASIC DIVIDE & CONQUER. Merge Sort: Motivation. Merge Sort: Formal Definition. Running Time of Merge. Guiding Principles of CS161. Review of Asymptotic Notation. Asymptotic Notation: Big-Omega and Big-Theta. 3. THE MASTER METHOD. Integer Multiplication Revisited. Master Method: Formal Statement. Master Method: Examples. Proof of Master Method. Master Method: Interpretation of the Three Cases. 4. LINEAR-TIME MEDIAN. We apologize for the poor audio quality in this video. The Selection Problem. Partitioning Around a Pivot. A Generic Selection Algorithm. Median of Medians. Recap. Rough Recurrence. Key Lemma. The Substitution Method. Analysis of Rough Recurrence. 5. GRAPH SEARCH & DIJKSTRA'S ALGORITHM. Graph Primitives. Representing Graphs: Adjacency Matrices and Lists. Breadth-First and Depth-First Search. Dijkstra's Algorithm. Undirected Connectivity. 6. CONNECTIVITY IN DIRECTED GRAPHS. Strongly Connected Components. SCCs: A Two-Pass Algorithm. Depth-First Search Revisited. Two-Tier Structure of Directed Graphs. Correctness of Algorithm. Correctness Intuition. Proof of Key Lemma. Structure of the Web, Small World Property, and PageRank. 7. INTRODUCTION TO GREEDY ALGORITHMS. Course Roadmap. Application and Final Exam Info. A Scheduling Problem. Two Greedy Algorithms. Correctness Proof. Cost-Benefit Analysis. 8. MINIMUM SPANNING TREES. Introduction. Prim's Algorithm. Graph Theory Preliminaries. Feasibility of Prim's Algorithm. The Cut Property. Proof of Cut Property. Key Exchange Argument. Naive Running Time and Heap Review. Implementing Prim with Heaps. New Running Time Analysis. 9. KRUSKAL'S ALGORITHM AND UNION-FIND. Kruskal's Algorithm. Proof of Correctness. Naive Running Time. Union-Find Data Structure. Union by Rank. Rank and Size of Subtrees. Open Research Question. Path Compression. Path Compression and the Ackermann Function. 10. PATH COMPRESSION AND CLUSTERING. Union-Find Review. Path Compression. Rank Blocks. Counting Pointer Updates. Clustering. A Greedy Algorithm. Correctness of Greedy Algorithm. 11. INTRODUCTION TO RANDOMIZED ALGORITHMS. The Min Cut Problem. The Contraction Algorithm. Probability Review. Analysis of Contraction Algorithm. Success Through Independent Trials. Final Comments. 12. QUICKSORT. The QuickSort Algorithm. Best-Case and Worst-Case Pivots. Running Time of Randomized QuickSort. Probability Review. Linearity of Expectation. Counting Comparisons. Crux of Proof. Final Calculations. Lower Bound of Comaprison-Based Sorting. 13. HASHING. Hashing: Introduction. Hashing: High-Level Idea. Running Time. How to Analyze Hashing. Universal Hashing. Proof of O(1) Running Time. A Universal Family. Universality: Proof Idea. Bloom Filters. 14. BALANCED SEARCH TREES AND SKIP LISTS. Review of Binary Search Trees. Deleting from a BST. Red-Black Trees. Height of Red-Black Trees. Rotations. Insertion to a Red-Black Tree. Skip Lists: High-Level Idea. Skip Lists: Intuition for Analysis. 15. INTRODUCTION TO DYNAMIC PROGRAMMING. Dynamic Programming: A First Example. Structure of Optimal Solution. A Recursive Algorithm. Bottom-Up Formulation. Reconstruction Algorithm. The Knapsack Problem. Dynamic Programming Solution. 16. SEQUENCE ALIGNMENT. Sequence Alignment. Optimal Substructure. Dynamic Programming Solution. Dynamic Programming Algorithm. Shortest Paths with Negative Edge Lengths. On Negative Cycles. Optimal Substructure. 17. SHORTEST PATHS: BELLMAN-FORD AND FLOYD-WARSHALL. Single-Source Shortest Paths Revisited. The Bellman-Ford Algorithm. Negative Cycle Checking. Space Optimization. The Floyd-Warshall Algorithm. Dynamic Programming Algorithm. 18. NP-COMPLETE PROBLEMS. Polynomial Time Algorithms and P. The Traveling Salesman Problem. Reductions. Completeness. NP-Completeness. Many Problems are NP-Complete. Does P=NP?. Coping with NP-Completeness. The Vertex Cover Problem. Smarter Brute-Force Search. 19. APPROXIMATION ALGORITHMS. Performance Guarantees for Heuristics. A Greedy Knapsack Algorithm. Proof of Performance Guarantee. Final Exam Info. Better Performance via Dynamic Programming. Accuracy Analysis. Running Time Analysis. 20. THE WIDER WORLD OF ALGORITHMS. Bipartite Matching. Stable Matching. Gale-Shapley Proposal Algorithm. Maximum Flow. Selfish Flow and Braess's Paradox. Linear Programming. Computational Geometry. Approximation and Randomized Algorithms. Complexity and Epilogue.
Practical UNIX (Stanford)
Practical UNIX Video Lectures
Course description:
A practical introduction to using the Unix operating system with a focus on Linux command line skills. Topics include: grep and regular expressions, ZSH, Vim and Emacs, basic and advanced GDB features, permissions, working with the file system, revision control, Unix utilities, environment customization, and using Python for shell scripts. Topics may be added, given sufficient interest.
Course topics:
INTRO. Setting Up Linux. Intro Shell. Intro Text Editors. SHELL. Changing Your Login Shell. ZSH Globbing. SEARCH. Diff. Find. Grep and Regular Expressions - Intro. Grep and Regular Expressions - Find. Grep and Regular Expressions - Replace. Grep and Regular Expressions - Advanced. GDB. GDB Essentials. PERMISSIONS. Permissions. NETWORK. scp - Secury Copy (copy files over a network). wget - WWW Get (download files from the internet). cURL - Send Requests to Online Resources - Intro. cURL - Web Request Basics. cURL - Customizing Web Requests. SCRIPTING. Intro to Shell Scripting in Python. INPUT/OUTPUT REDIRECTION. Pipes: Redirecting Output to Another Command's Input. Redircting Output to a File. Redirecting a File to Standard Input. Tee: Outputting to stdout and a File.
Compiler Techniques (610, University of Massachusetts)
Compiler Techniques Video Lectures
Course description:
We explore basic problems in the translation of programming languages andexamine common implementation techniques. The course is centered on theconstruction of a compiler for a substantial fragment of a realisticimperative programming language. Use of a computer is required.
Course topics:
Course introduction; Holistic compiler overview. Scanning. Debugging. Parsing overview. Top−down parsing. Bottom−up parsing. Abstract Syntax Trees and Semantic Actions. JavaCUP (parser generator tool). Context: Type systems. IRs and Symbol Tables. Procedures. Visitor Design Pattern: Walking trees. Generating Tuples. Intro to Optimization. Data Flow Analysis. Some Scalar Optimizations. Instruction Selection. Register Allocation.
Have fun with these lectures and see you next time!
Related Posts
Geometric Folding Algorithms: Linkages, Origami, Polyhedra (MIT, 6.849, Erik Demaine)
Geometric Folding Algorithms Course Website
Geometric Folding Algorithms Video Lectures
Course description:
Whenever you have a physical object to be reconfigured, geometric folding often comes into play. This class is about algorithms for analyzing and designing such folds. Motivating applications include: automated design of new and complex origami, transforming robots by self-folding sheets or chains, how to fold robotic arms without collision, how to bend sheet metal into desired 3D shapes, understanding how proteins fold. Major progress have been made in recent years in many of these directions, thanks to a growing understanding of the mathematics and algorithms underlying folding. Nonetheless, many fundamental questions remain tantalizingly unsolved. This class covers the state-of-the-art in folding research, including a variety of open problems, enabling the student to do research and advance the field.
Course topics:
Origami intro: Piece of paper, crease pattern, mountain-valley assignment. Simple folds: Folding any shape (silhouette or gift wrapping), 1D flat-foldability characterization, 2D map-folding algorithm. Single-vertex crease patterns: Characterizations of flat-foldable crease patterns and mountain-valley patterns, combinatorics of the latter, local flat foldability is easy. Tree method of origami design: Introduction, uniaxial base, demo. Efficient origami design: Tree method, TreeMaker, uniaxial base, active path, rabbit-ear molecule, universal molecule, Margulis Napkin Problem; cube folding, checkerboard folding; Origamizer, watertight, tuck proxy. Universal hinge patterns: box pleating, polycubes; orthogonal maze folding. NP-hardness: introduction, reductions; simple foldability; crease pattern flat foldability; disk packing (for tree method). Artistic origami design: sampling of representational origami art; tree method and its use (guest lecture by Jason Ku). Fold and one cut: history, straight-skeleton method, disk-packing method, simple folds, higher dimensions, flattening polyhedra. Folding motions: folded states vs. motions; universal foldability of polygonal paper. Linkages to sign your name: graphs vs. linkages vs. configurations, configuration space; Kempe Universality Theorem, original proof, bug, corrections, generalizations and strengthenings. Rigidity theory: Rigidity, generic rigidity, minimal generic rigidity, Henneberg characterization, Laman characterization, polynomial-time algorithm, convex polyhedra. Rigidity theory: Infinitesimal rigidity, rigidity matrix. Tensegrity theory: tensegrities, equilibrium stress, duality, polyhedral lifting, Maxwell-Cremona Theorem. Locked linkages: Carpenter's Rule Theorem. Locked linkages: Algorithms for unfolding 2D chains, pseudotriangulation, energy; rigid folding of single-vertex origami; locked trees, infinitesimally locked linkages, Rules 1 and 2; locked 3D chains, knitting needles. Hinged dissections: Locked and unlocked chains of planar shapes, adorned chains, slender adornments, slender implies not locked, Kirszbaun's Theorem, locked triangles with apex angle > 90°; existence of hinged dissections, refinement. Polyhedron unfolding: Edge unfoldings, general unfoldings, big questions, curvature, general unfolding of convex polyhedra, source unfolding, star unfolding, edge-unfolding special convex polyhedra, fewest nets, edge-ununfoldable nonconvex polyhedra. Polyhedron unfolding: Vertex unfolding, facet paths, generally unfolding orthogonal polyhedra, grid unfolding, refinement, Manhattan towers, orthostacks, orthotubes, orthotrees. Polyhedron folding: Cauchy's Rigidity Theorem, Alexandrov's uniqueness of folding. Polyhedron folding: Decision problem, enumeration problem, combinatorial problem, nonconvex solution, convex polyhedral metrics, Alexandrov gluings, Alexandrov's Theorem, Bobenko-Izmestiev constructive proof, pseudopolynomial algorithm, ungluable polygons, perimeter halving, gluing tree, rolling belts. Polyhedron folding: Combinatorial type of gluing, exponential upper and lower bounds for combinatorially distinct gluings, polynomial upper bound for polygons of bounded sharpness, dynamic program for edge-to-edge gluing, including polynomial-time decision, exponential-time dynamic program for general gluing; case studies of Latin cross, equilateral triangle, and square. Polyhedron refolding: Dissection-like open problem, regular tetrahedron to box, Platonic solids to tetrahedra, box to box, polycubes, orthogonal unfoldings with nonorthogonal foldings. Smooth polyhedron folding: Smooth Alexandrov, D-forms, ribbon curves. Smooth polyhedron unfolding: Smooth prismatoids. Smooth origami: wrapping smooth surfaces with flat paper, Mozartkugel, contractive mapping, Burago-Zalgaller Theorem (crinkling/crumpling), stretched path, stretched wrapping, source wrapping, strip wrapping, petal wrapping, comb wrapping, Pareto curve. Protein folding: Fixed-angle linkages, tree, and chains; span; flattening; flat-state connectivity, disconnectivity of orthogonal partially rigid trees, connectivity of orthogonal open chains; locked fixed-angle chains; producible protein (fixed-angle) chains, ribosome, β-producible chains, helix-like canonical configuration, flat states are producible, producible states are connected. Protein folding: HP model of protein folding, NP-hardness and approximation, unique optimal foldings, protein design. Interlocked 3D chains: Lubiw's problem, unlocking 2-chains, unlocking two 3-chains and 2-chains, interlocking 3-chains, interlocking 3-chain with 4-chain, interlocking 4-chain with triangle, interlocking 3-chain with quadrangle, topological vs. geometric arguments, rigid and fixed-angle variations. Maekawa and Kawasaki's Theorems Revisited and Extended: Maekawa's Theorem, Kawasaki's Theorem, history (Justin, Huffman, Husimi), Robertson's 1977 paper, manifolds without boundary, strata, volumes, degree of map, higher dimensions, Justin's Theorem, Gauss-Bonnet Theorem, tessellations on a sphere (guest lecture by Thomas Hull). Flips and friends: Pockets, flips, “Erdős-Nagy Theorem”, false and correct proofs; flipturns; deflations; pops. 4D linkages: Chains, trees. Pleat folding: “Hyperbolic paraboloid”, circular pleat, self-folding origami, plastic deformation and elastic memory; triangulation, interval arithmetic; how paper folds between creases, ruled surfaces, torsal, straight creases stay straight, polygons stay flat; nonexistence. Inflation: Teabag problem, inflating polyhedra. Curved creases: Recreating David Huffman's curved-crease folding. Architectural Origami: Origamizer, Freeform Origami, Rigid Origami Simulator, cylindrical origami, thick origami (guest lecture by Tomohiro Tachi).
Advanced Data Structures (MIT, 6.851, Erik Demaine)
Advanced Data Structures Course Website
Advanced Data Structures Video Lectures
Course description:
Data structures play a central role in modern computer science. You interact with data structures even more often than with algorithms (think Google, your mail server, and even your network routers). In addition, data structures are essential building blocks in obtaining efficient algorithms. This course covers major results and current directions of research in data structures: TIME TRAVEL We can remember the past efficiently (a technique called persistence), but in general it's difficult to change the past and see the outcomes on the present (retroactivity). So alas, Back To The Future isn't really possible. GEOMETRY When data has more than one dimension (e.g. maps, database tables). DYNAMIC OPTIMALITY Is there one binary search tree that's as good as all others? We still don't know, but we're close. MEMORY HIERARCHY Real computers have multiple levels of caches. We can optimize the number of cache misses, often without even knowing the size of the cache. HASHING Hashing is the most used data structure in computer science. And it's still an active area of research. INTEGERS Logarithmic time is too easy. By careful analysis of the information you're dealing with, you can often reduce the operation times substantially, sometimes even to constant. We will also cover lower bounds that illustrate when this is not possible. DYNAMIC GRAPHS A network link went down, or you just added or deleted a friend in a social network. We can still maintain essential information about the connectivity as it changes. STRINGS Searching for phrases in giant text (think Google or DNA). SUCCINCT Most “linear size” data structures you know are much larger than they need to be, often by an order of magnitude. Some data structures require almost no space beyond the raw data but are still fast (think heaps, but much cooler).
Course topics:
Temporal: class overview, pointer machine, partial persistence, full persistence, confluent persistence, functional. Temporal: partial retroactivity, full retroactivity, nonoblivious retroactivity. Geometric: point location via persistence, dynamic via retroactive; orthogonal range queries, range trees, layered range trees, dynamizing augmentation via weight balance, fractional cascading. Geometric: O(log n) 3D orthogonal range searching via fractional cascading; kinetic data structures. Dynamic optimality: binary search trees, analytic bounds, splay trees, geometric view, greedy algorithm. Dynamic optimality: independent rectangle, Wilber, and Signed Greedy lower bounds; key-independent optimality; O(lg lg n)-competitive Tango trees. Memory hierarchy: models, cache-oblivious B-trees. Memory hierarchy: ordered-file maintenance, list labeling, order queries, cache-oblivious priority queues. Memory hierarchy: distribution sweeping via lazy funnelsort; cache-oblivious orthogonal 2D range searching: batched and online. Dictionaries: universal, k-wise independent, simple tabulation hashing; chaining, dynamic perfect hashing, linear probing, cuckoo hashing. Integer: models, predecessor problem, van Emde Boas, x-fast and y-fast trees, indirection. Integer: fusion trees: sketching, parallel comparison, most significant set bit. Integer: predecessor lower bound via round elimination. Integer: sorting in linear time for w = O(lg2+ε n), priority queues. Static trees: least common ancestor, range minimum queries, level ancestor. Strings: suffix tree, suffix array, linear-time construction for large alphabets, suffix tray, document retrieval. Succinct: rank, select, tries. Succinct: compact suffix arrays and trees. Dynamic graphs: link-cut trees, heavy-light decomposition. Dynamic graphs: Euler tour trees, decremental connectivity in trees in O(1), fully dynamic connectivity in O(lg2 n), survey. Dynamic graphs: Ω(lg n) lower bound for dynamic connectivity.
Design and Analysis of Algorithms (CS 161, Stanford)
Design and Analysis of Algorithms Course Website
Course description:
Introduction to fundamental techniques for designing and analyzing algorithms, including asymptotic analysis; divide-and-conquer algorithms and recurrences; greedy algorithms; data structures; dynamic programming; graph algorithms; and randomized algorithms.
Course topics:
INTRODUCTION. Why are you here? Example: Internet Routing. Shortest-Path Algorithms. Example: Sequence Alignment. Beating Brute Force Search. Administrivia. Recursive Algorithms for Integer Multiplication. Gauss's Trick. 2. BASIC DIVIDE & CONQUER. Merge Sort: Motivation. Merge Sort: Formal Definition. Running Time of Merge. Guiding Principles of CS161. Review of Asymptotic Notation. Asymptotic Notation: Big-Omega and Big-Theta. 3. THE MASTER METHOD. Integer Multiplication Revisited. Master Method: Formal Statement. Master Method: Examples. Proof of Master Method. Master Method: Interpretation of the Three Cases. 4. LINEAR-TIME MEDIAN. We apologize for the poor audio quality in this video. The Selection Problem. Partitioning Around a Pivot. A Generic Selection Algorithm. Median of Medians. Recap. Rough Recurrence. Key Lemma. The Substitution Method. Analysis of Rough Recurrence. 5. GRAPH SEARCH & DIJKSTRA'S ALGORITHM. Graph Primitives. Representing Graphs: Adjacency Matrices and Lists. Breadth-First and Depth-First Search. Dijkstra's Algorithm. Undirected Connectivity. 6. CONNECTIVITY IN DIRECTED GRAPHS. Strongly Connected Components. SCCs: A Two-Pass Algorithm. Depth-First Search Revisited. Two-Tier Structure of Directed Graphs. Correctness of Algorithm. Correctness Intuition. Proof of Key Lemma. Structure of the Web, Small World Property, and PageRank. 7. INTRODUCTION TO GREEDY ALGORITHMS. Course Roadmap. Application and Final Exam Info. A Scheduling Problem. Two Greedy Algorithms. Correctness Proof. Cost-Benefit Analysis. 8. MINIMUM SPANNING TREES. Introduction. Prim's Algorithm. Graph Theory Preliminaries. Feasibility of Prim's Algorithm. The Cut Property. Proof of Cut Property. Key Exchange Argument. Naive Running Time and Heap Review. Implementing Prim with Heaps. New Running Time Analysis. 9. KRUSKAL'S ALGORITHM AND UNION-FIND. Kruskal's Algorithm. Proof of Correctness. Naive Running Time. Union-Find Data Structure. Union by Rank. Rank and Size of Subtrees. Open Research Question. Path Compression. Path Compression and the Ackermann Function. 10. PATH COMPRESSION AND CLUSTERING. Union-Find Review. Path Compression. Rank Blocks. Counting Pointer Updates. Clustering. A Greedy Algorithm. Correctness of Greedy Algorithm. 11. INTRODUCTION TO RANDOMIZED ALGORITHMS. The Min Cut Problem. The Contraction Algorithm. Probability Review. Analysis of Contraction Algorithm. Success Through Independent Trials. Final Comments. 12. QUICKSORT. The QuickSort Algorithm. Best-Case and Worst-Case Pivots. Running Time of Randomized QuickSort. Probability Review. Linearity of Expectation. Counting Comparisons. Crux of Proof. Final Calculations. Lower Bound of Comaprison-Based Sorting. 13. HASHING. Hashing: Introduction. Hashing: High-Level Idea. Running Time. How to Analyze Hashing. Universal Hashing. Proof of O(1) Running Time. A Universal Family. Universality: Proof Idea. Bloom Filters. 14. BALANCED SEARCH TREES AND SKIP LISTS. Review of Binary Search Trees. Deleting from a BST. Red-Black Trees. Height of Red-Black Trees. Rotations. Insertion to a Red-Black Tree. Skip Lists: High-Level Idea. Skip Lists: Intuition for Analysis. 15. INTRODUCTION TO DYNAMIC PROGRAMMING. Dynamic Programming: A First Example. Structure of Optimal Solution. A Recursive Algorithm. Bottom-Up Formulation. Reconstruction Algorithm. The Knapsack Problem. Dynamic Programming Solution. 16. SEQUENCE ALIGNMENT. Sequence Alignment. Optimal Substructure. Dynamic Programming Solution. Dynamic Programming Algorithm. Shortest Paths with Negative Edge Lengths. On Negative Cycles. Optimal Substructure. 17. SHORTEST PATHS: BELLMAN-FORD AND FLOYD-WARSHALL. Single-Source Shortest Paths Revisited. The Bellman-Ford Algorithm. Negative Cycle Checking. Space Optimization. The Floyd-Warshall Algorithm. Dynamic Programming Algorithm. 18. NP-COMPLETE PROBLEMS. Polynomial Time Algorithms and P. The Traveling Salesman Problem. Reductions. Completeness. NP-Completeness. Many Problems are NP-Complete. Does P=NP?. Coping with NP-Completeness. The Vertex Cover Problem. Smarter Brute-Force Search. 19. APPROXIMATION ALGORITHMS. Performance Guarantees for Heuristics. A Greedy Knapsack Algorithm. Proof of Performance Guarantee. Final Exam Info. Better Performance via Dynamic Programming. Accuracy Analysis. Running Time Analysis. 20. THE WIDER WORLD OF ALGORITHMS. Bipartite Matching. Stable Matching. Gale-Shapley Proposal Algorithm. Maximum Flow. Selfish Flow and Braess's Paradox. Linear Programming. Computational Geometry. Approximation and Randomized Algorithms. Complexity and Epilogue.
Practical UNIX (Stanford)
Practical UNIX Video Lectures
Course description:
A practical introduction to using the Unix operating system with a focus on Linux command line skills. Topics include: grep and regular expressions, ZSH, Vim and Emacs, basic and advanced GDB features, permissions, working with the file system, revision control, Unix utilities, environment customization, and using Python for shell scripts. Topics may be added, given sufficient interest.
Course topics:
INTRO. Setting Up Linux. Intro Shell. Intro Text Editors. SHELL. Changing Your Login Shell. ZSH Globbing. SEARCH. Diff. Find. Grep and Regular Expressions - Intro. Grep and Regular Expressions - Find. Grep and Regular Expressions - Replace. Grep and Regular Expressions - Advanced. GDB. GDB Essentials. PERMISSIONS. Permissions. NETWORK. scp - Secury Copy (copy files over a network). wget - WWW Get (download files from the internet). cURL - Send Requests to Online Resources - Intro. cURL - Web Request Basics. cURL - Customizing Web Requests. SCRIPTING. Intro to Shell Scripting in Python. INPUT/OUTPUT REDIRECTION. Pipes: Redirecting Output to Another Command's Input. Redircting Output to a File. Redirecting a File to Standard Input. Tee: Outputting to stdout and a File.
Compiler Techniques (610, University of Massachusetts)
Compiler Techniques Video Lectures
Course description:
We explore basic problems in the translation of programming languages andexamine common implementation techniques. The course is centered on theconstruction of a compiler for a substantial fragment of a realisticimperative programming language. Use of a computer is required.
Course topics:
Course introduction; Holistic compiler overview. Scanning. Debugging. Parsing overview. Top−down parsing. Bottom−up parsing. Abstract Syntax Trees and Semantic Actions. JavaCUP (parser generator tool). Context: Type systems. IRs and Symbol Tables. Procedures. Visitor Design Pattern: Walking trees. Generating Tuples. Intro to Optimization. Data Flow Analysis. Some Scalar Optimizations. Instruction Selection. Register Allocation.
Have fun with these lectures and see you next time!
Related Posts
- Free Computer Science Video Lecture Courses
(Courses include web application development, lisp/scheme programming, data structures, algorithms, machine structures, programming languages, principles of software engineering, object oriented programming in java, systems, computer system engineering, computer architecture, operating systems, database management systems, performance analysis, cryptography, artificial intelligence) - Programming Lectures and Tutorials
(Lectures include topics such as software engineering, javascript programming, overview of firefox's firebug extension, document object model, python programming, design patterns in python, java programming, delphi programming, vim editor and sqlite database design) - Programming, Networking Free Video Lectures and Other Interesting Ones
(Includes lectures on Python programming language, Common Lisp, Debugging, HTML and Web, BGP networking, Building scalable systems, and as a bonus lecture History of Google) - More Mathematics and Theoretical Computer Science Video Lectures
(Includes algebra, elementary statistics, applied probability, finite mathematics, trigonometry with calculus, mathematical computation, pre-calculus, analytic geometry, first year calculus, business calculus, mathematical writing (by Knuth), computer science problem seminar (by Knuth), dynamic systems and chaos, computer musings (by Knuth) and other Donald E. Knuth lectures) - More Mathematics and Theoretical Computer Science Video Lectures
(Includes algebra, elementary statistics, applied probability, finite mathematics, trigonometry with calculus, mathematical computation, pre-calculus, analytic geometry, first year calculus, business calculus, mathematical writing (by Knuth), computer science problem seminar (by Knuth), dynamic systems and chaos, computer musings (by Knuth) and other Donald E. Knuth lectures) - Pure Computer Science
(Includes basics of computation theory, intro to computer science, data structures, compiler optimization, intro to computers and internet, intro to clojure, and some videos from EECS colloquium at Case Western Reserve University.) - Programming video lectures
(Includes Steven Skiena's programming challenges with solutions. IOI 2009 problems and solutions. Haskell programming. Scheme. SICP. Scheme Macros. Machine Learning. Natural Language Processing. Programming Methodology. Programming Abstractions. Programming Paradigms. Evolution of Lisp. Programming Effective ML.) - Full Stanford University Courses
(Includes Artificial Intelligence, Databases, Machine Learning, iPhone Application Development and Programming Parallel Processors.)
Social Bookmark This Post:
posted by Peter Krumins at
11:16 PM
0 Comments:
Post a Comment
<< Home