Dsa Comp610 - Chapter 1 Exam Questions With Correct Answers.

DSA COMP610 - CHAPTER 1 EXAM
QUESTIONS WITH CORRECT
ANSWERS



Principles of Soft Eng - Correct Answers -Correctness, Reliability, Robustness,
Usability, Maintainability, Reusability, Portability, Efficiency

-
+
#
UML meaning - Correct Answers -- private
+ public
# protected

Inheritance - Correct Answers -White arrow. Is a. where a subclass extends a
superclass, such as a Car class extending a more general Vehicle class.
This is often described as an is-a relationship, and is indicated on a UML diagram as a
line with an open arrowhead pointing from the subclass to the superclass.

Association - Correct Answers -Straight line. where there is a relation-ship between the
instances (objects) created from two classes, such as in-stances of a Car class with
instances of a Driver class.

O (n) - Correct Answers -algorithms that execute in linear time, such as a linear search
of an unordered list of values

O (n log2 n) - Correct Answers -algorithms that execute in linear-logarithmic time, such
as the faster sorting algorithms like quick sort or heap sort

O(n2) - Correct Answers -algorithms that execute in quadratic time, such as the slower
sorting algorithms like selection sort or insertion sort

Aggregation - Correct Answers -backwards WHITE diamond. Has a. where objects from
one class are comprised, at least in part, from objects created from another class, such
as a Car object is an ag- gregation of various other objects in- cluding a RoofRack
object.

, Composition - Correct Answers -backwards RED diamond which is a special type of
aggregation which emphasizes that the part can belong to only one whole, such as a
Car class and an Engine class.

Implementation - Correct Answers -Dotted white arrow. where one class implements the
methods declared in an interface, such as a Car class and aTransporter interface.

Dependency - Correct Answers -Dotted black arrow. where one class uses an- other for
an operation (generically called a service) it provides, such as a Car class and a Road
class.
Car drives on Road

What is efficiency of algorithm based on? - Correct Answers -The efficiency of an
algorithm can be measured based on various factors (such as memory usage, storage,
or network resources), but most commonly is measured in terms of CPU time, giving an
indication of how fast the program will execute.

What is a growth function? - Correct Answers -the relationship between the complexity
f(n) of an algorithm (such as time or number of operations)and the size n of the problem

What is asymptotic complexity? - Correct Answers -the behaviour of the dominant term
(the term that increases the quickest for large values of n) in the growth function as n
increases.

O(1) - Correct Answers -for algorithms that execute in constant time regardless of n,
such as appending items to a list

O (log2 n) - Correct Answers -algorithms that execute in logarithmic time (either log2 n
or log n), such as a binary search of an ordered list of values

O (n3) - Correct Answers -algorithms that execute in cubic time, such as Gaussian
elimi- nation

O (2n) - Correct Answers -algorithms that execute in exponential time, such as
algorithms that require checking possible combinations

Example of O(1) - Correct Answers -System.out.println("Some operation");

Example of O(n) - Correct Answers -for (int i=0; i<n; i++)
System.out.println("Some operation");

example of O (log2 n) - Correct Answers -for (int i=1; i<n; i*=2)
System.out.println("Some operation");

example of O (n2) - Correct Answers -for (int i=0; i<n; i++) { for (int j=0; j<i; j++)
System.out.println("Some operation"); }