CSE 373 Lecture Notes - Lecture 1: Linked List, Time Complexity, Binary Search Algorithm
17 May 2018
School
Department
Course
Professor
CSE 373 Lecture 1
Implementing maps
- Using an array or a linked list
- Putting stuff in– linked list more efficient b/c constant time
- Memory storage – linked list more efficient
- Looking stuff up
o Array
▪ If you know index, finding an item is constant time
▪ If sorted, use binary search which is log(n) time
o Linked list lookup is linear time
o Array more efficient
Iterator – java interface that dictates how a collection of data should be traversed
- hasNext() and next()
- Eclipse feature to add unimplemented methods
Testing your code
- Isolate by breaking code into small modules
- Build in increments
- Test as you go
- What to test
o Expected behavior
o Can user mess up (forbidden input) – e.g., passing in null, illegal arguments
o Empty/null cases
o What about edge cases – e.g., if you’re trying to add something to array when
it’s full
o Scale – does it work at greater scale
- Tips
o Test behavior in combination
o Think about empty/error cases + boundary cases
- Example – writing list interface implementation that stores integers in an array
o Expected behavior – create new list, add some items to it, remove a couple of
them
o Forbidden input – adding other data types, adding outside of array indices,
negative numbers, duplicates, really large numbers
o Empty/null – remove when list is empty, adding to null list, size on a null list
Document Summary
Using an array or a linked list. Putting stuff in linked list more efficient b/c constant time. Memory storage linked list more efficient. If you know index, finding an item is constant time. If sorted, use binary search which is log(n) time: linked list lookup is linear time, array more efficient. Iterator java interface that dictates how a collection of data should be traversed. Tips: test behavior in combination, think about empty/error cases + boundary cases. Junit testing framework that works with ides: @test to indicate test code, assertions, assertequals(item1, item2, asserttrue(boolean, assertfalse(boolean, assertnotnull(item) Search array for value 42: o(n) linear. Best case scenario if value is first. Best case scenario if value is in middle. Finished when n/2^k = 1 k = log2n. Asymptotic analysis how runtime of an algorithm grows as the data grows (runtime grows as input grows)
