40 Algorithms Every Programmer Should Know: Hone your problem-solving skills by learning different algorithms and their implementation in Python

Cover
Title Page
Copyright and Credits
Dedication
About Packt
Contributors
Table of Contents
Preface
Section 1: Fundamentals and Core Algorithms
Chapter 1: Overview of Algorithms
	What is an algorithm?
		The phases of an algorithm
	Specifying the logic of an algorithm
		Understanding pseudocode 
			A practical example of pseudocode
		Using snippets 
		Creating an execution plan
	Introducing Python packages
		Python packages
			The SciPy ecosystem
		Implementing Python via the Jupyter Notebook
	Algorithm design techniques
		The data dimension
		Compute dimension
			A practical example
	Performance analysis
		Space complexity analysis
		Time complexity analysis
		Estimating the performance
			The best case
			The worst case
			The average case
		Selecting an algorithm
		Big O notation
			Constant time (O(1)) complexity
			Linear time (O(n)) complexity 
			Quadratic time (O(n2)) complexity
			Logarithmic time (O(logn)) complexity
	Validating an algorithm
		Exact, approximate, and randomized algorithms
		Explainability
	Summary
Chapter 2: Data Structures Used in Algorithms
	Exploring data structures in Python
		List
			Using lists
			Lambda functions
			The range function 
			The time complexity of lists
		Tuples
			The time complexity of tuples
		Dictionary
			The time complexity of a dictionary
		Sets
			Time complexity analysis for sets
		DataFrames
			Terminologies of DataFrames
			Creating a subset of a DataFrame
				Column selection
				Row selection
		Matrix
			Matrix operations
	Exploring abstract data types 
		Vector
		Stacks
			The time complexity of stacks
			Practical example
		Queues
		The basic idea behind the use of stacks and queues
		Tree
			Terminology
			Types of trees
			Practical examples
	Summary
Chapter 3: Sorting and Searching Algorithms
	Introducing Sorting Algorithms
		Swapping Variables in Python
		Bubble Sort
			Understanding the Logic Behind Bubble Sort
			A Performance Analysis of Bubble Sort
		Insertion Sort
		Merge Sort
		Shell Sort
			A Performance Analysis of Shell Sort
		Selection Sort
			The performance of the selection sort algorithm
			Choosing a sorting algorithm
	Introduction to Searching Algorithms
		Linear Search
			The Performance of Linear Search
		Binary Search
			The Performance of Binary Search
		Interpolation Search
			The Performance of Interpolation Search
	Practical Applications
	Summary
Chapter 4: Designing Algorithms
	Introducing the basic concepts of designing an algorithm
		Concern 1 – Will the designed algorithm produce the result we expect?
		Concern 2 – Is this the optimal way to get these results?
			Characterizing the complexity of the problem
		Concern 3 – How is the algorithm going to perform on larger datasets?
	Understanding algorithmic strategies
		Understanding the divide-and-conquer strategy
			Practical example – divide-and-conquer applied to Apache Spark
		Understanding the dynamic programming strategy
		Understanding greedy algorithms
	Practical application – solving the TSP
		Using a brute-force strategy
		Using a greedy algorithm
	Presenting the PageRank algorithm
		Problem definition
		Implementing the PageRank algorithm
	Understanding linear programming
		Formulating a linear programming problem
			Defining the objective function
			Specifying constraints
	Practical application – capacity planning with linear programming
	Summary
Chapter 5: Graph Algorithms
	Representations of graphs
		Types of graphs
			Undirected graphs
			Directed graphs
			Undirected multigraphs
			Directed multigraphs
		Special types of edges
		Ego-centered networks
		Social network analysis
	Introducing network analysis theory
		Understanding the shortest path
		Creating a neighborhood 
			Triangles
			Density
		Understanding centrality measures
			Degree
			Betweenness
			Fairness and closeness
			Eigenvector centrality
		Calculating centrality metrics using Python
	Understanding graph traversals
		Breadth-first search 
			Initialization 
			The main loop
		Depth-first search 
	Case study – fraud analytics
		Conducting simple fraud analytics
		Presenting the watchtower fraud analytics methodology
			Scoring negative outcomes 
			Degree of suspicion 
	Summary
Section 2: Machine Learning Algorithms
Chapter 6: Unsupervised Machine Learning Algorithms
	Introducing unsupervised learning
		Unsupervised learning in the data-mining life cycle 
		Current research trends in unsupervised learning
		Practical examples
			Voice categorization
			Document categorization
	Understanding clustering algorithms
		Quantifying similarities 
			Euclidean distance
			Manhattan distance
			Cosine distance
			K-means clustering algorithm
			The logic of k-means clustering
				Initialization
				The steps of the k-means algorithm
				Stop condition
			Coding the k-means algorithm
			Limitation of k-means clustering
		Hierarchical clustering
			Steps of hierarchical clustering
			Coding a hierarchical clustering algorithm
		Evaluating the clusters
		Application of clustering
	Dimensionality reduction
		Principal component analysis
		Limitations of PCA
	Association rules mining
		Examples of use
		Market basket analysis
		Association rules
			Types of rule
				Trivial rules
				Inexplicable rules
				Actionable rules
		Ranking rules
			Support
			Confidence
			Lift
		Algorithms for association analysis
			Apriori Algorithm
				Limitations of the apriori algorithm
			FP-growth algorithm
				Populating the FP-tree
				Mining Frequent Patterns
				Code for using FP-growth
	Practical application– clustering similar tweets together
		Topic modeling
		Clustering
	Anomaly-detection algorithms
		Using clustering
		Using density-based anomaly detection
		Using support vector machines
	Summary
Chapter 7: Traditional Supervised Learning Algorithms
	Understanding supervised machine learning
		Formulating supervised machine learning
		Understanding enabling conditions
		Differentiating between classifiers and regressors
	Understanding classification algorithms
		Presenting the classifiers challenge
			The problem statement
			Feature engineering using a data processing pipeline
				Importing data 
				 Feature selection
				One-hot encoding
				Specifying the features and label
				Dividing the dataset into testing and training portions
				Scaling the features
		Evaluating the classifiers
			Confusion matrix
			Performance metrics
			Understanding overfitting
				Bias
				Variance
				Bias-variance trade-off
		Specifying the phases of classifiers
		Decision tree classification algorithm
			Understanding the decision tree classification algorithm
			Using the decision tree classification algorithm for the classifiers challenge
			The strengths and weaknesses of decision tree classifiers
				Strengths
				Weaknesses 
			Use cases
				Classifying records
				Feature selection
		Understanding the ensemble methods
			Implementing gradient boosting with the XGBoost algorithm
			Using the random forest algorithm
				Training a random forest algorithm
				Using random forest for predictions
				Differentiating the random forest algorithm from ensemble boosting
			Using the random forest algorithm for the classifiers challenge
		Logistic regression
			Assumptions
			Establishing the relationship
				The loss and cost functions
			When to use logistic regression
			Using the logistic regression algorithm for the classifiers challenge
		The SVM algorithm
			Using the SVM algorithm for the classifiers challenge
		Understanding the naive Bayes algorithm
			Bayes, theorem
			Calculating probabilities
			Multiplication rules for AND events
			The general multiplication rule
			Addition rules for OR events
			Using the naive Bayes algorithm for the classifiers challenge
		For classification algorithms, the winner is...
	Understanding regression algorithms
		Presenting the regressors challenge
			The problem statement of the regressors challenge
				Exploring the historical dataset
			Feature engineering using a data processing pipeline
		 Linear regression
			Simple linear regression
			Evaluating the regressors
			Multiple regression
			Using the linear regression algorithm for the regressors challenge
			When is linear regression used?
			The weaknesses of linear regression
		The regression tree algorithm
			Using the regression tree algorithm for the regressors challenge
		The gradient boost regression algorithm
			Using gradient boost regression algorithm for the regressors challenge
		For regression algorithms, the winner is...
	Practical example – how to predict the weather
	Summary
Chapter 8: Neural Network Algorithms
	Understanding ANNs
	The Evolution of ANNs
	Training a Neural Network
		Understanding the Anatomy of a Neural Network
		Defining Gradient Descent 
		Activation Functions
			Threshold Function
			Sigmoid
			Rectified linear unit (ReLU)
			Leaky ReLU
			Hyperbolic tangent (tanh)
			Softmax
	Tools and Frameworks
		Keras
			Backend Engines of Keras
			Low-level layers of the deep learning stack
			Defining hyperparameters
			Defining a Keras model
			Choosing sequential or functional model
		Understanding TensorFlow
			Presenting TensorFlow's Basic Concepts
				Understanding Tensor Mathematics
		Understanding the Types of Neural Networks
			Convolutional Neural Networks 
				Convolution 
				Pooling 
			Recurrent Neural Networks 
			Generative Adversarial Networks
	Transfer Learning
	Case study – using deep learning for fraud detection
		Methodology
	Summary
Chapter 9: Algorithms for Natural Language Processing
	Introducing NLP
		Understanding NLP terminology
			Normalization
			Corpus
			Tokenization
			Named entity recognition 
			Stopwords
			Sentiment analysis
			Stemming and lemmatization
		NLTK
	BoW-based NLP
	Introduction to word embedding
		The neighborhood of a word
		Properties of word embeddings
	Using RNNs for NLP
	Using NLP for sentiment analysis
	Case study: movie review sentiment analysis 
	Summary
Chapter 10: Recommendation Engines
	Introducing recommendation systems
	Types of recommendation engines
		Content-based recommendation engines
			Finding similarities between unstructured documents
			Using a co-occurrence matrix
		Collaborative filtering recommendation engines
		Hybrid recommendation engines
			Generating a similarity matrix of the items
			Generating reference vectors of the users
			Generating recommendations
	Understanding the limitations of recommender systems
		The cold start problem
		Metadata requirements
		The data sparsity problem
		Bias due to social influence
		Limited data
	Areas of practical applications
	Practical example – creating a recommendation engine
	Summary
Section 3: Advanced Topics
Chapter 11: Data Algorithms
	Introduction to data algorithms
		Data classification
	Presenting data storage algorithms
		Understanding data storage strategies
			Presenting the CAP theorem
				CA systems
				AP systems
				CP systems
	Presenting streaming data algorithms
		Applications of streaming
	Presenting data compression algorithms
		Lossless compression algorithms
			Understanding the basic techniques of lossless compression
				Huffman coding
	A practical example – Twitter real-time sentiment analysis
	Summary
Chapter 12: Cryptography
	Introduction to Cryptography
		Understanding the Importance of the Weakest Link 
		The Basic Terminology
		Understanding the Security Requirements
			Identifying the Entities
			Establishing the Security Goals
			Understanding the Sensitivity of the Data
		Understanding the Basic Design of Ciphers
			Presenting Substitution Ciphers
			Understanding Transposition Ciphers
	Understanding the Types of Cryptographic Techniques
		Using the Cryptographic Hash Function
			Implementing cryptographic hash functions
				Understanding MD5-tolerated
				Understanding SHA
			An Application of  the Cryptographic Hash Function 
		Using Symmetric Encryption
			Coding Symmetric Encryption
			The Advantages of Symmetric Encryption
			The Problems with Symmetric Encryption
		Asymmetric Encryption
			The SSL/TLS Handshaking Algorithm
			Public Key Infrastructure 
	Example – Security Concerns When Deploying a Machine Learning Model
		MITM attacks
			How to prevent MITM attacks
		Avoiding Masquerading
		 Data and Model Encrpytion
	Summary
Chapter 13: Large-Scale Algorithms
	Introduction to large-scale algorithms
		Defining a well-designed, large-scale algorithm
		Terminology
			Latency
			Throughput
			Network bisection bandwidth
			Elasticity
	The design of parallel algorithms
		Amdahl's law 
			Conducting sequential process analysis
				Conducting parallel execution analysis
		Understanding task granularity
		Load balancing
		Locality issues
		Enabling concurrent processing in Python
	Strategizing multi-resource processing
		Introducing CUDA 
			Designing parallel algorithms on CUDA
			Using GPUs for data processing in Python
		Cluster computing
			Implementing data processing in Apache Spark
		The hybrid strategy
	Summary
Chapter 14: Practical Considerations
	Introducing practical considerations
		The sad story of an AI Twitter Bot
	The explainability of an algorithm
		Machine learning algorithms and explainability
			Presenting strategies for explainability
				Implementing explainability
	Understanding ethics and algorithms
		Problems with learning algorithms
		Understanding ethical considerations 
			Inconclusive evidence
			Traceability
			Misguided evidence
			Unfair outcomes
	Reducing bias in models    
	Tackling NP-hard problems
		Simplifying the problem 
			Example
		Customizing a well-known solution to a similar problem
			Example
		Using a probabilistic method
			Example
	When to use algorithms
		A practical example – black swan events
			Four criteria to classify an event as a black swan event
			Applying algorithms to black swan events
	Summary
Other Books You May Enjoy
Index