Log In
Or create an account ->
Imperial Library
Home
About
News
Upload
Forum
Help
Login/SignUp
Index
Halftitle
Title
Copyright
Table of Contents
Preface
List of Figures
List of Tables
List of Listings
Chapter 1 ▪ Basic Concepts of Recursive Programming
1.1 Recognizing recursion
1.2 Problem decomposition
1.3 Recursive code
1.4 Induction
1.4.1 Mathematical proofs by induction
1.4.2 Recursive leap of faith
1.4.3 Imperative vs. declarative programming
1.5 Recursion vs. iteration
1.6 Types of recursion
1.6.1 Linear recursion
1.6.2 Tail recursion
1.6.3 Multiple recursion
1.6.4 Mutual recursion
1.6.5 Nested recursion
1.7 Exercises
Chapter 2 ▪ Methodology for Recursive Thinking
2.1 Template for designing recursive algorithms
2.2 Size of the problem
2.3 Base cases
2.4 Problem decomposition
2.5 Recursive cases, induction, and diagrams
2.5.1 Thinking recursively through diagrams
2.5.2 Concrete instances
2.5.3 Alternative notations
2.5.4 Procedures
2.5.5 Several subproblems
2.6 Testing
2.7 Exercises
Chapter 3 ▪ Runtime Analysis of Recursive Algorithms
3.1 Mathematical preliminaries
3.1.1 Powers and logarithms
3.1.2 Binomial coefficients
3.1.3 Limits and L’Hopital’s rule
3.1.4 Sums and products
3.1.5 Floors and ceilings
3.1.6 Trigonometry
3.1.7 Vectors and matrices
3.2 Computational time complexity
3.2.1 Order of growth of functions
3.2.2 Asymptotic notation
3.3 Recurrence relations
3.3.1 Expansion method
3.3.2 General method for solving difference equations
3.4 Exercises
Chapter 4 ▪ Linear Recursion I: Basic Algorithms
4.1 Arithmetic operations
4.1.1 Power function
4.1.2 Slow addition
4.1.3 Double sum
4.2 Base conversion
4.2.1 Binary representation of a nonnegative integer
4.2.2 Decimal to base b conversion
4.3 Strings
4.3.1 Reversing a string
4.3.2 Is a string a palindrome?
4.4 Additional problems
4.4.1 Selection sort
4.4.2 Horner’s method for evaluating polynomials
4.4.3 A row of Pascal’s triangle
4.4.4 Ladder of resistors
4.5 Exercises
Chapter 5 ▪ Linear Recursion II: Tail Recursion
5.1 Boolean functions
5.1.1 Does a nonnegative integer contain a particular digit?
5.1.2 Equal strings?
5.2 Searching algorithms for lists
5.2.1 Linear search
5.2.2 Binary search in a sorted list
5.3 Binary search trees
5.3.1 Searching for an item
5.3.2 Inserting an item
5.4 Partitioning schemes
5.4.1 Basic partitioning scheme
5.4.2 Hoare’s partitioning method
5.5 The quickselect algorithm
5.6 Bisection algorithm for root finding
5.7 The woodcutter problem
5.8 Euclid’s algorithm
5.9 Exercises
Chapter 6 ▪ Multiple Recursion I: Divide and Conquer
6.1 Is a list sorted in ascending order?
6.2 Sorting
6.2.1 The merge sort algorithm
6.2.2 The quicksort algorithm
6.3 Majority element in a list
6.4 Fast integer multiplication
6.5 Matrix multiplication
6.5.1 Divide and conquer matrix multiplication
6.5.2 Strassen’s matrix multiplication algorithm
6.6 The Tromino Tiling Problem
6.7 The skyline problem
6.8 Exercises
Chapter 7 ▪ Multiple Recursion II: Puzzles, Fractals, and More...
7.1 Swamp traversal
7.2 Towers of Hanoi
7.3 Tree traversals
7.3.1 Inorder traversal
7.3.2 Preorder and postorder traversals
7.4 Longest palindrome substring
7.5 Fractals
7.5.1 Koch snowflake
7.5.2 Sierpiński’s carpet
7.6 Exercises
Chapter 8 ▪ Counting Problems
8.1 Permutations
8.2 Variations with repetition
8.3 Combinations
8.4 Staircase climbing
8.5 Manhattan paths
8.6 Convex polygon triangulations
8.7 Circle pyramids
8.8 Exercises
Chapter 9 ▪ Mutual Recursion
9.1 Parity of a number
9.2 Multiplayer games
9.3 Rabbit population growth
9.3.1 Adult and baby rabbit pairs
9.3.2 Rabbit family tree
9.4 Water treatment plants puzzle
9.4.1 Water flow between cities
9.4.2 Water discharge at each city
9.5 Cyclic towers of Hanoi
9.6 Grammars and recursive descent parsers
9.6.1 Tokenization of the input string
9.6.2 Recursive descent parser
9.7 Exercises
Chapter 10 ▪ Program Execution
10.1 Control flow between subroutines
10.2 Recursion trees
10.2.1 Runtime analysis
10.3 The program stack
10.3.1 Stack frames
10.3.2 Stack traces
10.3.3 Computational space complexity
10.3.4 Maximum recursion depth and stack overflow errors
10.3.5 Recursion as an alternative to a stack data structure
10.4 Memoization and dynamic programming
10.4.1 Memoization
10.4.2 Dependency graph and dynamic programming
10.5 Exercises
Chapter 11 ▪ Tail Recursion Revisited and Nested Recursion
11.1 Tail recursion vs. iteration
11.2 Tail recursion by thinking iteratively
11.2.1 Factorial
11.2.2 Decimal to base b conversion
11.3 Nested recursion
11.3.1 The Ackermann function
11.3.2 The McCarthy 91 function
11.3.3 The digital root
11.4 Tail and nested recursion through function generalization
11.4.1 Factorial
11.4.2 Decimal to base b conversion
11.5 Exercises
Chapter 12 ▪ Multiple Recursion III: Backtracking
12.1 Introduction
12.1.1 Partial and complete solutions
12.1.2 Recursive structure
12.2 Generating combinatorial entities
12.2.1 Subsets
12.2.2 Permutations
12.3 The n-queens problem
12.3.1 Finding every solution
12.3.2 Finding one solution
12.4 Subset sum problem
12.5 Path through a maze
12.6 The sudoku puzzle
12.7 0-1 knapsack problem
12.7.1 Standard backtracking algorithm
12.7.2 Branch and bound algorithm
12.8 Exercises
Further reading
Index
← Prev
Back
Next →
← Prev
Back
Next →