COP 4534 Final Exam Questions with
Complete Answers
First Half (1-47)
02: Intuitive Concept - Answer-Finite collection of steps to solve a problem in a
mechanical way.
Formal Concept - Answer-A model of a computer is defined and an algorithm is simply a
program for that ideal computer.
Computability - Answer-Existence of algorithms.
Complexity - Answer-Find algorithms consuming the least amount of resources (time,
space).
Worst-Case Time Complexity - Answer-The function f(n) which is the maximum, over all
inputs of size n, of the sum of the cost of each instruction executed (typical).
(**) Time complexity of an algorithm = running time of an algorithm
Average Time Complexity - Answer-The function f(n) which is the average, over all
inputs of size n, of the sum of the cost of each instruction executed.
Function Growth - Answer-1
log (n)
n
n * log (n)
n^2
n^3
2^n
n!
03: Abstract Data Type (ADT) - Answer-Mathematical model of a data structure. It
specifies logical properties (domain and operations) without implementation details.
i.e. what and not how.
Data Structure - Answer-Involves the implementation details.
Data Structuring Mechanisms:
-Direct access to elements (such as with arrays)
-Sequential access (chaining as with linked lists)
, ADT: List - Answer-A sequence of elements of the same type.
Operations:
-Insert an item in the list at the specified location
-Remove an item from the list at the specified location
-Replace an item at the specified location with another item
-Retrieve an item from the list at the specified location
-Search the list for a given item
Expandable Arrays - Answer-The elements are moved to a larger array each time the
original array is full.
Methods of doing so:
1.) Instantiate a larger array, copy over the elements in a loop, and shallow-copy the
newer array to the old one.
2.) Instantiate a larger array, copy over the elements using System.arraycopy, and
shallow-copy the new array to the old one.
3.) Using java.util.Arrays.copyOf.
ADT: Linked Lists - Answer-A list of items, called nodes, where each node has two
fields:
(1) one containing the information (info)
(2) one that is a reference to the next node in the list (next or link).
*A value of null is needed in the next field of the last node to indicate that no other
elements follow
ADT: Stacks - Answer-The stack ADT consists of a collection of homogeneous (same
type) elements and three basic operations: push , pop and peek (also called top).
-push: insertion
-pop: deletion of most recently inserted element
-peek or top: return the last inserted element
ADT: Queue - Answer-The queue ADT consists of a collection of homogeneous (same
type) elements and two basic operations: insert (also called add or enqueue) and delete
(also called remove or dequeue)
-enqueue: insertion of a new element in the back or rear of the queue
-dequeue: deletion of the front or first element
ADT: Deque (double-ended queue) - Answer-Consists of a collection of homogeneous
(same type) elements and the following operations:
Complete Answers
First Half (1-47)
02: Intuitive Concept - Answer-Finite collection of steps to solve a problem in a
mechanical way.
Formal Concept - Answer-A model of a computer is defined and an algorithm is simply a
program for that ideal computer.
Computability - Answer-Existence of algorithms.
Complexity - Answer-Find algorithms consuming the least amount of resources (time,
space).
Worst-Case Time Complexity - Answer-The function f(n) which is the maximum, over all
inputs of size n, of the sum of the cost of each instruction executed (typical).
(**) Time complexity of an algorithm = running time of an algorithm
Average Time Complexity - Answer-The function f(n) which is the average, over all
inputs of size n, of the sum of the cost of each instruction executed.
Function Growth - Answer-1
log (n)
n
n * log (n)
n^2
n^3
2^n
n!
03: Abstract Data Type (ADT) - Answer-Mathematical model of a data structure. It
specifies logical properties (domain and operations) without implementation details.
i.e. what and not how.
Data Structure - Answer-Involves the implementation details.
Data Structuring Mechanisms:
-Direct access to elements (such as with arrays)
-Sequential access (chaining as with linked lists)
, ADT: List - Answer-A sequence of elements of the same type.
Operations:
-Insert an item in the list at the specified location
-Remove an item from the list at the specified location
-Replace an item at the specified location with another item
-Retrieve an item from the list at the specified location
-Search the list for a given item
Expandable Arrays - Answer-The elements are moved to a larger array each time the
original array is full.
Methods of doing so:
1.) Instantiate a larger array, copy over the elements in a loop, and shallow-copy the
newer array to the old one.
2.) Instantiate a larger array, copy over the elements using System.arraycopy, and
shallow-copy the new array to the old one.
3.) Using java.util.Arrays.copyOf.
ADT: Linked Lists - Answer-A list of items, called nodes, where each node has two
fields:
(1) one containing the information (info)
(2) one that is a reference to the next node in the list (next or link).
*A value of null is needed in the next field of the last node to indicate that no other
elements follow
ADT: Stacks - Answer-The stack ADT consists of a collection of homogeneous (same
type) elements and three basic operations: push , pop and peek (also called top).
-push: insertion
-pop: deletion of most recently inserted element
-peek or top: return the last inserted element
ADT: Queue - Answer-The queue ADT consists of a collection of homogeneous (same
type) elements and two basic operations: insert (also called add or enqueue) and delete
(also called remove or dequeue)
-enqueue: insertion of a new element in the back or rear of the queue
-dequeue: deletion of the front or first element
ADT: Deque (double-ended queue) - Answer-Consists of a collection of homogeneous
(same type) elements and the following operations:
