----------
OUTLINE
----------

MIDTERM REVIEW
GRAPHS AND TREES INTRO
PROJECT 3
TREES AND TRAVERSALS



----------
PRE-DISCUSSION
----------

PRINT THESE NOTES
PRINT PROJECT OUTLINE
BRING MIDTERM KEY
BRING PRE DRAWN GRAPHS

DRAW OUT GRAPHS ON BOARD



----------
ANNOUNCEMENTS
----------

LAB GRADES HAVE BEEN ENTERED - IF THERE ARE PROBLEMS, TALK TO ME.

PROJECT 3 HAS BEEN RELEASED - WE WILL TALK ABOUT IT TODAY.

THERE IS A REVISED ANALYSIS OF THE ALTERNATE-BASE MERGE SORT WE DISCUSSED
LAST WEEK.

EMAIL THE READER (AT CS61B-RA) IF YOU HAVE ANY PROBLEMS WITH THE HOMEWORK.

----------
MIDTERM REVIEW
----------

I WON'T TALK TO YOU ABOUT POINT ISSUES OR REGRADES -

I DON'T HAVE THE POWER TO GIVE YOU MORE POINTS,

I DIDN'T GRADE EVERY PROBLEM (SO I DON'T KNOW THE EXACT GRADING STANDARD)



THE OFFICIAL POLICY IS -
CLEARLY WRITE OUT AN EXPLANATION OF WHAT POINTS YOU WANT BACK AND WHY YOU
THINK YOU DESERVE THEM. TURN THIS INTO GEORGE AT HIS OFFICE HOURS. HE WILL
THEN CONSIDER YOUR REQUEST.



I WOULD BE CAREFUL IN DOING THIS -

THERE IS A GOOD CHANCE YOUR GRADE WILL GO DOWN.



TODAY I WILL GO OVER A FEW PROBLEMS THAT I THINK ARE WORTH REVIEWING.

IF YOU STILL HAVE NON-POINT RELATED QUESTIONS, COME TO MY OFFICE HOURS OR
CHECK OVER THE POSTED SOLUTIONS.



--- PROBLEM 3

I WILL ONLY LOOK AT PART 3

WORST CASE IS THE RUNNING TIME WITH THE ABSOLUTE WORST INPUT YOU CAN COME
UP WITH.

AVERAGE CASE IS TECHNICALLY THE RUNNING TIME OF THE ALGORITHM ACROSS ALL
INPUTS.

IN GENERAL IT IS USUALLY SYNONYMOUS WITH "RANDOM", SINCE MOST INPUTS CAN BE
CONSIDERED RANDOM.
IN THIS CASE WAS TRUE.



--- PROBLEM 4

SIMPLE SOLUTION -

1. CONVERT TO ARRAYS (O(N))

2. SORT BY NAME (O(NLOG(N))

3. FIND / ELIMINATE ADJACENT DUPLICATES (O(N))

4. DO MERGE-LIKE COMPARISON BETWEEN TWO ARRAYS TO CHECK CONSISTENCY



OFFICIAL SOLUTION -

TAKES SIMILAR FORM

1. REHASH EACH ELEMENT IN EACH CHAIN OF SIZE M TO A NEW HASH TABLE WITH SIZE M.
USE A DIFFERENT, "ORTHOGONAL" HASH FUNCTION - SHOULD KEEP NUMBER OF
COLLISIONS LOW.

2. IF THERE IS A COLLISION, CHECK FOR A DUPLICATE (O(N))

3. THEN PUT THE ELEMENTS FROM THE HASH TABLE IN AN ARRAY AND SORT BY COST
AND THEN NAME (O(NLOG(N)))

4. DO A LINEAR COMPARISON BETWEEN THE SORTED_BY_COST LIST AND THE ABOVE
ARRAY. DUPLICATES IN SORTED_BY_COST WILL BE DETECTED AS INCONSISTENCIES
BETWEEN THE TWO LISTS. (O(N))



GRADING WAS LENIENT -

COULD PUSH A LOT OF THE DETAILS INTO THE HASH FUNCTION.



----------
INTRODUCTION TO TREES AND GRAPHS
----------

WE HAVE BEEN WORKING TOWARD TREES AND GRAPHS ALL SEMESTER.

THIS IS THE REALLY INTERESTING STUFF.

EACH IS USEFUL FOR A TON OF DIFFERENT THINGS.

I CAN'T SAY MUCH BEYOND THIS - EITHER YOU ARE EXCITED OR YOU AREN'T.



A NODE IN A GRAPH IS THE MOST GENERAL TYPE OF NODE -

SOME OBJECT AND A VARIABLE NUMBER OF POINTERS



SHOW THAT THE FIGURE I HAVE DRAWN IS A GRAPH

ERASE EDGES TO GET THE LINKED LIST AND TREES



DRAW THESE OUT:

TREES -
File systems
Expression trees - The obligatory example (but actually very useful)
The method call tree
A conversation

GRAPHS -
Airline flights
People
Tons of other things



AS YOU CAN SEE, THESE ARE INCREDIBLY USEFUL BOTH IN COMPUTER SCIENCE AND
REAL WORLD APPLICATIONS.




----------
PROJECT 3
----------

USE THE SPEC AS A REFERENCE



DRAW OUT 'SLIDE' AND TALK ABOUT HOW IT WORKS AND WHAT THE GOAL IS



TALK ABOUT HOW THEY WILL SOLVE THIS PROBLEM - EXHAUSTIVE SEARCH.

LEADS INTO THE GAME GRAPH



FOCUS ON THE GAME GRAPH

SHOW THAT WE WANT TO GET RID OF CYCLES THAT WILL LEAD TO INFINITE EXECUTION.



TALK ABOUT HASHING AT THIS POINT - A NUMBER OF DIFFERENT APPROACHES.

GOAL IS TO FIND DUPLICATE BOARDS AND NOT CONTINUE DOWN THAT PATH.



TALK ABOUT SOME SAMPLE GAMES AND WHAT SORT OF TREES THEY WILL PRODUCE -

WHAT IF WE HAVE A LOT OF OPEN SPACES (DO A 3X3 WITH ONLY 1 TILE)

WHAT IF WE HAVE VERY FEW OPEN SPACES (DO A 3X3 WITH ONLY 1 OPEN SPACE)



GIVE THEM ADVICE ON HOW TO PROCEED -

DESIGN A LOT!

THEN IMPLEMENT, TEST, TWEAK, RINSE, REPEAT.