Your midterm is essentially divided into three (3) sections. Each section tests

Question

Your midterm is essentially divided into three (3) sections. Each section tests your knowledge of the material in a different and increasingly difficult way. The first section is basic knowledge and explanation. You will see questions like, "what is a... ," or "explain when or why a programmer would...." The second section involves interpreting/analyzing code or writing short coding statements. For these questions, you will be given excerpts of code and asked questions such as, "what would be output," or "write the code to add the given object to the given array list." The final section of your test will involve free response code writing. You will be asked to do things like, "complete method removeElement of the LinkedList class given the following requirements." Below is a complete list of topics and guidelines for your midtermm Topic Outline 1. Complexity Analysis a. b. c. What is the dominate term and how to pick them out of a function Expressing algorithm complexity in "Big-Oh" notation Be able to analyze a non-recursive algorithm i. Know how to identify an algorithm's basic operation ii. Express the number of times the basic operation executes ii. Pick out the dominate term and put it in O () notation 2. Queues a. b. c. d. e. Where are new elements added From where are elements removed Given an implementation, determine the order in which elements are removed Cost of enqueue() and dequeue() operations What type of pointers are used 3. Stacks a. b. c. d. e. Where are new elements added From where are elements removed Given an implementation, determine the order in which elements are removed Cost of pop() and push() operations What type of pointers are used 4. Linked Lists (your free response question will be on linked lists) How the list is constructed - each element holds a reference to the next element in the list. The linked list class holds a reference to the first element, Understand how to add elements to the front of the list and shift the current elements using code Understand how to determine if the list is empty a. b. c.

Explanation / Answer

1. Complexity Analysis
1.a. Dominate term and how to pick them out of a function
the mathematical term greater in absolute value than any other (as in a set) or than the sum of the others.
A dominant term such as x -> a is a term which grows more rapidly than
any other in the expression. In your example there are two terms:

f(x) = x^2 + 1/x^2.

As x -> infinity, the dominant term is x^2, because the ratio of x^2
to 1/x^2 (which equals x^4) goes to infinity. The function behaves
like x^2 for large values of x, because the other terms are of
negligable size compared to the dominant one.

1.b Algorithm complexity in Big-oh notation

Algorithmic complexity is concerned about how fast or slow particular algorithm performs. We define complexity as a numerical function T(n) - time versus the input size n. We want to define time taken by an algorithm without depending on the implementation details.

The goal of computational complexity is to classify algorithms according to their performances. We will represent the time function T(n) using the "big-O" notation to express an algorithm runtime complexity. For example, the following statement

T(n) = O(n2)
Definition of "big Oh"

For any monotonic functions f(n) and g(n) from the positive integers to the positive integers, we say that f(n) = O(g(n)) when there exist constants c > 0 and n0 > 0 such that
f(n) = c * g(n), for all n = n0
Intuitively, this means that function f(n) does not grow faster than g(n), or that function g(n) is an upper bound for f(n), for all sufficiently large n?8

1.c.i) algorithm's basic opertion

There are four rules to count the operations:
Rule 1: for loops - the size of the loop times the running time of the body
Rule 2: Nested loops – the product of the size of the loops times the running time of
the body
Rule 3: Consecutive program fragments
Rule 4: If statement

1.c.ii) Express no of times basic operations executes
1. Decide on problem size specification
2. Identify basic operation
3. Check worst, best, average case
4. Count: set up the sum
5. Evaluate or determine order of sum

1.c.iii) pick out dominate term and put it in 0() notation

2 Queues
2.a) add element to the end of the queue / elements inserted from one end called REAR(also called tail)
2.b) returns the element from the front of the queue, removing it / deletion of existing element takes place from the other end called as FRONT(also called head)
2.c) implementation

class Queue {
private Object[] mElements = new Object[] {};

public void enqueue(Object element) {
Arrays.insertAt(mElements, element, 0);
}

public Object dequeue() {
Object result = null;
if (null != mElements && 0 < mElements.length) {
result = mElements[mElements.length - 1];
Arrays.remove(mElements, result);
}
return result;
}

public Object peek() {
if (null != mElements && 0 < mElements.length)
return mElements[mElements.length - 1];
else
return null;
}

public void remove() {
if (null != mElements && 0 < mElements.length)
Arrays.remove(mElements, peek());
}
}

2.d) The cost of dequeue is O(n) and the cost of enqueue is O(1)

2.e) types of pointers - head pointer and Tail pointer

3 Stacks

3.a) elements can be added and removed from the stack only at the top. push adds an item to the top of the stack,
3.b ) pop removes the item from the top

3.c) implementation

if (isEmpty())
return null;
else
{
for (int i = 0; i < index; i++)
tmpStack.push(this.pop());

E removedElement = tmpStack.pop();

while (!tmpStack.isEmpty())
this.push(tmpStack.pop());

return removedElement;
}

3.d) cost of push() and pop()

If push is of complexity O(1), it means that running time is less than some constant C > 0. Therefore, for n operations the running time is less than nC, so the complexity is O(n).
Multipop calls pop k times, since pop has complexity O(1), the running time of multipop is k O(1) = O(k).
O(2m) = O(m), because constants don't matter when complexities are calculated.
Worst case complexity is O(n^2), since multipop is of complexity O(n) and push/pop of O(1). However, for sequence of operations the Amortized Analysis is often used, and in this case the amortized complexity for sequence of push, pop and multipop is O(n).

3.e) stack pointer is used

4) Linked List in details

how it is constructed and how to add emements and how to determine that list is empty

// Java program to count number of nodes in a linked list

/* Linked list Node*/
class Node
{
int data;
Node next;
Node(int d) { data = d; next = null; }
}

// Linked List class
class LinkedList
{
Node head; // head of list

/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */
new_node.next = head;

/* 4. Move the head to point to new Node */
head = new_node;
}

/* Returns count of nodes in linked list */
public int getCount()
{
Node temp = head;
int count = 0;
while (temp != null)
{
count++;
temp = temp.next;
}
return count;
}

/* Drier program to test above functions. Ideally
this function should be in a separate user class.
It is kept here to keep code compact */
public static void main(String[] args)
{
/* Start with the empty list */
LinkedList llist = new LinkedList();
llist.push(1);
llist.push(3);
llist.push(1);
llist.push(2);
llist.push(1);

System.out.println("Count of nodes is " +
llist.getCount());
}
}



Output:
count of nodes is 5

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.