Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
132 Cards in this Set
- Front
- Back
What are the 3 pillars of OOP
|
Classes, Interfaces, Inheritance & Polymorphism
|
|
What are the Principles of OOP
|
Abstraction , Encapsulation, Modularity
|
|
Abstraction : ___
|
Distill a complicated system to itsmost fundemental parts and then describe these in simple but precise language (DocuString)
|
|
What does Abstraction improve
|
Design Transparency, Easier to predict behavior
|
|
Encapsulation : ___
|
Componenets should hide internal details for other components. Hide implementation details datafields )
|
|
Why do you need Encapsulation
|
You dont need to know the workings of a combustion engine to drive a car or Know the internals of Telecommunication to switch to go to another channel on TV
|
|
What does encapsulation improve
|
The adaptaility of the program, you can implement details that do not affect other parts.
|
|
Modularity:___
|
The different components of a system should be separated into independent functional units .
|
|
What does Modularity improve
|
Modularity enhances the reusablity of the program: Modules can easily be used in other programs.
|
|
Classes and Objects contain which of the principles
|
Abstraction and Modularity
|
|
Interfaces contain which of the principles of OOP
|
Encapsulation and Modularity
|
|
Inheritance contains which of the principles of OOP
|
Abstraction and Reuse of Code
|
|
What do classes and Objects do interms of state and functionality
|
Classes and Objects encapsulate state and functionality into modules
|
|
What do classes and Objects do interms of implementation details
|
Classes and Objects hide implemntation details
|
|
Create a bank account in OOP.
|
class Bank Account { private int balance = 21321 ; private String owner = "Me" public BankAccount(String owner) {} }
|
|
What do interfaces do in Java
|
Define types and behavior ; They are independent of functionality
|
|
What does inheritance do in Java
|
Define both behavior and partial functionality, inherited by subclasses
|
|
Example of inheritance
|
class Super {....} ; class Sub extends Super { .... }
|
|
What are Abstract classes?
|
Cannot be instantiatied only inherited, abstract class Super{...} NOT POSSILE to o Super newsupe = new Super() NOT POSSIBLE
|
|
How does Polymorphism affect an object
|
Polymorphism is the ability of an object to take on many forms.
|
|
What is a common use of polymorphism in OOP ?
|
A common use of polymorphism in OOP occurs when a parent class wreference is used to refer to a child class object
|
|
What can yhou do to write a signle method to print an array of Int, String , Dates and Objects
|
Generics!
|
|
Write a generic ArrayPrinter class
|
public class ArrayPrinter { public void printArray(E[] inputArray) { for E element : inputArray { System.out.println("%s", element) }} }
|
|
How do we use Interfaces in OOP
|
We define common behavior
|
|
We declare class variables as private why ?
|
we can get and set methods to access data not make it public
|
|
How can we improve our programs using abstraction
|
Think about how to abstract away implementation details from the user
|
|
What can we do to promote modular design and code-reuse
|
Use Inheritance in our programs
|
|
When should we use generics
|
In ALL data structures.
|
|
What is an ADT ?
|
Mathematic models of data structures .
|
|
What do ADTs specify
|
They types of data stored, operations , types of the operation parameters
|
|
Do ADTs specify operations?
|
Yes
|
|
ADTs specify types of the operations parameters?
|
Yes
|
|
Is a List an example of an ADT
|
Yes
|
|
What is a list
|
A sequence of zero or more linearlly ordered elements of a given type
|
|
What are some of the operations on a list
|
setEmpty() , First() , Next(), Add(v) , Remove(v)
|
|
What do ADTs express?
|
Specifying what each operation does NOT how they do it.
|
|
How is an ADT expressed in JAVA
|
an ADT is expressed by an interface or abstract class
|
|
What do ADTs do ?
|
Specify what data structure is used and how each operation works
|
|
How is an ADT realized
|
By a data structure implemented in one or more classes , Classes then specify how the operations are performed..
|
|
Map coloring problem , all neighbours have diffenent colors and the number of colors is minimal. How do we represent the map
|
A linked list
|
|
What are algorithms
|
A finite sequence of instructions each of which has a clear meaning and can be performed within a finite length of time and with a finite amount of effort.
|
|
What are the three required properties of Algorithms
|
Unambiguous (Clear meaning) , Executable (can be performed) , Terminating( finite length of time)
|
|
What does an algorithm description contain
|
A set of inputs (data) for whcih the algorithm is designed(legal input) and the output that results from the algortihm (data or behavior) if any legal input is provided.
|
|
What would an example for a greedy algorithm for colorMap be.
|
Try to color as many nodes as possible with the first color and then as many as possible of the uncolored nodes with the second color and so on.." To color nodes with a new color, the new steps are performed: "Select uncolored vertex and color it with the new color" For each uncolored vertex determine whether it has an edge to any vertex already colored with the color. If there is no such edge color the present vertex with the color, otherwise use a new color.
|
|
Why is the algorithm called Greedy?
|
Because it colors a node whenever it can without thinking of the potential drawbacks
|
|
ADTs can describe ________ ______ that can be applied to any programming language
|
Conceptual models
|
|
What type of lists are there
|
Index-Based, Postitions , Linked Lists
|
|
What is an Index Based List
|
Index based list extends the notion of an array by storing a sequence of arbritrary objects
|
|
How are elements accessed in an Index Based List
|
Elements can be accessed inserted or removed by specifying their rank or r (number of elements preceding it)
|
|
How would you return an element at rank r from an IBL called A of size N
|
A[r] or A.get(r)
|
|
How are elements inserted into a list
|
In the operation add(r,object) with an array called A with n occupied elements , we would add the object at r by moving the n-r elements further down the list .
|
|
How are elements removed from a list
|
In the operation remove(r) we need to fill the hole removed by the removed element by shifting backward the n-r-1 elements A[r+1],.... A[n-1]
|
|
What is a position ADT
|
It is a way to store data within an encapsulating data structure :
|
|
What is a simple implementation of a position ADT
|
public interface Position { E getElement() Position getNext(); }
|
|
What is a linked list
|
It is a list that stores elements at nodes or positions
|
|
What are two types of linked lists?
|
Signly-linked , Double-linked
|
|
What is a singly linked list?
|
A concrete data structure consisting of a sequence of positions. Each position stores an element and a link to the next position
|
|
What is the difference between a singly and double linked list
|
There is a prevPosition() method
|
|
How is insertion performed for a node q between p and its successor n
|
p's nextposition needs to shift from n to q , and n's prevPosition needs to shift from p to q . qs next and previous position will then become n and p respectively
|
|
How is deletion performed for a node q between its successor n and previous node p
|
ps next position needs to go to n and ns prev position needs to go to p . q should then get garbage collected or deleted by cutting off all next / previous positions.
|
|
What are the downsides to index based lists?
|
linear time0
|
|
What is a Stack
|
Last in First Out .
|
|
What are some of the main operations on a Stack
|
push(e), pop(), isEmpty() , size() , top()
|
|
What does push(e) do on a Stack
|
push(element) : Insert an Element to the top of the stack
|
|
What does pop(e) do ?
|
pop() : remove AND return last inserted element.
|
|
Create an Interface for a Stack
|
public interface Stack { ; element pop() ; void push(element) ; boolean isEmpty() ; element top(); int size(); }
|
|
What are some Direct applications of a Stack
|
Direct applications : Page visited history in a Web browser ; Undo sequence in a text editor ; Chain of method calls in a program;
|
|
What are some inDirect application
|
Auxiliary data structures for algorithms ; Component of other Data Structures
|
|
Explain how the chain of methods called is implemented using a stack
|
When a method is called the system pushes on the stack containing (Local variables and return values , Program counter keeping track of the statement being executed. When the method ends its frame is popped from the stack and contral is passed to the method ontop of the stack.
|
|
What is an Array based stack
|
Adding elemtns fromleft to right, and a variable keeps track of the index of the top element
|
|
What are some potential problems with an Array Based Stack
|
The array storing the stack elements may become full and a push operation will then either grow the array or signal an error.
|
|
What is a Queue
|
First in First Out
|
|
What are some operations on a queue
|
enqueue(e) ; dequeue() ; size() ; first() ; isEmpty()
|
|
What does enqueue(e) do ?
|
enqueue(e) : inserts e at the end of the queue and; int size() returns the number of elements in the queue in integers; element first() returns the first element in the queue
|
|
What does dequeue() do ?
|
e dequeue() : removes and returns element at the front of the queue
|
|
What does size() do?
|
int size() returns the number of elements in the queue
|
|
What does isEmpty() do?
|
isEmpty() returns true if the queue has 0 elements false otherwise
|
|
What are some Direct applications of a Queue
|
Access to shared resource (eg Printer) , MultiThreaded programming
|
|
What are some inDirect applications of a Queue
|
Auxiliary data structures for algorithms ; Component of other Data Structures
|
|
What is an Array based Queue
|
Regular removal / Insertion at front , it uses a circular array which keeps track of f(index of front element) n(number of elements)
|
|
When the queue has fewer than N elements what is the array location of the first empty slot past the rear of the queue?
|
r = (f+n) % N
|
|
Using the ABQ concept code methods for enqueue and dequeue.
|
public void enqueue(element v) { a[f+n % a.length] = v ; n++ } public E dequeue() { n-- ; element ret = a[f] ; f = (f+1) % a.length; return ret }
|
|
What are some properties of Algorithms
|
running time & storage space
|
|
What determines the complexity of an algorithm?
|
Its running time and its storage space.
|
|
What are some of the central questions regarding algorithm analysis
|
What is the performance How does an algorithm scale Classification of algorithms based on their complexity , Are there theoretical bounds on how fast we can perform certain taskts
|
|
How does the running time of an algorithm typically respond to increase in the input size
|
It increases
|
|
What are the types of measurements we take for running time
|
Worst case , Best case and Average
|
|
Experimental Algorithm analysis is performed how?
|
1. Write a program implementing an Algorithm 2) Capture information on the time it takes and varying input size and composition 3) Plot the results
|
|
What are some challenges to Experimental Algorithm Analysis
|
Implementing the algorithm may be difficult (Stage 1) ; Inputs may not be included in the experiment (Stage 2) ; In order to compare 2 algorithms the same harware and software should be used (All stages)
|
|
How is Theoretical Algorithm Analysis performed
|
High level description of algorithms instead of implementations(Stage 1) ; Characterize running time as a function of input size n (Stage 2) ; take into account all possible inputs (stage 2) ; evaluate an algorith independent of the hardware software environment (All stages)
|
|
What is Psuedo code
|
High level description of an algorithm; More structured thatn English prose; Less detailed than a program ; Preferred notation for describing algorithms;
|
|
What are some drawbacks of Psuedocode ??
|
Hides program design issues
|
|
What are some of psuedocodes syntax for control flow
|
if...then...[else..] ; while.. do... ; repeat.. until..; for...do... ; Indentation replaces braces(#python)
|
|
What are some of the pseudocode syntax for method declaration and method calls
|
Algorithm method ( arg [,arg ...]) ; Input... ; Output... ||| Method call : method (arg [, arg..])
|
|
What are some of the syntax for pseudocode return values and expressions
|
return expression || <- Assignment , = Equality testing , n^2 superscripts and other mathematical formatting allowed.
|
|
What are Primitive operations
|
Basic Operations performed by an algorithm, Identifiable in pseudocode mostly independent from programming languages ; Exact definition is not important
|
|
How long are Primitive Operations Expected to take to compute
|
A constant amount of time
|
|
How can we find out the maimum number of primitive operations executed by an Algorithm as a function of its input size
|
By inspecting the pseudocode and its
|
|
in the Lecture 1 how many operations does arrayMax execute worst case
|
7n - 2
|
|
What is the growth rate of the number of operations not affected by
|
Constant factors (122n) or Lower order terms (105n^2 + 108n is a quadratic function)
|
|
How do we deterin an algorithms worst case running tim
|
First we look at how to classify the algorithm
|
|
What are the seven algorithm classes
|
Constant 1; Logarithmic Log n ; Linear n ; N-Log-N nlogn ; Quadratic n^2 ; Cubic n^3 ; Exponential a^n
|
|
What is the fundemental formula for Big O notation
|
Given function f(n) and g(n) we say that f(n) is O(g(n) if there is a positive constant c and n0 such that: f(n) <= cg(n) for all n>= n0
|
|
What is an example of the fundemental big O notation
|
2n + 10 is O(n) ,, g(n) = n , f(n) = 2n+10 , 2n +10 <= cn ; 10 <= cn - 2n ; 10<= n(c-2) ; 10/(c-2) <= n .. Pick c= 3 and n0 = 10
|
|
What is an example of how n^2 is not O(n)
|
n^2 <= cn ; n<= c ; Cannot be true because c has to be a constant
|
|
The big-O notation gives a ____ bound on the growth rate of a function.
|
Upper
|
|
What does the statement f(n) is O(g(n) ) mean ?
|
The statement f(n) is O(g(n)) means that the growth rate of f(n) is no more than the growth rate of g(n)
|
|
What can we use big-O notation for
|
To rank functions according to their growth rate
|
|
If f(n) is a polynomial of degree d , then ..
|
f(n) is O(n^d) . ie Drop lower order terms / Drop constant factors
|
|
f(n) = (n + n ) + (n +n) what is big O
|
O(n) NOT O(n2)
|
|
3n + 5 is what in big O notation
|
O(n) NOT O(3n)
|
|
Use the simplest ___ of the class for big O notation
|
Expression
|
|
Use the ____ possible ___ of function
|
smallest, class
|
|
What is the Asymptotic Analysis of an Algorithm
|
It determins the running time in bigO notation
|
|
How do we perform asymptotic analysis
|
We find the worst case number of primitive operations executed as a function of the input size , We express this function with big O notation
|
|
What is the Asymptotic Analysis of the arrayMax algorithm
|
The algorithm arrayMax runs in O(n) time
|
|
Why does the arrayMax algorithm run in O(n) time
|
contant factors and lower order terms are eventually dropped and we can discard them when counting primitive operations
|
|
Taking the Lecture 1s prefixAverages(X,n) algortihm what is the running time ?
|
O(1+ 2+ 3+ ... +n)
|
|
prefixAverages has O(1+2+3...+n) running time What is the sum of the first n integers?
|
n(n+1) /2 , 1/2 n^2 + n/2 --> O(n^2)
|
|
Why does prefixAverages2 run in O(n) time instead of O(n2)
|
There is no nested for loop which creates a 1+2+3+...+n-1 summation
|
|
Array/ Linked Complexity for size()?
|
O(1), O(1)
|
|
Array/ Linked Complexity for isEmpty()
|
O(1), O(1)
|
|
Array/ Linked Complexity for atRank()
|
O(1), O(n)
|
|
Array/ Linked Complexity for rankOf()
|
O(1) , O(n)
|
|
Array/ Linked Complexity for elemAtRank()
|
O(1), O(n)
|
|
Array/ Linked Complexity for first, last , before , after
|
O(1) , O(1)
|
|
Array/ Linked Complexity for replaceElement() , swapElements()
|
O(1), O(1)
|
|
Array/ Linked Complexity for insertAtRank, removeAtRank
|
O(n), O(n)
|
|
Array/ Linked Complexity for insertFirst , insertLast
|
O(1), O(1)
|
|
Array/ Linked Complexity for insertAfter, insertBefore
|
O(n) , O(1)
|
|
Array/ Linked Complexity for remove
|
O(n), O(1)
|
|
Array/ Linked Complexity for replaceAtRank
|
O(1) , O(n)
|