CLRS Exercises 2.3-4 Recursive insertion sort

Problem:

Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1 n],
we recursively sort A[1 n -1] and then insert A[n] into the sorted array A[1 n - 1]. Write a
recurrence for the running time of this recursive version of insertion sort.

Solution:

1. Initially the array size will be n
2. call insertionsort function until the size becomes 1
3. then start the normal insertion approach as shown in code

T(n) = T(n-1) + 1 +  O(n) = O(n^2)

Complexity: O(n^2) TC
Code:

Reverse a Linked List recursively

Robot in an NXN grid

Problem:

Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot?
FOLLOW UP
Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.

Solution:

• Start from (0,0)
• Robot can take right? i.e in boundary and cell is not marked as "off limits"
• Then take right
• Robot can take left? i.e in boundary and cell is not marked as "off limits"
• Then take left
• Do these steps recursively until destination is found or no path is found.
• return possible steps.

It can be derived in mathematical way as follows:

Result will be like this,

1 + (1+2) + (1+2+3) + (1+2+3+4) + ... + (1+2+3+4+..+N)
which can be written as,









Finally, it can be expressed as follows,


Complexity: O(N^2)
Code: