Efficient Java Programming Strategies for Week 8

CS1020 Week 8: 12thMarch 2015

Contents Sit-in lab #2 Common Mistakes Take-home Lab #3 Week 8

Sit-in Lab #2 Set A Construct Set B Evaluation Week 8

Objectives Collections Use array of objects, and java.util.Arraylist Length vs size vs capacity Handle insertion, sequential searching efficiently Problem solving Design algorithm without changing structure, behaviour Think of objects in terms of: the data they have, and the services they provide Week 8 4

Understand Question 10 20 30 40 50 buildUnit( , ) Week 8 5

Design Classes (1/2) Sequential searching Week 8 6

Design Classes (Set A: 2/2) : Construct 2 size == 2 capacity == 2 : Building size == 1 capacity == 3 1 : Building + size() 2 : ArrayList <Building> For efficiency, store (logical) size! Week 8 7

Design Classes (Set B: 2/2) : Evaluate 2 size == 2 capacity == 2 A B : Category size == 1 capacity == 3 1 C : Category + size() 2 D E : ArrayList <Category> For efficiency, store (logical) size! Week 8 8

Insertion (Set A: 1/2) How to add Building in sequence? How to add Unit in sequence? : Construct 2 : Building 1 1 : Building + size() 2 : ArrayList <Building> Week 8 9

Insertion (Set B: 1/2) How to add Category in sequence? How to add Offense in sequence? : Evaluate 2 A B : Category 1 1 C : Category + size() 2 D E :Category : ArrayList <Category> Week 8 10

Insertion (Set A: 2/2) How to add Unit efficiently? a) _arr[size++] = givenUnit; c) Unit[] temp = new Unit[ _arr.length + 1]; // copy _arr s units to temp temp[_arr.length] = givenUnit; _arr = temp; b) int currIdx = 0; for (Unit curr : _arr) { if (curr == null) _arr[currIdx] = givenUnit; currIdx++; } d) All of the above e) None of the above 2 : Building Week 8 11

Insertion (Set B: 2/2) How to add Offence efficiently? a) _arr[size++] = givenOffence; c) Offence[] temp = new Offense[ _arr.length + 1]; // copy _arr s units to temp temp[_arr.length] = givenOffence; _arr = temp; d) All of the above e) None of the above b) int currIdx = 0; for (Offence curr : _arr) { if (curr == null) _arr[currIdx] = givenUnit; currIdx++; } 2 B A : Building Week 8 12

Searching (Set A: 1/5) How to prevent redundant searches? buildUnit( , ) : Construct 2 : Building 3 : Building + size() 2 : ArrayList <Building> Week 8 13

Searching (Set B: 1/5) How to prevent redundant searches? recordOffence( category, offence) : Construct 2 A B : Category 3 E C D : Category + size() 2 : ArrayList <Category> Week 8 14

Searching (Set A: 2/5) buildUnit( , ) Find the first matching building Find the first matching unit within : Construct 2 : Building 3 : Building + size() 2 : ArrayList <Building> Abstraction: I don t care how Building finds the 1st matching Unit Week 8 15

Searching (Set B: 2/5) recordOffence( category, offence) Find the first matching category Find the first matching offence within : Evaluate 2 : Category 3 : Category + size() 2 : ArrayList <Category> Abstraction: I don t care how Category finds the 1st matching Offence Week 8 16

Searching (Set A: 3/5) buildUnit( , ) Unit selected = null; // why initialize? /* Find the first matching building */ : Construct 2 For each Building currBldg : _buildings If currBldg.hasName(bldgName) selected = currBldg.( find first matching unit within )() : Building 3 : Building + size() 2 Attempt to build unit What s wrong with this? : ArrayList <Building> Week 8 17

Searching (Set B: 3/5) recordOffence( category, offence) Offence selected = null; // why initialize? /* Find the first matching category */ : Evaluate 2 For each Category currCat : _categories If currCat.hasName(offenceName) selected = currCategory.( find first matching unit within )() : Category 3 : Category + size() 2 Attempt to build unit What s wrong with this? : ArrayList <Category> Week 8 18

Searching (Set A: 4/5) findUnitByName( blueCar ) For each Unit currUnit : _units If currUnit.getName().equals( blueCar ) return currUnit return null What s wrong with this? 2 : Building Week 8 19

Searching (Set B: 4/5) findOffenseByName( offenceA ) For each Offence currOffence : _offenses If currOffence.getName().equals( offenceA ) return currOffence return null What s wrong with this? 2 A B : Building Week 8 20

Searching (Set A: 5/5) /* Find the first matching unit */ findUnitByName( blueCar ) Unit match = null For each Unit currUnit : _units If currUnit.getName().equals( blueCar ) match = currUnit return match What s wrong with this? 3 : Building Week 8 21

Searching (Set B: 5/5) /* Find the first matching offense */ findUnitByName( offenseA ) Offence match = null For each Offense currOffsense : _offenses If currOffense.getName().equals( offenseA ) match = currOffense return match What s wrong with this? A B 3 C : Building Week 8 22

Common Mistakes (1/2) Inefficient implementation of array-based collection Re-creating array on insertion Finding the first null element as the location to insert to Searching continues after first match is found Incorrect searching in array-based collection Searching past the logical end of the array Results in NullPointerException or undesired behaviour Using equals() method to compare each Building object in the ArrayList<Building> with building NAME, a String Week 8 23

Common Mistakes (2/2) Fail to visualize how problem should be solved I must create getters/accessors for this to work Failing to view classes as templates of objects that store data and provide services Don t knowwhat this method is for Don t know which method to place this functionality in Don t know which method to invoke (When writing real software, changing what a public method does will likely affect other programs) Week 8 24

Next Step (1/3) Understand relationship between: Collection List RandomAccess ArrayList/Vector Simulate your own ArrayList to understand how java.util.ArrayList works! See next page (You should have done this during recess week) Week 8 25

Next Step (2/3) Implement an array-based Collection supporting Efficient insertion, proportional to 1 operation Sequential search and removal, proportional to N operations when we have N elements in the array Implement an array-based List supporting Insertion into a given index in the middle of the list Removing from a given index in the middle of the list Week 8 26

Next Step (3/3) Implement your own LinkedList<E> and ListNode<E> from scratch Think: Why use LinkedListwhen there s ArrayList? Why use ArrayList when there s array? Which operations are more efficient in LinkedList, and which are more efficient in ArrayList? Week 8 27

Take-home Lab #3 Exercise 1 Flip The List 28 Week 8

Simple Algorithm (1/11) Starting index to be flipped A B C D E Keep a pointer to link the last index Week 8 29

Simple Algorithm (2/11) Pointer 1 Pointer 2 Pointer 3 A B C D E Week 8 30

Simple Algorithm (3/11) Pointer 1 Pointer 2 Pointer 3 A B C D E NULL Week 8 31

Simple Algorithm (4/11) Pointer 1 Pointer 2 Pointer 3 A B C D E NULL Week 8 32

Simple Algorithm (5/11) Pointer 2 Pointer 3 Pointer 1 A B C D E NULL Week 8 33

Simple Algorithm (6/11) Pointer 3 Pointer 1 Pointer 2 A B C D E NULL Week 8 34

Simple Algorithm (7/11) Pointer 1 Pointer 3 Pointer 2 A B C D E NULL Week 8 35

Simple Algorithm (8/11) Pointer 1 Pointer 3 Pointer 2 A B C D E NULL Week 8 36

Simple Algorithm (9/11) Pointer 2 Pointer 1 A B C D E NULL Week 8 37

Simple Algorithm (10/11) Pointer 2 Pointer 1 A B C D E NULL Week 8 38

Simple Algorithm (11/11) Pointer 2 Pointer 1 A B C D E NULL Week 8 39

Exception Start Index Start Index A B C D E Week 8 40

Take-home Lab #3 Exercise 2 Kallang Wave 41 Week 8

Kallang Wave Simulate a wave throughout an entire stadium Multiple rows are not simulated Simulation runs from left to right Members of the audience are represented by ASCII characters Different characters represent different states, not individuals 42 Week 8

Audience 43 Week 8

Audience as ASCII ||,,, ,||,, ,,||, ,,,|| |,,,| 44 Week 8

Circular Linked List Stadium is round need a round linked list Must use circular linked list Either from skeleton or self-made Given CircularLinkedList class is incomplete Bonus marks for efficient use Will need modification of data structure 45 Week 8

END OF FILE 46 Week 8