Algorithm design and analysis is a fundamental and important part of computer science.
This repository contains advanced techniques for the design and analysis of algorithms, and explores a variety of applications.
The topics and applications that coverd include greedy algorithms, network algorithms and network design, huffman codes and data compression, NP-hardness, approximation and randomized algorithms.
It Also contains various useful ideas, including randomization, probabilistic analysis, amortized analysis, competitive analysis, eigenvalues, linear and semi-definite programming, high dimensional geometry, and random walks.
- pseudo-code for describing algorithms
- big-Oh notation and complexity analysis
- related mathematics foundations
- data structures such as lists, stacks, queues, and binary trees
- sorting: insertion sort, selection sort, mergesort, quicksort, heapsort, radix sort
- selection problem
- basic graph concepts and representations
- depth-first search and breadth-first search
- Dijkstra shortest path algorithm
- Dijkstra-Prim minimum spanning tree algorithm
- the algorithm for testing biconnectivity
- Strassen’s matrix multiplication algorithm
- Warshall’s transitive closure algorithm
- general idea of P, NP, and NP-completeness
- search tree structures (worst case analysis)
- union and find (amortized analysis)
- topological sort (application of DFS)
- strongly connected components (application of DFS)
- minimum spanning tree algorithms (greedy algorithms, including improved Kruskal’s algorithm and Prim’s algorithm)
- single-source shortest path algorithms (greedy algorithms, including Dijkstra’s algorithm and Bellman-Ford algorithm)
- maximum flow
- graph matching
- string and sequence algorithms
- NP-completeness
- approximation algorithms
- randomized algorithms
- parameterized algorithms
- bigdata algorithms