Subscribe to DSC Newsletter

Free book – for #datascience interviews - Guide to competitive programming

Recently Springer made some good books on maths free to download.

Competitive programming strategies are useful for many data science interviews and they help to improve your maths foundations.  There are not many books on this subject (although there are many good websites and YouTube resources).

So, I hope you find this book useful

From the book

  • Competitive programming combines two topics: the design of algorithms and the implementation of algorithms.
  • Design of Algorithms The core of competitive programming is about inventing efficient algorithms that solve well-defined computational problems.
  • The design of algorithms requires problem solving and mathematical skills. Often a solution to a problem is a combination of well-known methods and new insights.
  • Mathematics plays an important role in competitive programming. Actually, there are no clear boundaries between algorithm design and mathematics.
  • The most common language for the implementation of competitive algorithms is C++

 

The book contents are

 Programming Techniques                                   

Language Features                                    

Input and Output                               

Working with Numbers                          

Shortening Code                               

Recursive Algorithms                                  

Generating Subsets                             

Generating Permutations                         

Backtracking                                  

Bit Manipulation                                     

Bit Operations                                 

Representing Sets                              

 

 Efficiency                                                

 Time Complexity                                     

 Calculation Rules                              

 Common Time Complexities                     

 Estimating Efficiency                           

 Formal Definitions                             

 Examples                                           

 Maximum Subarray Sum                        

 Two Queens Problem                           

 

 Sorting and Searching                                     

 Sorting Algorithms                                    

 Bubble Sort                                   

vii

 Merge Sort                                   

 Sorting Lower Bound                           

 Counting Sort                                 

 Sorting in Practice                              

 Solving Problems by Sorting                            

 Sweep Line Algorithms                          

 Scheduling Events                              

 Tasks and Deadlines                            

 Binary Search                                        

 Implementing the Search                         

 Finding Optimal Solutions                       

 

 Data Structures                                           

 Dynamic Arrays                                      

 Vectors                                      

 Iterators and Ranges                            

 Other Structures                               

 Set Structures                                        

 Sets and Multisets                              

 Maps                                        

 Priority Queues                                

 Policy-Based Sets                              

 Experiments                                         

 Set Versus Sorting                             

 Map Versus Array                             

 Priority Queue Versus Multiset                    

 

 Dynamic Programming                                    

 Basic Concepts                                       

 When Greedy Fails                             

 Finding an Optimal Solution                      

 Counting Solutions                             

 Further Examples                                     

 Longest Increasing Subsequence                   

 Paths in a Grid                                

 Knapsack Problems                             

 From Permutations to Subsets                     

 Counting Tilings                               

 

 Graph Algorithms                                         

 Basics of Graphs                                     

 Graph Terminology                             

 Graph Representation                           

 Graph Traversal                                      

 Depth-First Search                             

viii Contents

 Breadth-First Search                            

 Applications                                  

 Shortest Paths                                        

 Bellman–Ford Algorithm                        

 Dijkstra’s Algorithm                            

 Floyd–Warshall Algorithm                       

 Directed Acyclic Graphs                               

 Topological Sorting                             

 Dynamic Programming                          

 Successor Graphs                                     

 Finding Successors                             

 Cycle Detection                                

 Minimum Spanning Trees                              

 Kruskal’s Algorithm                            

 Union-Find Structure                            

 Prim’s Algorithm                              

 

 Algorithm Design Topics                                   

 Bit-Parallel Algorithms                                 

 Hamming Distances                            

 Counting Subgrids                             

 Reachability in Graphs                          

 Amortized Analysis                                   

 Two Pointers Method                           

 Nearest Smaller Elements                        

 Sliding Window Minimum                       

 Finding Minimum Values                               

 Ternary Search                                

 Convex Functions                              

 Minimizing Sums                              

 

 Range Queries                                            

 Queries on Static Arrays                               

 Sum Queries                                  

 Minimum Queries                              

 Tree Structures                                       

 Binary Indexed Trees                           

 Segment Trees                                

 Additional Techniques                          

 

 Tree Algorithms                                          

 Basic Techniques                                     

 Tree Traversal                                 

 Calculating Diameters                           

 All Longest Paths                              

Contents ix

 Tree Queries                                         

 Finding Ancestors                              

 Subtrees and Paths                             

 Lowest Common Ancestors                      

 Merging Data Structures                         

 Advanced Techniques                                 

 Centroid Decomposition                         

 Heavy-Light Decomposition                      

 

 Mathematics                                             

 Number Theory                                      

 Primes and Factors                             

 Sieve of Eratosthenes                           

 Euclid’s Algorithm                             

 Modular Exponentiation                         

 Euler’s Theorem                               

 Solving Equations                              

 Combinatorics                                       

 Binomial Coefficients                           

 Catalan Numbers                               

 Inclusion-Exclusion                             

 Burnside’s Lemma                             

 Cayley’s Formula                              

 Matrices                                            

 Matrix Operations                              

 Linear Recurrences                             

 Graphs and Matrices                            

 Gaussian Elimination                           

 

 Probability                                          

 Working with Events                           

 Random Variables                              

 Markov Chains                                

 Randomized Algorithms                         

 Game Theory                                        

 Game States                                  

 Nim Game                                   

 Sprague–Grundy Theorem                       

 

 Advanced Graph Algorithms                                

 Strong Connectivity                                   

 Kosaraju’s Algorithm                           

 SAT Problem                                

 Complete Paths                                      

 Eulerian Paths                                 

x Contents

 Hamiltonian Paths                              

 Applications                                  

 Maximum Flows                                     

 Ford–Fulkerson Algorithm                       

 Disjoint Paths                                 

 Maximum Matchings                           

 Path Covers                                   

 Depth-First Search Trees                               

 Biconnectivity                                 

 Eulerian Subgraphs                             

 

 Geometry                                                

 Geometric Techniques                                 

 Complex Numbers                             

 Points and Lines                               

 Polygon Area                                 

 Distance Functions                             

 Sweep Line Algorithms                                

 Intersection Points                              

 Closest Pair Problem                            

 Convex Hull Problem                           

 

 String Algorithms                                         

 Basic Topics                                         

 Trie Structure                                 

 Dynamic Programming                          

 String Hashing                                       

 Polynomial Hashing                            

 Applications                                  

 Collisions and Parameters                        

 Z-Algorithm                                         

 Constructing the Z-Array                        

 Applications                                  

 Suffix Arrays                                        

 Prefix Doubling Method                         

 Finding Patterns                               

 LCP Arrays                                   

 

 Additional Topics                                         

 Square Root Techniques                                

 Data Structures                                

 Subalgorithms                                 

 Integer Partitions                               

 Mo’s Algorithm                               

Contents xi

 Segment Trees Revisited                               

 Lazy Propagation                              

 Dynamic Trees                                

 Data Structures in Nodes                        

 Two-Dimensional Trees                         

 Treaps                                             

 Splitting and Merging                           

 Implementation                                

 Additional Techniques                          

 Dynamic Programming Optimization                      

 Convex Hull Trick                             

 Divide and Conquer Optimization                  

 Knuth’s Optimization                           

 Miscellaneous                                        

 Meet in the Middle                             

 Counting Subsets                              

 Parallel Binary Search                           

 Dynamic Connectivity                           

Appendix A: Mathematical Background    

link to download https://link.springer.com/book/10.1007/978-3-319-72547-5 

 

 

                       

Views: 2751

Comment

You need to be a member of Data Science Central to add comments!

Join Data Science Central

Comment by Kwai Leung on June 27, 2020 at 5:13pm

It works. Thank you.

Comment by ajit jaokar on June 27, 2020 at 12:15pm
Comment by Hani Patel on June 27, 2020 at 12:15pm

https://link.springer.com/book/10.1007/978-3-319-72547-5 - This is the link from where I downloaded. @kwaiLeung 

Comment by Kwai Leung on June 27, 2020 at 9:05am

Where can I click and download this book? Thank you.

Videos

  • Add Videos
  • View All

© 2020   Data Science Central ®   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service