Saturday, April 14, 2007

Lecture 30

Sorting an array of strings
for strings you can't use < , >
there exists a method called compareTo() which returns an integer
String x;
String y;
x.compareTo(y);
returns a negative number if x < y
returns zero if x == y
returns a positive number if x > y
String implements the comparable interface
public interface Comparable
{
public int compareTo(Object in);
}
Any class that implements comparable is strongly suggested to do it as follows
1. Total Ordering
- if a.compareTo(b) == 0;
then b.compareTo(a) == 0; (reflexive)

- if a.compareTo(b) <= 0;
then b.compareTo(a) >= 0; (antisymmetric)

- if a.compareTo(b) <= 0 and b.compareTo(c) <= 0
then a.compareTo(c) <= 0 (transitive)

a.compareTo(b) is defined for all a,b (Total)


2. If you implement equals() then if a.compareTo(b) == 0;
then a.equals(b) == true
and vice versa


Searching a sorted list
Sorted list searching can be done recursively with the divide and conquer strategy

Strategy
- split the list in half
- Let s represent the list item at the split point
if list has size > 1
if s = i, return index of s
if s > i, search the list segment with smaller values
if s < i, search the list segment with larger values
if list has size 1
if s = i, return index of s
otherwise i is not in the list
eg/ return -1

7 comments:

Domenico said...

I just wanted to say thank you.

Jake deVos said...

no problem man, this is so nice to have before exams. I'm glad i could be some help, for the next cse courses after 1030 i plan on continuing this, but i would probably want multiple moderators because EVERY lecture was getting really difficult to post in time.
but i appreciate your thanks and good luck on the final

Anonymous said...

Hi,

Thanks from me too.
Are you taking any cs courses in the summer?

Domenico said...

On that note, CSE 2001, 2011, 2021 and 2031 are next year's courses. Thats what the undergrad calendar seems to say. The topics look interesting.

Anonymous said...

finally more comp classes...and less crap classes

Anonymous said...

Hey Jake,

Thanks for your putting your notes online. I was in Turpins class, so I really really needed it, like most of us in Turpin's class who struggled to get notes out of his lectures.

So you could say you helped AT LEAST half of the students go some way towards getting through this course.

thanks again, best of luck with the exam.

Anonymous said...

thanks Jake, your notes were very helpful