Introduction to Algorithms

Algorithm is an accurate and understandable guide which is performed to address any given problem. But not many people know how to prepare effective steps to design an algorithm with clear and ambiguous rules.

Who should take this course?

This course is beneficial for students – who want to know more about algorithms and for designers – who are struggling to design and analyze algorithm. Prior knowledge of mathematics and probability will make it easier for students to undergo the entire course.  

What are the benefits of the course?

This guide will help you learn

- Designing and analyzing algorithms
- Data structure
- Dynamic programming

Table of contents:

- INTRODUCTION

- THE MASTER METHOD

- LINEAR-TIME MEDIAN

The Selection Problem
Partitioning Around a Pivot
A Generic Selection Algorithm
Median of Medians
Recap
Rough Recurrence
The Substitution Method
Analysis of Rough Recurrence

- GRAPH SEARCH & DIJKSTRA'S ALGORITH
 
Graph Primitives
Representing Graphs: Adjacency Matrices and Lists
Breadth-First and Depth-First Search
Dijkstra's Algorithm
Undirected Connectivity
 
- 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 Page Rank

- INTRODUCTION TO GREEDY ALGORITHMS
 
Course Roadmap
Application and Final Exam Info
A Scheduling Problem
Two Greedy Algorithms
Correctness Proof
Cost-Benefit Analysis

- 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
New Running Time Analysis
 
- KRUSKAL'S ALGORITHM AND UNION-FIND

Kruskal's Algorithm
Naive Running Time
Union-Find Data Structure
Union by Rank
Rank and Size of Subtrees
Open Research Question
Path Compression and the Ackermann Function

- PATH COMPRESSION AND CLUSTERING
 
Union-Find Review
Path Compression
Rank Blocks
Counting Pointer Updates
Clustering
A Greedy Algorithm
Correctness of Greedy Algorithm

- INTRODUCTION TO RANDOMIZED ALGORITHMS

The Min Cut Problem
The Contraction Algorithm
Probability Review
Analysis of Contraction Algorithm
Success through Independent Trials
Final Comments

- 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 Comparison-Based Sorting

- HASHING

Hashing: Introduction
Hashing: High-Level Idea
Running Time
How to Analyze Hashing
Universal Hashing
A Universal Family
Universality: Proof Idea
Bloom Filters

- 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


- 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

- SEQUENCE ALIGNMENT

Sequence Alignment
Optimal Substructure
Dynamic Programming Solution
Dynamic Programming Algorithm
Shortest Paths with Negative Edge Lengths
On Negative Cycles
Optimal Substructure

- 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
 
- 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
 
- THE WIDER WORLD OF ALGORITHMS

Bipartite Matching
Stable Matching
Gale-Shapley Proposal Algorithm
Maximum Flow
Linear Programming
Computational Geometry
Approximation and Randomized Algorithms
Complexity and Epilogue
 
Author Bio:

This efficient, effective and convenient guide has been designed and prepared by renowned professors and lecturers of different universities and colleges across the United States of America.