Basics of Programming and Algorithms, Principles and Applications

✍ Scribed by Roberto Mantaci; Jean-Baptiste Yunès

• Publisher: Springer Nature Switzerland
• Year: 2024
• Tongue: English
• Leaves: 365
• Category: Library

✦ Table of Contents

Preface
Thanks
Organizations
People
Special Thanks
About This Book
Notations
Solutions
Solution to Exercise 1
Contents
Part I Python Programming
1 Introduction
2 First Steps in Python
2.1 Interactive Mode
2.2 Arithmetic, Types
2.2.1 Integers and Floating Point Numbers
2.2.2 Types Everywhere
2.2.3 Some Mathematical Functions
2.3 Variables
2.3.1 Identifiers
2.3.2 Definition and Assignment
2.3.3 Deletion of a Variable
2.3.4 Empty Variable, None
2.4 Statements
2.4.1 Sequential Composition
2.4.2 Compound Assignments
2.5 Booleans
2.6 Solutions to Exercises
Solution of Exercise 2.1
Solution of Exercise 2.2
Solution of Exercise 2.6
Solution of Exercise 2.8
Solution of Exercise 2.12
3 Programs
3.1 Programs
3.2 Sequence
3.2.1 Flowchart of a Sequence
3.3 Iteration, the for
3.4 Input
3.5 Strings
3.6 Alternative, the if
3.7 Conditional Loop, the while
3.8 Early Exits and Continuations in Loops
3.8.1 Early Exit, the break
3.8.2 Early Continuation, the continue
3.9 Solutions to Exercises
Solution to Exercise 3.1
Solution to Exercise 3.2
Solution to Exercise 3.4
Solution to Exercise 3.5
Solution to Exercise 3.6
Solution to Exercise 3.7
Solution to Exercise 3.8
4 Functions and Recursion
4.1 Functions
4.1.1 Parameters
4.1.2 Local Variables
4.1.3 Returning a Value
4.1.4 Error Handling
4.1.5 Exception Handling
4.1.6 Closure
4.1.6.1 Reading a Variable Outside'' 4.1.6.2 Modifying a VariableOutside''
4.1.7 Variable Hiding
4.1.8 Documenting a Function
4.2 Modules
4.3 More on Parameters
4.3.1 Default Values
4.3.2 Positional and Keyword Arguments
4.4 Recursion
4.4.1 Loops vs Recursion
4.5 Solutions to Exercises
Solution to Exercise 4.1
Solution to Exercise 4.2
Solution to Exercise 4.3
Solution to Exercise 4.5
Solution to Exercise 4.7
Solution to Exercise 4.8
Solution to Exercise 4.9
5 Data Structures
5.1 Tuples
5.1.1 Tuples as Parameters or Return Value
5.1.1.1 Error Handling with Tuples
5.1.2 Length of a Tuple
5.1.3 Labeled Tuples
5.2 Arrays/Lists
5.2.1 List Concatenation
5.2.2 Access to Elements
5.2.3 Modification of Elements
5.2.4 Insertion and Removal of Elements
5.2.4.1 List as Stack
5.2.4.2 List as Queue
5.2.4.3 Removal of an Element
5.2.4.4 Tests
5.2.4.5 Other Operations on Lists
5.2.5 More on Accessing and Slicing
5.3 Variables, Objects and Values
5.4 More on Tuples, Lists, Strings: Sequences
5.5 More on Lists: Comprehension
5.6 Dictionaries
5.6.1 Iterating over Dictionaries
5.7 Objects
5.7.1 Methods
5.7.2 Printing
5.8 Solutions to Exercises
Solution to Exercise 5.1
Solution to Exercises 5.2 and 5.3
Solution to Exercise 5.4
Solution to Exercise 5.5
Solution to Exercise 5.6
Solution to Exercise 5.8
Solution to Exercise 5.9
Solution to Exercise 5.10
Solution to Exercise 5.11
Solution to Exercise 5.15
6 Drawings and More
6.1 Measuring Time
6.1.1 Wall Clock
6.1.2 CPU Clock
6.2 Counting Operations
6.3 Drawing
6.3.1 Generate an Image File
6.3.2 Picture Properties
6.3.3 Drawing Several Functions
6.3.4 Scaling Axis
6.4 File Handling
6.4.1 Writing
6.4.2 Reading
6.5 Random Numbers
6.6 Solutions to Exercises
Solution to Exercise 6.2
Solution to Exercise 6.4
Solution to Exercise 6.5
Solution to Exercise 6.7
Solution to Exercise 6.8
Solution to Exercise 6.9
Part II Algorithms
7 Algorithm Performance
7.1 Complexity in Time and Space
7.1.1 Time Complexity
7.1.2 Space Complexity
7.2 Complexity Functions (for Time Complexity)
7.2.1 A First Example: The Sum of Entries of an Array
7.2.2 Another Example: The Minimum Element of an Array
7.3 Asymptotic Notations of O, Θ and Ω
7.3.1 Notation O (big-O)
7.3.2 Notation Θ (big-theta)
7.3.3 Notation Ω (big-omega)
7.4 Evaluating the Complexity of Algorithms
7.4.1 Sequential Blocks
7.4.2 Loops
7.4.3 Examples
7.5 Solutions to Exercises
Solution of Exercise 7.2
Solution of Exercise 7.3
Solution of Exercise 7.7
Solution of Exercise 7.8
Solution of Exercise 7.9
Solution of Exercise 7.12
Solution of Exercise 7.14
Solution of Exercise 7.15
Solution of Exercise 7.16
8 Introduction to Recursion
8.1 Factorial
8.1.1 Space Complexity of Recursive Algorithms, Tree of Recursive Calls
8.2 Exponentiation
8.3 Searching
8.3.1 Naive Search
8.3.2 Binary Search
8.4 Fibonacci Numbers
8.5 Solution for Exercises
Solution of Exercise 8.1
Solution of Exercise 8.3
Solution to Exercise 8.4
Solution to Exercise 8.6
Solution to Exercise 8.7
Solution to Exercise 8.8
Solution to Exercise 8.9
Solution to Exercise 8.11
9 The Sorting Problem
9.1 Selection Sort
9.1.1 Complexity of Selection Sort
9.2 Insertion Sort
9.2.1 Complexity of Insertion Sort
9.3 Merge Sort
9.3.1 Time Complexity of Merge and Merge Sort
9.3.2 Space Complexity and Other Features of Merge Sort
9.4 Quick Sort
9.4.1 Complexity of Quick Sort
9.5 Is n logn Optimal?
9.6 Sorting in Linear Time
9.6.1 Counting Sort
9.6.2 Radix Sort
9.6.3 Bucket Sort
9.7 Solutions to Exercices
Solution to Exercise 9.4
Solution to Exercise 9.6
Solution to Exercise 9.7
Solution to Exercise 9.12
Solution to Exercise 9.13
10 More on Recursion
10.1 Divide and Conquer Algorithms and the Master Theorem
10.2 More Divide and Conquer Algorithms
10.2.1 Minimum of an Array
10.2.2 Longest Freezing Period
10.2.3 Karatsuba's Multiplication
10.2.4 Stooge Sort
10.3 Dynamic Programming
10.3.1 Memoisation (Top Down)
10.3.2 Tabulation (Bottom-Up)
10.3.3 Binomial Coefficients
10.3.4 On the Order of the Filling of the Memoisation Table
10.4 Tail Recursion
10.5 Solutions to Exercises
Solution of Exercise 10.1
Solution of Exercise 10.3
Solution of Exercise 10.4
Solution of Exercise 10.5
Solution of Exercise 10.6
11 Trees as Data Structures
11.1 Definitions
11.1.1 Key Components and Basic Properties of a Tree
11.2 Implementation of Trees in Memory
11.2.1 Implementations by Arrays
11.2.2 Implementation by References/Pointers
11.2.2.1 The Arity of the Tree Is Known
11.2.2.2 The Arity of the Tree Is not Known, the Left-Child Right-Sibling Implementation
11.2.3 The .parent Attribute
11.3 Tree Traversal
11.3.1 Depth-First Traversal
11.3.1.1 Pre-order
11.3.1.2 Post-order
11.3.1.3 In-order
11.3.2 Breadth-First Traversal
11.4 Recursive Functions on Trees
11.4.1 Computation of the Size of a Tree
11.4.2 Computation of the Height
11.4.3 Another Exemple
11.5 Heaps and Priority Queues
11.5.1 Definition of Heaps
11.5.2 Implications on Heap Implementation in Memory
11.5.3 Insert and MinRemoval in Heaps
11.5.4 A Step Back to the Aspect of the Implementation
11.5.5 Insertion in a Heap
11.5.6 MinRemoval in a Heap
11.5.6.1 An Example of MinRemoval on the Array Content
11.6 Binary Search Trees (BST)
11.6.1 BST Definition
11.6.2 Testing That a Binary Tree Is a BST
11.6.3 Search in a BST
11.6.4 Insertion in a BST
11.6.5 Deletion in a BST
11.6.5.1 The Element x Is in a Leaf
11.6.5.2 The Element x Is in a Node N with Only One Child
11.6.5.3 The Element x Is in a Node with Two Children
11.6.5.4 Analysis of the Complexity of DeletionBST
11.7 AVL Trees
11.7.1 Definition and Properties
11.7.2 Rotations
11.7.3 Rebalancing
11.7.4 Complexity and Implementation Issues
11.7.5 Insertions in AVL
11.7.6 Deletions in AVL
11.8 Solutions to Exercises
Solution of Exercise 11.1
Solution of Exercise 11.8
Solution of Exercise 11.20
Solution of Exercise 11.28
12 Hashing
12.1 Separate Chaining
12.2 Hashing with Open Addressing
12.2.1 Insertion in Tables with Opening Addressing
12.2.2 Searching in Tables with Opening Addressing
12.2.3 Deletion in Tables with Opening Addressing
12.2.4 Complexity of Search, Insertion and Deletion with Open Addressing
List of Figures
List of Python Interactive Sessions (REPL)
List of Programs
List of Algorithms
References
Index