CSE 373 Study Guide - Spring 2018, Comprehensive Midterm Notes - Linked List, No In, Glossary Of Graph Theory Terms
12 Oct 2018
School
Department
Course
Professor
CSE 373
MIDTERM EXAM
STUDY GUIDE
Fall 2018
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 tryig to add soethig to array whe
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
find more resources at oneclass.com
find more resources at oneclass.com
o Boundary/edge cases – adding first thing, adding to front/back of list, adding
when list is full
o Scale – adding many items, removing many items in a row, setting value of item
many times
- JUnit – testing framework that works with IDEs
o @Test to indicate test code
o Assertions
▪ assertEquals(item1, item2)
▪ assertTrue(Boolean)
▪ assertFalse(Boolean)
▪ assertNotNull(item)
Sequential search
- Search array for value 42: o(N) linear
- Best case scenario – if value is first
Binary search
- Search array for value: o(log(N)) logarithmic
- Best case scenario – if value is in middle
- How long does it take to finish? – 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)
- Approximations
o Basic operations take constant time (assign variable, accessing index/field)
o Consecutive statements (time for each statement)
o Futio alls tie of futio’s ody
o Conditionals (time of comparison + result of comparison in worst case)
o Loops (number of iterations)
o Examples below:
find more resources at oneclass.com
find more resources at oneclass.com
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)
