Introduction to Algorithms
Week 7: Exercises

1. Recursive Orange

Write a recursive function orange(n) that prints the word 'orange' n times.

2. Recursive Power

Write a recursive function isPowOfTwo(n) that returns True if n is a power of 2.

3. Recursive Count

Write a recursive function count(x, l) that returns the number of times that x occurs in the given list.

4. Recursive Multiplication

Write a recursive function mul(a, b) that returns the product (a * b) for positive integers a and b. You may use the built-in addition operator (+), but not the multiplication operator (*).

5. Recursive Largest Element

Write a recursive function largest(l) that returns the largest element in a list.

6. Recursive I/O Reverse

Write a recursive procedure reverse() that reads a series of lines until the end of the input, and write the lines out in reverse order. Do not use any loops or lists.

7. Recursive Pos

Write a recursive function pos(s, c) that returns the first index at which the character c appears in the string s, or None if none.

8. Recursive Reverse

Write a recursive function reverse(s): string that reverses the string s. You may use string concatenation, but may not call any library functions.

9. Recursive Palindrome

Write a recursive function that determines whether a string is a palindrome.

10. Recursive Compare

Use recursion to write a function sameAsFirst(a) that returns the number of integers in an array that are equal to its first element.

11. Array Writes

Suppose that we run a sorting algorithm on an array that is already sorted. How many array writes will it perform if we use each of the following algorithms? An answer in big-O notation is acceptable.

bubble sort
insertion sort
mergesort
quicksort (using Hoare partitioning)

12. Number of Moves

Suppose that we sort an array of distinct integers of length N, and that initially the largest integer is at the beginning of the array. How many times will this integer move to a new array position if we use each of the following algorithms?

bubble sort
insertion sort
mergesort
quicksort (using Hoare partitioning)

13. Dynamic Array-Based Queue

In the lecture we implemented a fixed-size queue using an array. Now implement an array-based queue that can grow to any size.

LinkedList class

In the following exercises, you are given a class LinkedList with a single attribute head that points to the head of a linked list. Each list node is an instance of the Node class:

class Node:
  def __init__(self, val, next):
    self.val = val
    self.next = next
    
class LinkedList:
  def __init__(self, head):
    self.head = head

14. Append

Write method that appends a value to a LinkedList.

15. Delete First

Write a method that deletes the first node (if any) in a LinkedList.

16. Delete Last

Write a method that deletes the last node (if any) in a LinkedList.

17. Rotate a List

Write a method that moves the last node in a LinkedList to the head of the list.

18. Second To Last

Write a method that returns the second-to-last element of a LinkedList of non-negative integers. If there is no such element, return None.

19. Delete the Nth

Write a method that deletes the Nth element (if any) of a LinkedList.

20. Delete Every Other

Write a method that deletes every other element of a LinkedList, starting with the first.

21. Reverse a List

Write a method that reverses a LinkedList. Do not allocate any additional memory.

22. Sort a List

Write a method that sorts a LinkedList using mergesort. Do not use any ordinary lists (i.e. arrays).

23. Even/Odd Split

Write a method that splits a LinkedList into two LinkedList objects, one containing even numbers, one odd. The numbers in each list should appear in the same order as in the original list.

Introduction to Algorithms Week 7: Exercises