-
what is an object?
object is an instantiation(allocating memory for the new object and calling the constructor) of a class.
-
what does a class defines?
the structure of its objects
-
what does class inheritance mean?
classes are organized in an "is-a" hierarchy.
-
what happens when a class implements an interface?
the class should implement all hte methods declared in the interface.
-
How does the time taken depend on the input size?
Suppose it takes 2N2 + 5N - 3 operations to sort a list of size N.
What happens if we double the size of the input?
- 8N2 + 10N - 3 : almost four times as long
- As N gets bigger and bigger, the 2N2 term becomes more
- important, and the 5N term becomes less important.
- If we care mostly about big problems, we can ignore
- those lower-order terms.
-
what is order of complexity?
- is a measure of how its
- performance changes as the problem instance gets bigger.
- Written in "big O notation": O(N2), O(N).
-
get the big O notation of 2N2 + 5N -3 (this is the expression for number of operations)
with steps
- Take the highest-order (fastest-growing) term: 2N2
- Drop the constant: N2
- So we say the algorithm has complexity O(N2).
- "Order N squared" or "Big O of N squared"
-
names for some of the most
common complexity classes:
- O(1): constant. Doesn't depend on the size of the input.
- O(log2N): logarithmic. Doubling the input adds an amount of
- time.
- O(N): linear. Doubling the input doubles the time.
- O(Nlog2N): N log N. Good sorting algorithms, e.g., Mergesort
- O(N2): quadratic. Doubling the input quadruples the time.
- O(2N): exponential. Adding one to the input size doubles the
- time.
-
Time complexities for the following:
sum = 0;
for (count = 1; count <= n; count++)
sum = sum + count;
sum = ((n + 1) * n) / 2;
O(N)
O(1)
-
Abstract data type (ADT)
A data type whose properties (domain and operations) are specified independently of any particular implementation.
only the interface of the method is included
-
primary responsibility of NumberListADT:
Remember all the numbers that have been inserted into it;Identify whether a given number has been inserted.
-
NumberListmethods
- constructor
- transformers(mutators: insert(intv)
- observers (accessors): contains(intv), isFull, toString
-
Array-based vs linked-based: differences.
- use of memory
- manner of access
- efficiency for various operations
- language support
-
implement a StringNode class
- public class StringNode
- {
- protected String info;
- protected StringNodelink;
- public StringNode(String
- info)
- {
- this.info = info;
- link = null;
- }
- public void setInfo(String
- info)
- {
- this.info = info;
- }
- public String getInfo()
- {
- return info;
- }
- public void setLink(StringNode
- link)
- {
- this.link= link;
- }
- public StringNodegetLink()
- {
- return link;
- }
- }
-
create the String Node class and create object sNode1 that will hold the value basketball.
will also create sNode2 with value "baseball"
StringNodesNode1 = new StringNode("basketball");
sNode1.setLink(sNode2);
snode1->info:basketball link:->(sNode2)->info:baseball link->null
-
create a traversal of a linked list
draw it B C D with currNode moving.
StringNode currNode= letters;
- while (currNode!= null)
- {
- System.out.println(currNode.getInfo());
- currNode= currNode.getLink();
- }
Letters->info:B link:->info:C link:->info:D link->null
-
Insertion at the front
for letters(beginning of the list)
newNode.setLink(letters);
letters = newNode;
-
Linked-based NumberListADT implementation
- public class LinkedNumberList implements NumberList
- {
- private LNodefirst;
- public LinkedNumberList()
- {
- first = null;
- }
- ...
-
inked-basedNumberListADT
The insert operation
assume that the numbers are inserted to the front of the list.
- public void insert(intv)
- {
- LNode newNode= new LNode(v);
- newNode.setLink(first);
- first = newNode;
- }
-
Create observers isFull and contains:
- public boolean isFull()
- {
- return false;
- }
- public boolean contains(intv)
- {
- LNodecurrent = m_first;
- while (current != null)
- {
- if (current.getInfo() == v)
- return true;
- else
- current = current.getLink();
- }
- return false;
- }
-
The toString observer
// Return a string representation of the list (listContent)
- public String toString()
- {
- String listContent= "The content of the list is: ";
- LNodecurrent = m_first;
- while (current != null)
- {
- listContent+= current.getInfo() + " ";
- current = current.getLink();
- }
- return listContent;
- }
|
|