1.      A set of classes is given as below:

• Class People extends Object and adds instance variables name:String and ssn:String, and methods getName():String and getSSN():String
• Class Student extends People and adds an instance variable avg_score:double and methods setAvg_Score(double) and getAvg_Score():double
• Class Faculty extends People and adds an instance variable course:String and methods setCourse(String) and getCourse():String
• Class Staff extends People and adds an instance variable office:String and a method getOffice():String
• Class TraditionalStudent extends Student and adds a method isFullTime():boolean
• Class NonTraditionalStudent extends Student and adds an instance variable employer:String and methods getEmployer():Sting and setEmployer(String)

a.       Draw a class inheritance diagram for the above set of classes: (10 points)

Solution: omit

 

2. Consider the following piece of Java code: (5 points)

TraditionalStudent tradStu = new TraditionalStudent();

tradStu.setEmployer("Hi-Tech");

Student student = tradStu;

String e1 = ((TraditionalStudent)Student).getEmployer();

String e2 = ((NonTraditionalStudent)student).getEmployer();

Explain the result when this piece of code is executed.

 

Solution: Second line will have a syntax error (exception) that TraditionalStudent doesn't have a method setEmployer

 

 

2.      Implement the Vector ADT using a singly linked list. Design your implementation class and describe methods using pseudo-code. (15 points)

Solution:

a.      Vector is the same as ArrayList

b.      Use Adaptor Design Pattern

c.       You can also maintain a singly linked list directly

        Instance field: SinglyLinkedList sll

        Constructor:

                sll = new SinglyLinkedList()

        Methods:

                isEmpty:                                            sll.isEmpty()

                size:                                                    sll.size()

                get(i) (elemAtRank(i)):                       if (i>size()) error

                                                                            ptr <-- sll.getFirst()

                                                                            rank <--0

                                                                            while (rank < i) ptr <-- ptr.next()

                                                                            return ptr.element()

                set(i, e) (replaceAtRank(i)):                if (i>size()) error

                                                                            ptr <-- sll.getFirst()

                                                                            rank <-- 0

                                                                            while (rank < i) ptr <-- ptr.next();

                                                                            sll.set(ptr, e)

                add(i, e) (insertAtRank(I, e):               if (i>size()) sll.addLast(e)

                                                                            ptr <-- sll.getFirst()

                                                                            rank <-- 0

                                                                            while (rank < i) ptr <-- ptr.next();

                                                                            sll.addBefore(ptr, e)

                remove(i) (removeAtRank(i):             if (i>size()) error

                                                                            ptr <-- sll.getFirst()

                                                                            rank <-- 0

                                                                            while (rank < i) ptr <-- ptr.next();

                                                                            sll.remove(ptr)

 

3.      Design an adaptor class to implement the Queue interface using the methods of the List ADT. (15 points)

Solution:

Queue:

Instance field:      List lst

Constructor:        lst <-- a new empty list

Methods:

        isEmpty:         lst.isEmpty

        size:                lst.size()

        enqueue(e):    lst.addFirst(e)

        dequeue():      lst.remove(lst.last())

        front():           lst.getFirst()

 

 

a.       Order the following functions in terms of Big-O notation: (5 points)

       log(n),  n^1/2, 2ⁿ, nlog(n), n² 

Solution:

logn, n^1/2, nlogn, n², 2ⁿ

b.      Show that if d(n) is O(f(n)) and e(n) is O(g(n)), then d(n)e(n) is O(f(n)g(n)). (10 points)

Solution:

d(n) is O(f(n)) --> exists n₁>0 and c₁>0 such that when n>=n₁, d(n)<c₁f(n)

e(n) is O(g(n) --> exists n₂>0 and c₂>0 such that when n>=n₂, e(n) <c₂g(n)

Let c=c₁ c₂ and n₀=max{n₁, n₂}, then when n>n₀,

d(n)e(n)< c₁f(n)c₂g(n)=c(f(n)g(n) -->  d(n)e(n) is O(f(n)g(n))