Algorithms - Design and Analysis Fundamentals

a. Design a recursive algorithm whose input is a decimal integer and whose output is the binary representation of the input. b. Design a recursive algorithm that computes the reverse of the result in (a) - that is, converts a binary integer to its decimal equivalent.

Algorithms - Design and Analysis Fundamentals - Recursion - Fibonacci sequence

Prove by induction that fib(1) + fib(2) + ... + fib(n) = fib(n + 2) - 1.

Algorithms - Analyzing Algorithm Performance

Design an algorithm that tests whether or not two input lists of size n have at least one element in common. Give formulas for B(n) and W(n) for your algorithm.

Algorithms - Data Structures and Algorithm Design

Given a linked list, create a linked list with the same elements but in the reverse direction.

Analyzing Some Basic Comparison - Based Algorithms

Given a list L[0:n – 1], one way of maintaining a sorted order of L is to use an auxiliary array Link[0:n – 1]. The array Link[0:n – 1] serves as a linked list determining the next highest element in L, so the elements of L can be given in nondecreasing order by L[Start], L[Link[Start]], L[Link[Link[Start]]], and so forth. Then Linkn-1[Start] is the index of the largest element in L, and we set Link[Linkn-1[Start]] = Linkn[Start] = 0 to signal the end of the linked list. Design a version of MergeSort that uses the auxiliary array Link. See attached file for full problem description.