Midterm review

Linked Lists:

1. Write an algorithm to detect a cycle in a linked list.

2. Remove consecutive duplicate entries from a given linked list.

3. Get the k-th to the last element in the linked list (when the size of the list is not known/tracked).

4. Check if the linked list is a palindrome.

5. Reverse a singly-linked list non-recursively.

Stacks/Queues:

1. Design a stack such that getMinimum() is O(1).

2. Reverse the elements of stack only using stack operations.

Recursion:

1. Write a recursive algorithm to perform x^n.

2. Write a recursive algorithm for binary search.

Complexity analysis:

1. Compare merge sort algorithms with various partitioning options.

2. Write down the lower bound, upper bound and order functions for f(n) = 0.5 n^3 + 2 n^2 + log n

Binary Search Trees:

1. Given an inorder traversal and a postorder traversal, write an algorithm to reconstruct the tree.

2. Find the nearest match of a given value in a binary search tree.

3. Write a function to check whether two BSTs are structurally identical.

4. Write a function to find the size of a BST.

5. Write a function to compute the sum of all elements in a BST.

 

 

 

This entry was posted in Review. Bookmark the permalink.

Comments are closed.