This note covers the following topics:
Lazy Evaluation and S-Notation, Amortization and Persistence via Lazy
Evaluation, Eliminating Amortization, Lazy Rebuilding, Numerical
Representations, Data-Structural Bootstrapping, Implicit Recursive Slowdown.
introduces students to advanced techniques for the design and analysis of
algorithms, and explores a variety of applications. Topics covered includes:
Greedy algorithms, Dynamic programming, Network flow applications, matchings,
Randomized algorithms, Karger's min-cut algorithm, NP-completeness, Linear
programming, LP duality, Primal-dual algorithms, Semi-definite Programming, MB
model contd., PAC model, Boosting in the PAC framework.
The field of approximation algorithms has
developed in response to the difficulty in solving a good many optimization
problems exactly. This note will present general techniques that underly these
explains core material in data structures and algorithm design, and also helps
students prepare for research in the field of algorithms. Topics covered
includes: Splay Trees, Amortized Time for Splay Trees, Maintaining Disjoint
Sets, Binomial heaps, F-heap, Minimum Spanning Trees, Fredman-Tarjan MST
Algorithm, Light Approximate Shortest Path Trees, Matchings, Hopcroft-Karp
Matching Algorithm, Two Processor Scheduling, Network Flow - Maximum Flow
Problem, The Max Flow Problem and Max-Flow Algorithm.
This note covers the following
topics: Self adjusting data structures, amortized analysis, self adjusting
lists, Splay trees, their performance and related conjectures, Hashing, FKS
perfect hashing, Cuckoo hasing, dynamic perfect hashing, Fusion Trees, Fully
dynamic connectivity in polylogarithmic time, Dynamic all pairs shortest paths,
Linear time construction of Suffix trees and arrays, Succinct Data Structures,
External memory data structures, Geometric data structures, Top trees,
Retroactive data structures, Online optimal structure for planar point
note will examine various data structures for storing and accessing information
together with relationships between the items being stored, and algorithms for efficiently
finding solutions to various problems, both relative to the data structures and
queries and operations based on the relationships between the items stored.
Topics covered includes: Algorithm analysis, List, stacks and queues, Trees and
hierarchical orders, Ordered trees, Search trees, Priority queues, Sorting
algorithms, Hash functions and hash tables, Equivalence relations and disjoint
sets, Graph algorithms, Algorithm design and Theory of computation.
This note introduces a number of important algorithm
design techniques as well as basic algorithms that are interesting both from a
theoretical and also practical point of view. Topics covered are: Introduction
to Algorithms, Asymptotic Analysis, Recurrence Equations, Sorting Algorithms,
Search Trees, Randomized Algorithms and Quicksort, Selection Algorithms, Number
Theory and Cryptography Algorithms, Graph algorithms, Greedy Algorithms and
External Memory Algorithms.
Author(s): Department of Computer
Science at Duke University