DS6 ABSTRACT DATA TYPES

Question 1

INTRO

Answer 1

differentiate mechanism from use with layers of abstraction
bit -> assembly -> high level programming language -> algorithm design
abstract data types are accessed through interfaces
interfaces describe the type and methods we can use but dont reveal the internal mechanism

with abstraction we can have multiple clients
we can optimize the implementation to a specific system using modular code

Question 2

EXAMPLE: POINT CLASS

Answer 2

user program has interface:
public interface Point{
Point();
Point(double, double);
double x();
double y();
double r();
double theta();
double distance(Point);
public String toString();}

the class Point can be implemented with both cartesian and polar coords and the client will see no difference

code can be optimized without affecting the program

Question 3

QUEUES

Answer 3

general basic ds structures
collection of items
insert remove isempty
on the bases of queues we have priority queues fifo and lifo queues etc
its is a little abstract

Question 4

PUSHDOWN STACK

Answer 4

is a LIFO queue (last in first out)
insert = push in from top
remove = pop from top

lifo queue is best for:
-algorithms that need to be able to return to previous steps (undo and back functions)
-backtracking algorithms that form a partial solution check it stepwise and undo if it doesnt work
this can be an optimized alternative to brute force case checking

Question 5

FIFO QUEUE

Answer 5

first in first out
insert = put on top (or enqueue)
remove = get from bottom (or deque)

! note there can be a hybrid where we can push and pop and put and get

Question 6

INFIX TO POSTFIX USING STACK

Answer 6

infix is the way we write mathematical expressions(3+57-6)
postfix is when the operators are at the end of the expression(357+6-)
input: infix expression
output: postfix expression
use a stack
when operand print
when operator push to stack
when left parenthesis do nothing
when right parenthesis pop operator and print

Question 7

CALCULATE EXPRESSION USING STACK

Answer 7

in postfix
use stack for operands
when operand push in stack
when operator pop twice calculate and push result

Question 8

STACK WITH ARRAY

Answer 8

class intStack{
~private int[] s;
~private int N; counter for items in stack
~intStack(int maxN){ s = new int[maxN]; N = 0;}
~boolean isEmpty(){return (N == 0);)}
~void push(int item){s[N++] = item;}
~int pop(){return s[–N];}
}
ideally automatic size change

when N == maxN -> maxN *= 2
when N<= maxN/4 -> maxN/=2
since it is array (static) we need to copy to different array to change the size

Question 10

STACK WITH LIST

Answer 10

to solve size change problem
reference handling load
(in memory stack with array should be better since memory is limited anyways, if data segment is predetermined we can know the max size our systems allows)

class intStack{
~private Node head;
~private class Node{
~~int item; Node next;
~~Node(int item, Node next){this.item = item; this.next = next;}}
~intStack(int maxN){head = null;}
~boolean isEmpty(){return (head == null);}
~void push(int item){head = new Node(item, head);}
~int pop(){int v = head.item; Node t = head.next;
head = t;//delete head// return v;}
}

maxN is never used
code is very similar for most methods
push and pop are o(1) unless array resize is needed
exception handling is necessary but omitted for simplicity

Question 11

GENERALIZED IMPLEMENTATION

Answer 11

item or array is Object class
problems with type conversion (wrapper classes, type checking etc)
default types like ints require wrapper class to be used and therefore are slower than they should be

solution stack<T> where T is the type
where T is used its replaced with type of choice</T>

Question 12

FIFO QUEUE WITH LIST

Answer 12

class intQ{
~private Node head, tail;
~private class Node{
~~int item;
~~Node next;
~~Node(int item){this.item = item; next = null;}
~intQ(int max){head = null; tail = null;}
~boolean isEmpty(){return head == null;}
~void put(int item){
~~if(isEmpty()){
~~~tail = new Node(item);
~~~head = tail;}
~~else{
~~~Node t = tail;
~~~tail = new Node(item);
~~~t.next = tail;}
~int get(){
~~int v = head.item;
~~Node t = head.next;
~~head = t;
~~return v;}
}

Question 13

FIFO QUEUE WITH ARRAY

Answer 13

instead of moving items we will move the head and tail as indexes of the queue
n size array
wrap at 0
head is first item unless head ==N
head % ++
tail ++ %
empty: head%N == tail
full: (head-1)%N == tail

class Q{
private int q[];
private int N, head = 0, tail = 0;
~Q(int maxN){
~~q = new int[maxN+1];
~~N = maxN +1;
~~head = N; tail = 0;}
~boolean isEmpty(){return head%N==tail;}
~boolean isFull(){return (head-1)%N ==tail;}
~void enq(int item){q[tail++]=item; tail = tail%N}// cause when tail = N we need it to go to 0
~int deq(){head = head%N; return q[head++];}
}