CS 112 Lab 5

Agenda

Two algorithm exercises on sorting and Linked List. Please work out algorithms for two problems below, programming them is not required but is encouraged for the second problem if you have worked out the algorithm.

Linked List

Task: Given a singly linked list L with unknown number of nodes, check if L has a cycle. Assume each node has a unique identifier and no two nodes share the same identifier.

Requirements for your algorithm:

  • Time: Linear O(N) in the number of nodes in L.
  • Space: Constant O(1), do not use an additional variable size datastruture like array, hashtable, etc.

Hints: Use two probes (iterators) that move (walk) at different speeds.

Sorting

Task: Given two integer arrays A, B of length N elements and an integer S: check if S can be obtained as the sum of a pair of numbers (S = a + b) where a is from array A and b is from array B.

There can be many pairs (a, b) for a given S, we only need to find one pair or report that there are no pairs that sum to S.

Requirements for your algorithm:

  • Time: O(N log N) where N is length of input array. Note that O(N^2) algorithm is trivial, just check each pair.
  • Space: Constant O(1), do not use an additional variable size datastruture like array, hashtable, etc.

Hints: To get O(N log N), first sort the two arrays. You should then be able to solve the problem in linear O(N) time using two pointers similar to merge procedure for merge sort.

URL

http://cs-people.bu.edu/tvashwin/cs112_spring09/lab05.html