book

50 Algorithms Every Programmer Should Know - Second Edition

Name: 50 Algorithms Every Programmer Should Know - Second Edition
Author: Imran Ahmad
ISBN: 9781803247762

by Imran Ahmad

September 2023

Intermediate to advanced

538 pages

13h 11m

English

Packt Publishing

Read now

Unlock full access

Preface
Who this book is forWhat this book coversGet in touch
Section 1: Fundamentals and Core Algorithms
Overview of Algorithms
What is an algorithm?The phases of an algorithmDevelopment environmentPython packagesThe SciPy ecosystemUsing Jupyter NotebookAlgorithm design techniquesThe data dimensionThe compute dimensionPerformance analysisSpace complexity analysisTime complexity analysisEstimating the performanceThe best caseThe worst caseThe average caseBig O notationConstant time (O(1)) complexityLinear time (O(n)) complexityQuadratic time (O(n2)) complexityLogarithmic time (O(logn)) complexitySelecting an algorithmValidating an algorithmExact, approximate, and randomized algorithmsExplainabilitySummary
Data Structures Used in Algorithms
Exploring Python built-in data typesListsUsing listsModifying lists: append and pop operationsThe range() functionThe time complexity of listsTuplesThe time complexity of tuplesDictionaries and setsDictionariesSetsTime complexity analysis for setsWhen to use a dictionary and when to use a setUsing Series and DataFramesSeriesDataFrameCreating a subset of a DataFrameMatricesMatrix operationsBig O notation and matricesExploring abstract data typesVectorTime complexity of vectorsStacksTime complexity of stack operationsPractical exampleQueuesTime complexity analysis for queuesThe basic idea behind the use of stacks and queuesTreeTerminologyTypes of treesPractical examplesSummary
Sorting and Searching Algorithms
Introducing sorting algorithmsSwapping variables in PythonBubble sortUnderstanding the logic behind bubble sortOptimizing bubble sortPerformance analysis of the bubble sort algorithmInsertion sortPerformance analysis of the insertion sort algorithmMerge sortShell sortPerformance analysis of the Shell sort algorithmSelection sortPerformance analysis of the selection sort algorithmChoosing a sorting algorithmIntroduction to searching algorithmsLinear searchPerformance analysis of the linear search algorithmBinary searchPerformance analysis of the binary search algorithmInterpolation searchPerformance analysis of the interpolation search algorithmPractical applicationsSummary
Designing Algorithms
Introducing the basic concepts of designing an algorithmConcern 1: correctness: will the designed algorithm produce the result we expect?Concern 2: performance: is this the optimal way to get these results?Characterizing the complexity of the problemExploring the relationship between P and NPIntroducing NP-complete and NP-hardConcern 3 – scalability: how is the algorithm going to perform on larger datasets?The elasticity of the cloud and algorithmic scalabilityUnderstanding algorithmic strategiesUnderstanding the divide-and-conquer strategyA practical example – divide-and-conquer applied to Apache SparkUnderstanding the dynamic programming strategyComponents of dynamic programmingConditions for using dynamic programmingUnderstanding greedy algorithmsConditions for using greedy programmingA practical application – solving the TSPUsing a brute-force strategyUsing a greedy algorithmComparison of Three StrategiesPresenting the PageRank algorithmProblem definitionImplementing the PageRank algorithmUnderstanding linear programmingFormulating a linear programming problemDefining the objective functionSpecifying constraintsA practical application – capacity planning with linear programmingSummary
Graph Algorithms
Understanding graphs: a brief introductionGraphs: the backbone of modern data networksReal-world applicationsThe basics of a graph: vertices (or nodes)Graph theory and network analysisRepresentations of graphsGraph mechanics and typesEgo-centered networksBasics of egonetsOne-hop, two-hop, and beyondApplications of egonetsIntroducing network analysis theoryUnderstanding the shortest pathCreating a neighborhoodTrianglesDensityUnderstanding centrality measuresDegreeBetweennessFairness and closenessEigenvector centralityCalculating centrality metrics using Python1. Setting the foundation: libraries and data2. Crafting the graph3. Painting a picture: visualizing the graphSocial network analysisUnderstanding graph traversalsBFSConstructing the adjacency listBFS algorithm implementationUsing BFS for specific searchesDFSCase study: fraud detection using SNAIntroductionWhat is fraud in this context?Conducting simple fraud analyticsPresenting the watchtower fraud analytics methodologyScoring negative outcomesDegree of suspicionSummary
Section 2: Machine Learning Algorithms
Unsupervised Machine Learning Algorithms
Introducing unsupervised learningUnsupervised learning in the data-mining lifecyclePhase 1: Business understanding Phase 2: Data understandingPhase 3: Data preparationPhase 4: ModelingPhase 5: EvaluationPhase 6: DeploymentCurrent research trends in unsupervised learningPractical examplesMarketing segmentation using unsupervised learningUnderstanding clustering algorithmsQuantifying similaritiesEuclidean distanceManhattan distanceCosine distancek-means clustering algorithmThe logic of k-means clusteringInitializationThe steps of the k-means algorithmStop conditionCoding the k-means algorithmLimitation of k-means clusteringHierarchical clusteringSteps of hierarchical clusteringCoding a hierarchical clustering algorithmUnderstanding DBSCANCreating clusters using DBSCAN in PythonEvaluating the clustersApplication of clusteringDimensionality reductionPrincipal component analysisLimitations of PCAAssociation rules miningExamples of useMarket basket analysisAssociation rules miningTypes of rulesTrivial rulesInexplicable rulesActionable rulesRanking rulesSupportConfidenceLiftAlgorithms for association analysisApriori algorithmLimitations of the apriori algorithmFP-growth algorithmPopulating the FP-treeMining frequent patternsCode for using FP-growthSummary
Traditional Supervised Learning Algorithms
Understanding supervised machine learningFormulating supervised machine learning problemsUnderstanding enabling conditionsDifferentiating between classifiers and regressorsUnderstanding classification algorithmsPresenting the classifiers challengeThe problem statementFeature engineering using a data processing pipelineScaling the featuresEvaluating the classifiersConfusion matricesUnderstanding recall and precisionUnderstanding the recall and precision trade-offUnderstanding overfittingSpecifying the phases of classifiersDecision tree classification algorithmUnderstanding the decision tree classification algorithmThe strengths and weaknesses of decision tree classifiersUse casesUnderstanding the ensemble methodsImplementing gradient boosting with the XGBoost algorithmDifferentiating the Random Forest algorithm from ensemble boostingUsing the Random Forest algorithm for the classifiers challengeLogistic regressionAssumptionsEstablishing the relationshipThe loss and cost functionsWhen to use logistic regressionUsing the logistic regression algorithm for the classifiers challengeThe SVM algorithmUsing the SVM algorithm for the classifiers challengeUnderstanding the Naive Bayes algorithmBayes’ theoremCalculating probabilitiesMultiplication rules for AND eventsThe general multiplication ruleAddition rules for OR eventsUsing the Naive Bayes algorithm for the classifiers challengeFor classification algorithms, the winner is...Understanding regression algorithmsPresenting the regressors challengeThe problem statement of the regressors challengeExploring the historical datasetFeature engineering using a data processing pipelineLinear regressionSimple linear regressionEvaluating the regressorsMultiple regressionUsing the linear regression algorithm for the regressors challengeWhen is linear regression used?The weaknesses of linear regressionThe regression tree algorithmUsing the regression tree algorithm for the regressors challengeThe gradient boost regression algorithmUsing the gradient boost regression algorithm for the regressors challengeFor regression algorithms, the winner is...Practical example – how to predict the weatherSummary

Neural Network Algorithms
The evolution of neural networksHistorical backgroundAI winter and the dawn of AI springUnderstanding neural networksUnderstanding perceptronsUnderstanding the intuition behind neural networksUnderstanding layered deep learning architecturesDeveloping an intuition for hidden layersHow many hidden layers should be used?Mathematical basis of neural networkTraining a neural networkUnderstanding the anatomy of a neural networkDefining gradient descentActivation functionsStep functionSigmoid functionReLULeaky ReLUHyperbolic tangent (tanh)SoftmaxTools and frameworksKerasBackend engines of KerasLow-level layers of the deep learning stackDefining hyperparametersDefining a Keras modelChoosing a sequential or functional modelUnderstanding TensorFlowPresenting TensorFlow’s basic conceptsUnderstanding Tensor mathematicsUnderstanding the types of neural networksConvolutional neural networksConvolutionPoolingGenerative Adversarial NetworksUsing transfer learningCase study – using deep learning for fraud detectionMethodologySummary
Algorithms for Natural Language Processing
Introducing NLPUnderstanding NLP terminologyText preprocessing in NLPTokenizationCleaning dataCleaning data using PythonUnderstanding the Term Document MatrixUsing TF-IDFSummary and discussion of resultsIntroduction to word embeddingImplementing word embedding with Word2VecInterpreting similarity scoresAdvantages and disadvantages of Word2VecCase study: Restaurant review sentiment analysisImporting required libraries and loading the datasetBuilding a clean corpus: Preprocessing text dataConverting text data into numerical featuresAnalyzing the resultsApplications of NLPSummary
Understanding Sequential Models
Understanding sequential dataTypes of sequence modelsOne-to-manyMany-to-oneMany-to-manyData representation for sequential modelsIntroducing RNNsUnderstanding the architecture of RNNsUnderstanding the memory cell and hidden stateUnderstanding the characteristics of the input variableTraining the RNN at the first timestepThe activation function in actionTraining the RNN for a whole sequenceCalculating the output for each timestepBackpropagation through timePredicting with RNNsLimitations of basic RNNsVanishing gradient problemInability to look ahead in the sequenceGRUIntroducing the update gateImplementing the update gateUpdating the hidden cellRunning GRUs for multiple timestepsIntroducing LSTMIntroducing the forget gateThe candidate cell stateThe update gateCalculating memory stateThe output gatePutting everything togetherCoding sequential modelsLoading the datasetPreparing the dataCreating the modelTraining the modelViewing some incorrect predictionsSummary
Advanced Sequential Modeling Algorithms
The evolution of advanced sequential modeling techniquesExploring autoencodersCoding an autoencoderSetting up the environmentData preparationModel architectureCompilationTrainingPredictionVisualizationUnderstanding the Seq2Seq modelEncoderThought vectorDecoder or writerSpecial tokens in Seq2SeqThe information bottleneck dilemmaUnderstanding the attention mechanismWhat is attention in neural networks?Basic ideaExampleThree key aspects of attention mechanismsA deeper dive into attention mechanismsThe challenges of attention mechanismsDelving into self-attentionAttention weightsEncoder: bidirectional RNNsThought vectorDecoder: regular RNNsTraining versus inferenceTransformers: the evolution in neural networks after self-attentionWhy transformers shineA Python code breakdownUnderstanding the outputLLMsUnderstanding attention in LLMsExploring the powerhouses of NLP: GPT and BERT2018’s LLM pioneers: GPT and BERTUsing deep and wide models to create powerful LLMsBottom of FormSummary
Section 3: Advanced Topics
Recommendation Engines
Introducing recommendation systemsTypes of recommendation enginesContent-based recommendation enginesDetermining similarities in unstructured documentsCollaborative filtering recommendation enginesIssues related to collaborative filteringHybrid recommendation enginesGenerating a similarity matrix of the itemsGenerating reference vectors of the usersGenerating recommendationsEvolving the recommendation systemUnderstanding the limitations of recommendation systemsThe cold start problemMetadata requirementsThe data sparsity problemThe double-edged sword of social influence in recommendation systemsAreas of practical applicationsNetflix’s mastery of data-driven recommendationsThe evolution of Amazon’s recommendation systemPractical example – creating a recommendation engine1. Setting up the framework2. Data loading: ingesting reviews and titles3. Merging data: crafting a comprehensive view4. Descriptive analysis: gleaning insights from ratings5. Structuring for recommendations: crafting the matrix6. Putting the engine to test: recommending moviesFinding movies correlating with Avatar (2009)10,000 BC (2008) -0.075431 Understanding correlationEvaluating the modelRetraining over time: incorporating user feedbackSummary
Algorithmic Strategies for Data Handling
Introduction to data algorithmsSignificance of CAP theorem in context of data algorithmsStorage in distributed environmentsConnecting CAP theorem and data compressionPresenting the CAP theoremCA systemsAP systemsCP systemsDecoding data compression algorithmsLossless compression techniquesHuffman coding: Implementing variable-length codingUnderstanding dictionary-based compression LZ77Advanced lossless compression formatsPractical example: Data management in AWS: A focus on CAP theorem and compression algorithms1. Applying the CAP theorem2. Using compression algorithms3. Quantifying the benefitsSummary
Cryptography
Introduction to cryptographyUnderstanding the importance of the weakest linkThe basic terminologyUnderstanding the security requirementsStep 1: Identifying the entitiesStep 2: Establishing the security goalsStep 3: Understanding the sensitivity of the dataUnderstanding the basic design of ciphersPresenting substitution ciphersCryptanalysis of substitution ciphersUnderstanding transposition ciphersUnderstanding the types of cryptographic techniquesUsing the cryptographic hash functionImplementing cryptographic hash functionsAn application of the cryptographic hash functionChoosing between MD5 and SHAUsing symmetric encryptionCoding symmetric encryptionThe advantages of symmetric encryptionThe problems with symmetric encryptionAsymmetric encryptionThe SSL/TLS handshaking algorithmPublic key infrastructureBlockchain and cryptographyExample: security concerns when deploying a machine learning modelMITM attacksHow to prevent MITM attacksAvoiding masqueradingData and model encryptionSummary
Large-Scale Algorithms
Introduction to large-scale algorithmsCharacterizing performant infrastructure for large-scale algorithmsElasticityCharacterizing a well-designed, large-scale algorithmLoad balancingELB: Combining elasticity and load balancingStrategizing multi-resource processingUnderstanding theoretical limitations of parallel computingAmdahl’s lawDeriving Amdahl’s lawCUDA: Unleashing the potential of GPU architectures in parallel computingBottom of formParallel processing in LLMs: A case study in Amdahl’s law and diminishing returnsRethinking data localityBenefiting from cluster computing using Apache SparkHow Apache Spark empowers large-scale algorithm processingDistributed computingIn-memory processingUsing large-scale algorithms in cloud computingExampleSummary
Practical Considerations
Challenges facing algorithmic solutionsExpecting the unexpectedFailure of Tay, the Twitter AI botThe explainability of an algorithmMachine learning algorithms and explainabilityPresenting strategies for explainabilityUnderstanding ethics and algorithmsProblems with learning algorithmsUnderstanding ethical considerationsFactors affecting algorithmic solutionsConsidering inconclusive evidenceTraceabilityMisguided evidenceUnfair outcomesReducing bias in modelsWhen to use algorithmsUnderstanding black swan events and their implications on algorithmsSummary
Other Books You May Enjoy
Index

Content preview from 50 Algorithms Every Programmer Should Know - Second Edition

3 Sorting and Searching Algorithms

In this chapter, we will look at the algorithms that are used for sorting and searching. This is an important class of algorithms that can be used on their own or can become the foundation for more complex algorithms. These include Natural Language Processing (NLP) and pattern-extracting algorithms. This chapter starts by presenting different types of sorting algorithms. It compares the performance of various approaches to designing a sorting algorithm. Then, some searching algorithms are presented in detail. Finally, a practical example of the sorting and searching algorithms presented in this chapter is studied.

By the end of this chapter, we should be able to understand the various algorithms that are used ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

40 Algorithms Every Programmer Should Know

Publisher Resources

ISBN: 9781803247762

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

50 Algorithms Every Programmer Should Know - Second Edition

by Imran Ahmad

3

Sorting and Searching Algorithms

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.