Insert Operation in BST using Recursion

Searching in a Binary Search Tree

Stitching Videos Using FFMPEG

1. On Mac 10.13.6 (17G12034). To install ffmpeg:

brew install ffmpeg

2. Create the stitch.txt with files to be stitched. The command needs a slight modification to avoid silent video:

ffmpeg -f concat -safe 0 -i stitch.txt -c:v copy adjacent-duplicates-f.mp4

Tree Depth using Recursion

Tree traversals using Recursion

Binary Search using Recursion

Problem Solving Tools

The three important problem solving tools are:

1. Data Models
2. Data Structures
3. Algorithms

Data models are abstractions used to describe problems. Graphs is an example of a data model.

Use abstractions to formulate solutions to problems. For example, graphs are a way to model data and provide data abstraction to manipulate data effectively to solve problems.

Data structures are programming language constructs used to represent data models. For example, built-in abstractions such as structs and pointers. This can be used to construct data structures to represent complex abstractions such as graphs.

Algorithms are techniques used to obtain solutions by manipulating data as represented by the abstractions of a data model, by data structures or by other means.

Linear Search using Recursion

Fibonacci Sequence

Factorial Using Recursion

Equal Strings using Recursion

Contains Digit using Recursion

Find Largest Number Using Recursion

Print Digits in Reverse using Recursion

Palindrome using Recursion

Reverse String using Recursion

Square Root using Recursion

Guessing Game

Sum Digits using Recursion

Power Function using Recursion

Questions on N Queens Problem

1. Why matrix is inefficient?
2. How is recursive calls made in preorder traversal of the tree?
3. How to generate all of the permutations and all of the subsets of n distinct elements?
4. Print all of the subsets of the elements in a list. Input: [a, b, c]
5. Which part of the code does backtracking?
6. What does the solution space tree look like?
7. Why it is DP? Does it satisfy optimality? Subproblem?
8. When to use backtracking?
9. How call stacks are called with for loop? What is returned?
10. What happens when we backtrack?
11. How to determine the base case?
12. What is the time complexity?
13. What is the space complexity?
14. What data structures to use?
15. How to check if a position is in a diagonal?
16. How to identify a backtracking problem?
17. When do we stop making choices?
18. When does the undo happen? (only when the choice is invalid?)
19. How many wrapper functions do we need? What parameters are needed?
20. What are the subproblems?

Even Number using Recursion

Remainder using Recursion

Array Sum using Recursion

Summation using Recursion

Division using Recursion

Multiplication using Recursion

Addition using Recursion

Mastering Recursion Course Outline for Module 1

## 1. Head and Tail Recursion

- How to replace a loop with recursion?
- What is head recursion?
- What is tail recursion?
- Differences between head and tail recursion?
- Tail recursion call tree
- Head recursion call tree

## 2. Addition

- How to find base cases?
- Problem decomposition
- How to determine the size of the problem?
- Recursion diagram as a tool to design recursive programs
- What to do in the combine step?
- How to find the recursive case?
- Mathematical representation of recursive function
- How choice of reduction affects performance
- Recursive rule for efficient solution
- Translating mathematical function into recursive code

## 3. Multiplication

- How to derive recurrence relation?
- How to reassemble the result of subproblems to get the result for original problem?
- Improving the efficiency of the recursive solution
- How to determine the number of base cases?

## 4. Division

- Using a counter
- How to create a trace table
- Concrete case analysis using recursion diagram
- Reducing the problem size by more than one unit
- Recognize implicit counter in recursive code

## 5. Summation

- Expressing the problem mathematically
- Determine the size of the problem
- Using induction in the recursion diagram
- Translating recursion diagram into recursive solution
- Comparison of iterative and recursive solutions
- Recursion call stack
- Time and space complexity
- Linear recursion

## 6. Array Sum

- How data handled by base case affects recursive case
- Choosing what to reduce when you have many options
- Trace table showing the computations occurring when recursive calls terminate

## 7. Modulo

- Deriving equation to solve a problem
- Time complexity for equation based implementation
- Solving the problem by hand (brute force)
- Solving the problem by translating manual steps to iterative code
- Recognizing nothing to be done in combine step using recursion diagram
- Trivial combine step in recursion leads to tail recursion
- Comparison of iterative and recursive solution to see how terminating condition maps to base case, result and reduced value are the same in this case

## 8. Even

- Without using % operator
- Time and space complexity
 - Iterative Solution
    - Using multiply and divide
- Recursion diagram
- Recursive solution
- Fixing stack overflow error
- Reduction step
- Trivial combine step
- Tail recursion
- Two base cases
- How many base cases are required?
- Time and space complexity
- Linear recursion

## 9. Exponent

- Powers of 2 (warmup)
- Exponentiation operator
- Implement without using exponentiation operator
- Iterative solution
- Product accumulator
- Powers of a given base
- Recursive implementation in linear time
- Size of the problem
- Base cases
- Reduce and combine
- Allow negative integer exponents
- Problem decomposition
- Recursive case
- Relationship between reduction step and base case
- Function to express recursive case
- Multiple recursive cases
- Powers in logarithmic time
- Handling multiple cases and its effect on recursion diagram
- Recursive function with multiple recursive cases
- Direct translation of mathematical function to code

## 10. Sum Digits

- Extracting right most digit
- Chopping off right most digit
- Iterative solution
- Accumulator variable
- Time and space complexity
- Recursion diagram
- Reduce and combine
- Problem decomposition
- Recursive solution
- Time and space complexity

## 11. Guess a Number Game

- Game
- Computational complexity
- Derive the time complexity

## 12. Square Root

- Iterative solution
- Recursive solution using a wrapper function
- Comparison of iterative and recursive function
- Using bisection to improve performance

## 13. Reverse a String

- Recursive solution
- Multiple options in reduction step
- Combine step requires language builtin function
- Performance implications of concatenating strings
- Iteration solution using inplace modification of string
- Using two pointers
- Recursive solution with string inplace modification
- Using a wrapper function

## 14. Palindrome

- Problem size
- Multiple base cases
- Using two pointers
- Comparison with reverse a string problem
- Problem decomposition and its relationship to base cases
- Recursive solution

## 15. Print digits in reverse

- Prerequisites : Head and tail recursion, Add digits
- Size of the problem
- Base case
- Problem decomposition
- Recursion diagram: Reduction and combination
- Recursive solution

## 16. Find largest

- Problem decomposition
- Recursion diagram
- Combine step is a custom function
- Reducing by half
- Recursive function
- Two recursive calls
- Recursive solution
- Comparison of two versions

## 17. Contains Digit

- Problem Statement
- Program interface
- Assumption on input
- Linear recursive algorithm
- Recursion diagram
- Tail recursive algorithm
- Short circuit evaluation
- Relationship between base cases and recursive case
- One base case vs Two base cases
- Time complexity
- Similar problem

## 18. Equal Strings

- Interface (input and output)
- Base case
- Size of the problem
- Linear recursive algorithm
- Recursion diagram
- Problem decomposition
- Boolean function
- Recursive solution
- Tail recursive algorithm
- Short circuit evaluation
- Recursion diagram
- Comparison of linear and recursive solution

## 19. Factorial

- Problem definition
- Mathematical representation
- Translating mathematical function to recursive code
- Recurrence relation
- Deferred operation
- Subproblem with reduced argument
- Minimizing base cases
- Iterative solution
- Product accumulator
- Factorial call trace
- Factorial call and return table
- Pending multiplication direction
- Stack growth
- Time and space complexity
- Comparison of iterative and tail recursive solution

## 20 Fibonacci

- Problem Statement
- Recursive solution
- Two base cases
- Two recursive calls
- Recursive call tree
- Redundant calculations
- Binary Tree
 - Level and number of nodes
 - Total number of nodes
- Binary recursion runtime
- Improving performance by dynamic programming
- Time and space complexity
- Iterative solution
- Time and space complexity

Head and Tail Recursion

Division using Recursion

Outline

• Using a counter
• How to create a trace table
• Concrete case analysis using recursion diagram
• Reducing the problem size by more than one unit
• Recognize implicit counter in recursive code

Multiplication using Recursion