This is an intermediate algorithms course note
with an emphasis on teaching techniques for the design and analysis of efficient
algorithms, emphasizing methods of application. Topics include
divide-and-conquer, randomization, dynamic programming, greedy algorithms,
incremental improvement, complexity, and cryptography.
Author(s): Prof. Erik Demaine, Prof. Srinivas
Devadas and Prof. Nancy Lynch
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.
lecture note discusses the approaches to designing optimization algorithms,
including dynamic programming and greedy algorithms, graph algorithms, minimum
spanning trees, shortest paths, and network flows. Also it briefly discusses
algorithmic problems arising from geometric settings, that is, computational
note covers the following topics related to Algorithm Analysis and Design: Model
and Analysis, Warm up problems, Brute force and Greedy strategy, Dynamic
Programming, Searching, Multidimensional Searching and Geometric algorithms,
Fast Fourier Transform and Applictions, String matching and finger printing,
Graph Algorithms, NP Completeness and Approximation Algorithms.
This note covers the design of algorithms according to
methodology and application. Methodologies include: divide and
conquer, dynamic programming, and greedy strategies. Applications
involve: sorting, ordering and searching, graph algorithms,
geometric algorithms, mathematical (number theory, algebra and
linear algebra) algorithms, and string matching algorithms.