weight = 5
Homework
Week 1
- CodingBat double23
- CodingBat swapEnds
- CodingBat front11
- Repeat above problems using
ArrayList
s instead of arrays
Week 2
Start with this implementation of the ArrayList.java
developed in class.
- Implement the
ArrayList.set(int index)
method. - Implement the
ArrayList.remove(int index)
method. - Implement the
ArrayList.toArray()
method.
- Study Collection and List interfaces and prepare questions and feedback for your instructor
- Study Array-Based Lists, ArrayList review and prepare questions and feedback for your instructor
- Study Generics in Java and prepare questions and feedback for your instructor
Week 3
Complete by 8am Monday of week 3 - be prepared to ask questions in class
- Give the Big-O time complexity for the following algorithm. Justify your answer.
public static boolean areUnique(List<String> strings) { boolean areUnique = true; for(int i=0; areUnique && i<strings.size(); ++i) { for(int j=0; areUnique && j<strings.size(); ++j) { if(i!=j && strings.get(i).equals(strings.get(j)) { areUnique = false; } } } return areUnique; }
- Give the Big-O time complexity for the following algorithm. Justify your answer.
public static boolean areUnique(List<String> strings) { boolean areUnique = true; for(int i=0; areUnique && i<strings.size(); ++i) { for(int j=i+1; areUnique && j<strings.size(); ++j) { if(strings.get(i).equals(strings.get(j)) { areUnique = false; } } } return areUnique; }
-
Give the Big-O time complexity for \( T(n) = 8 + 17n + 3n^2 \).
-
Study Linked Lists and prepare questions and feedback for your instructor Start with the
LinkedList.java
the code developed in class. Implement the following methods: -
get(int)
-
set(int, E)
-
add(int, E)
-
contains(Object)
-
remove(int)
-
remove(Object)
-
indexOf(Object)
-
toArray()
-
Study Iterators and prepare questions and feedback for your instructor
-
Implement the
ArrayList::ArrayListIterator.remove()
method. -
Implement the
LinkedList.iterator()
method and the complete inner class that implements theIterator
interface.
Week 4
Complete before Exam I
- Implement a
Stack
class with three methods using an array to store items on the stack:E push(E element)
E peek()
E pop()
- Implement a method,
parenChecker
, that accepts aString
and returnstrue
if the parenthesization is legal. The method must make use of theStack
developed in lecture.((a + b) + c)
— Good([a + b] + c)
— Good(a + {b + c})
— Good((a + b) + c
— Bad([a + b] + c]
— Bad(a + {b + c)}
— Bad
Week 5
- Implement a
Queue
class with three methods using anLinkedList
to store items on the queue:boolean offer(E element)
E peek()
E poll()
- Implement the
CircularQueue
class introduced in lecture. - Implement a recursive method to create a
String
representation of an array ofString
s. - bunnyEars
- triangle
- countHi
Week 6
In preparation for the week 6 quiz
boolean binarySearch(List<E> list, E target)
which returns true if thelist
containstarget
. You may assume that the list is sorted.- changeXY
- noX
- pairStar
- array220
- countPairs
- nestParen
- strCopies
- groupSum (optional)
- groupSum6 (optional)
Week 7
- Provide the asymptotic time complexity (and justification) for the following methods of the
BST
class developed in lecture:contains()
,add()
,size()
, andheight()
. Provide answers for a BST that is balance and not balanced. - Implement the
toString()
method (along with a recursive method) for theBST
class developed in lecture that returns a string containing all of the elements in sorted order. - Implement a recursive method,
max()
that returns the largest value of the tree. - Implement a recursive method,
min()
that returns the smallest value of the tree. - Implement a recursive method,
numberOfLeaves()
that returns the number of leaf nodes in the tree. - Just for fun: Implement a recursive method,
getIthLargest()
that returns the ith largest value of the tree. [This one is a bit more challenging. You would not be expected implement this on a quiz or exam.]