Slides Corection

[Haidong (Haydon) Xue]

Hi all,

A mistake on slides: "Lecture 8B_Intro to dynamic programming, matrix chain multiplication, longest common subsequence", page 23, is found, fixed and updated.

The animation of BFS(3) on today's slides is fixed and updated.

A mistake in the DFS(1) tree is fixed and updated. 

 

--
Haidong(Haydon) Xue
Ph.D Candidate
Research Assistant, Teaching Instructor
Department of Computer Science
Georgia State University

http://www.cs.gsu.edu/~hxue1

[Travis Seiler]

Could you also give us the answer to the bonus question?  I had to leave at the end of class and did not have time to wait for the answer.  Not having a sorted array through my original idea for a loop.

Thanks,

Travis Seiler

[Haidong (Haydon) Xue]

Sure.

The problem is: 

Given an integer array A[0, ..., n], and a number s. Find out all the index pair of A (e.g. (i, j) ) that the element sum is s (i.e. A[i]+A[j]=s), with O(n) time.

E.g. for A[0] = -1 , A[1] = 2, A[2] = 1; s=3

The output should be: 

(1, 2) //since A[1]+A[2]=3

First of all, there are many solutions of this problem. Some of them are from certain unique intuition or technique which prevent you solve a similar problem next time.

The common method here is to use hash tables to speed up search, so the standard solution in my mind is: 

1. Scan A once, in each iteration:    //This scan need O(n) time 

Insert <A[i], i> into a hash table.  //A[i] as key, O(1)

/*

* An element of the hash table is <value, index>; value is the key, index is the satellite data 

*/

2. Scan A again, and in each iteration:   //This scan need O(n) time 

e = search( s-A[i] ) in the hash table  //O(1) 

if(e!=null) output(i, e.index);