• Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

Card Range To Study

through

image

Play button

image

Play button

image

Progress

1/132

Click to flip

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)