# Shared Flashcard Set

## Details

data structures and algorithms
Midterm
81
Computer Science
03/11/2011

Term
 Recursion Method
Definition
 [image]
Term
 Towers of Hanoi
Definition
 [image]
Term
 Insertion Sort
Definition
 Insertion sort is a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists, and often is used as part of more sophisticated algorithms. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one. The insertion sort works just like its name suggests - it inserts each item into its proper place in the final list. The simplest implementation of this requires two list structures - the source list and the list into which sorted items are inserted. To save memory, most implementations use an in-place sort that works by moving the current item past the already sorted items and repeatedly swapping it with the preceding item until it is in place. Shell sort (see below) is a variant of insertion sort that is more efficient for larger lists. This method is much more efficient than the bubble sort, though it has more constraints.   Insertion Sort:- In insertion sort pick a element{ } and insert it into proper place. Start with second element shift it into 'temp' and compare with first element[ ] if first element is greater then move it one forword. temp = 6  {6} 8 2 14 7 [15 move one forword]6 15 {8} 2 14 7temp = 8 6  {8} 2 14 7 [15 move one forword] 15 2 14 7 [15 move one forword and compare with previous element no movement insert temp after 6]6 8 15 2 14 7temp = 2 6 8  {2} 14 7 [15 move one forword]6  15 14 7 [8 move one forword] 8 15 14 7 [6 move one forword insert temp into proper place]2 6 8 15 {14} 7temp =14 2 6 8  {14} 7 [15 move one forword]2 6  15 7 [ insert temp just after when previous element is not greater.temp = 7 2 6 8 14  {7} [15 move one forword]2 6  14 15 [14 move one forword]2  8 14 15 [8 move one forword]2 6 7 8 14 15 [ insert temp just after when previous element is not greater.
Term
 Bubble Sort
Definition
 Bubble sort is a straightforward and simplistic method of sorting data that is used in computer science education. The algorithm starts at the beginning of the data set. It compares the first two elements, and if the first is greater than the second, it swaps them. It continues doing this for each pair of adjacent elements to the end of the data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass. While simple, this algorithm is highly inefficient and is rarely used except in education. A slightly better variant, cocktail sort, works by inverting the ordering criteria and the pass direction on alternating passes. Its average case and worst case are both O(n²). Bubble Sort:- In bubble sort elements are compared with just next element if first{ } is greater than second[ ] then swap. {5}  8 2 14 24 16 18 [no swapping move forward] 5 {6}  2 14 24 16 18 [no swapping move forward] 5 6 {8}  14 24 16 18 [swapping move forward] 5 6 2 {8}  24 16 18 [no swapping move forward] 5 6 2 8 {14}  16 18 [no swapping move forward] 5 6 2 8 14 {24}  18 [swapping move forward] 5 6 2 8 14 16 {24}  [swapping move forward] 5 6 2 8 14 16 18 24 [swapping move forward first phase over again start with first index] {5}  2 8 14 16 18 24 [no swapping move forward] 5 {6}  8 14 16 18 24 [swapping move forward] 5 2 {6}  14 16 18 24 [no swapping move forward] 5 2 6 {8}  16 18 24 [no swapping move forward their is no further swaping in the phase start next phase] {5}  6 8 14 16 18 24 [swapping move forward] 2 5 6 8 14 16 18 24 Finaly array is arranged in ascending order.
Term
 Selection sort
Definition
 Selection sort is a simple sorting algorithm that improves on the performance of bubble sort. It works by first finding the smallest element using a linear scan and swapping it into the first position in the list, then finding the second smallest element by scanning the remaining elements, and so on. Selection sort is unique compared to almost any other algorithm in that its running time is not affected by the prior ordering of the list: it performs the same number of operations because of its simple structure. Selection sort also requires only n swaps, and hence just Θ(n) memory writes, which is optimal for any sorting algorithm. Thus it can be very attractive if writes are the most expensive operation, but otherwise selection sort will usually be outperformed by insertion sort or the more complicated algorithms. [{5} 6 8 2 14 24 16 (1)] unsorted array. Find the smallest element( ) in array and swap with first element{ } of unsorted array[ ]. 1 [{6} 8 (2) 14 24 16 5]. Do the same process again. 1 2 [{8} 6 14 24 16 (5)]. 1 2 5 [{(6)} 14 24 16 8]. 1 2 5 6 [{14} 24 16 (8)]. 1 2 5 6 8 [{24} 16 (14)]. 1 2 5 6 8 14 [{(16)} 24]. 1 2 5 6 8 14 16 [{(24)}]. 1 2 5 6 8 14 16 24. Finaly got the Sorted array
Term
 Insertion Sort Code
Definition
 [image]
Term
 Binary Search Code
Definition
 [image]
Term
 Selection Sort Code
Definition
 [image]
Term
 Linear Search Code
Definition
 [image]
Term
 Insertion Sort code(check against virginias to)
Definition
 [image]
Term
 Bubble Sort Code
Definition
 [image]
Term
 Name for Big O, Omega and theta
Definition
 Asymptotic bounds
Term
 What are Access Specifiers available in Java?
Definition
 Access specifiers are keywords that determines the type of access to the member of a class. These are: Public Protected Private Defaults
Term
 Explain the Encapsulation principle.
Definition
 Encapsulation is a process of binding or wrapping the data and the codes that operates on the data into a single entity. This keeps the data safe from outside interface and misuse. One way to think about encapsulation is as a protective wrapper that prevents code and data from being arbitrarily accessed by other code defined outside the wrapper.
Term
 Upper bound (complicated)
Definition
 First, it is important to clarify what big-O actually is. Technically speaking, it describes what is called an asymptotic upper bound. Rigorously, we can say that f(x) is an asymptotic upper bound of g(x) if and only if there exist constants k and xinitial, such that k times f(x) ≥ g(x) ≥ 0 for all values of x greater than xinitial. If f(x) is an asymptotic upper bound of g(x) this can be denoted by writing g(x) = O(f(x)). Basically, an asymptotic upper bound of a function is any function which eventually becomes greater than or equal to that function and stays greater than it forever, if it is multiplied by some arbitrary constant. It is important to note that even if f(x) is an upper bound of g(x), f(x) < g(x) can hold for all x. Because big-O denotes an upper bound, it should be used to describe the worst-case runtime of an algorithm.
Term
 Lower Bound
Definition
 Next up is big-Omega (denoted as Ω(something)). Ω denotes an asymptotic lower bound. Its rigorous definition is the same as big-O's, except that it f(x) is between (inclusive) zero and g(x) for all values of x greater than xinitial. Ω Notation should be used for specifying the minimum runtime of an algorithm.
Term
 big theta
Definition
 Building on these two notations, we come to big-Theta notation (denoted as Θ(something). We can rigorously define Θ as denoting a function which is both an asymptotic upper and lower bounds. That is, g(x) = Θ(f(x)) if, and only if, g(x) = Ω(f(x)) and g(x) = O(f(x)). As you may be able to guess, big-Theta is an asymptotically tight bound. Some texts choose to define big-Theta separately and then prove the above definition as a theorem, but either way works. Also, some texts choose to use O to represent an asymptotically tight bound. My understanding is that the norm is to use Θ.
Term
 Example for static
Definition
 18 the age you can vote would be static. Age would need not to be static cause it would all be potentially different.
Term
 Visibility modifiers
Definition
 Public—anyone can use itprivate—only in the class definition itselfint z; nothing—package visibility any class in the same package can acess it.java.util.Scanner ways of accessing packages
Term
 Method names
Definition
 Get- Getters get functions (get) accessor Set -mutator functions Boolean accessors—inquisitors normally begin with is iaAStudent  Scope is the special extent in which the object or variable can be used visibile in its scope invisible out of its scope
Term
Definition
 Choose to over laod if you want to do a bunch of other things if they should all have the same name A bunch of different things but they are all analogs of eachother You would want to use getName on a human/animal/ for readability purposes   Overloading is allowed if signature is different. Need to change order.
Term
 Passing by value
Definition
 the copy that gets passed .   Important because you cant updated the actual parameter. More or less true for primitive  True for reference type because it stores the address.  Allows you to update.
Term
 Wrapper class
Definition
 is one of eight classes provided in the `java.lang` package to provide object methods for the eight primitive types. All of the primitive wrapper classes in Java are immutable.J2SE 5.0 introduced autoboxing of primitive types into their wrapper object, and automatic unboxing of the wrapper objects into their primitive value—the implicit conversion between the wrapper objects and primitive values.
Term
 Different Wrapper Classes
Definition
 [image]
Term
 Static
Definition
 Static means all the methods share the same var everyone else gets their own.
Term

# The ? : operator in Java

Definition
 The value of a variable often depends on whether a particular boolean expression is or is not true and on nothing else. For instance one common operation is setting the value of a variable to the maximum of two quantities. In Java you might write ``````if (a > b) { max = a; } else { max = b; } `````` Setting a single variable to one of two states based on a single condition is such a common use of `if-else` that a shortcut has been devised for it, the conditional operator, ?:. Using the conditional operator you can rewrite the above example in a single line like this: `max = (a > b) ? a : b;`   `(a > b) ? a : b;` is an expression which returns one of two values, `a` or `b`. The condition, `(a > b)`, is tested. If it is true the first value, `a`, is returned. If it is false, the second value, `b`, is returned. Whichever value is returned is dependent on the conditional test, `a > b`. The condition can be any expression which returns a boolean value.
Term
Definition
 [image]
Term
Definition
 [image]
Term
Definition
 [image]
Term
Definition
 [image]
Term
Definition
 [image]
Term
Definition
 [image]
Term
Definition
 [image]
Term
 Best/worst/ average for Linear Sort
Definition
 [image]
Term
 best/worst/average binary search
Definition
 [image]
Term
 RTF
Definition
 running time function tells us how much time an algorithm takes for n being the varying of the problem.
Term
 why n-1 for a sorting function?
Definition
 To prove an upper bound of n − 1 we just need to give an algorithm. For instance, consider the algorithm that in step 1 puts the smallest item in location 1, swapping it with whatever was originally there. Then in step 2 it swaps the second-smallest item with whatever is currently in location 2, and so on (if in step k, the kth-smallest item is already in the correct position then we just do a no-op). No step ever undoes any of the previous work, so after n − 1 steps, the ﬁrst n − 1 items are in the correct position. This means the nth item must be in the correct position too.
Term
 Running time function for Linear Search
Definition
 Best Case   Lower bound : Ω(1) Upper Bound : O(1) Best Case Def would be: Θ (1) if element is in the first slot   Worst Case   Lower bound : Ω(n) Upper Bound : O(n) Best Case Def would be: Θ (n) if element searches through whole array     Average Case Θ(n/2) = Θ(n) element is in the last slot or not in array   General TL(n)==O(n) Ω(1) will get dropped because its assumed
Term
 Running time function for Adder method
Definition
 Best Case Lower bound : Ω(n) Upper Bound : O(n) Best Case Def would be: Θ (n) if element is in the first slot   Worst Case   Lower bound : Ω(n) Upper Bound : O(n) Best Case Def would be: Θ (n) if element searches through whole array     Average Case  Θ(n)   General TA(n)==Θ(n) will always need to go through all elements
Term
 Running time function for Binary Search
Definition
 Best Case Lower bound : Ω(1) Upper Bound : O(1) Best Case Def would be: Θ (1) if element is in the first slot   Worst Case   Lower bound : Ω(n) Upper Bound : O(log n) Best Case Def would be: Θ (Log2 n) if element searches through whole array   Average Case Θ(log n)  element is in the last slot or not in array   General TB(n)==O(log n) is not theta because best and worst are not similar, so you take the worst.
Term
 Running time For Selection Sort
Definition
 Best Case   Lower bound : Ω(n2) Upper Bound : O(n2) Best Case Def would be: Θ (n2)   Worst Case Lower bound : Ω(n2) Upper Bound : O(n2) Best Case Def would be: Θ (n2) Average Case Θ(n2)    General TL(n)==Θ(n2)
Term
 Running time function for Insertion Sort  look into
Definition
 Best Case   Lower bound : Ω(n) Upper Bound : O(n) Best Case Def would be: Θ (n)   Worst Case Lower bound : Ω(n2) Upper Bound : O(n2) Best Case Def would be: Θ (n2) Average Case Θ(n2)    General TL(n)==O(n2)
Term
 Runtime Function of Bubble Sort
Definition
 Best Case   Lower bound : Ω(n2) Upper Bound : O(n2) Best Case Def would be: Θ (n2)   Worst Case Lower bound : Ω(n2) Upper Bound : O(n2) Best Case Def would be: Θ (n2) Average Case Θ(n2)    General TB(n)==Θ(n2)
Term
 Running Time function for Quick Sort
Definition
 Best Case   Lower bound : Ω(n2) Upper Bound : O(n2) Best Case Def would be: Θ (n2)   Worst Case Lower bound : Ω(n log n) Upper Bound : O(n log n) Best Case Def would be: Θ (n log n) Average Case Θ(n log n)    General TB(n)==Ω(n2) & O(n log n)//double check
Term
 universal quanitfier
Definition
 upside down A.
Term
 Stack Search
Definition
 [image]
Term
 Stack Is Empty
Definition
 [image]
Term
 Stack Display
Definition
 [image]
Term
 Stack Push
Definition
 [image]
Term
 Stack Pop
Definition
 [image]
Term
 Stack Peek
Definition
 [image]
Term
 Stack Constructor
Definition
 [image]
Term
 Factors that affect running time
Definition
 [image]
Term
 Sigma explained
Definition
 [image]
Term
 Fibonachi concept wrong
Definition
 This program prints out the first 20 numbers in the Fibonacci sequence. Each term is formed by adding together the previous two terms in the sequence,starting with the terms 1 and 1.
Term
 Fibonachi Code
Definition
 [image]
Term
 Fibonachi output
Definition
 [image]
Term
 Queue Constructor
Definition
 [image]
Term
 Queue Insert
Definition
 [image]
Term
 Queue Remove
Definition
 [image]
Term
 Queue Display
Definition
 [image]
Term
 # of moves needed for tower of Hanoi
Definition
 2n -1
Term
 Towers of Hanoi Site
Definition
 http://www.animatedrecursion.com/intermediate/towersofhanoi.html
Term
 Copy Array 1
Definition
 [image]
Term
 Copy Array 2
Definition
 [image]
Term
 Copy Array 3
Definition
 [image]
Term
 Reverse Array
Definition
 [image]
Term
 Randomize Array
Definition
 [image]
Term
 .This and this()
Definition

The most common reason for using the `this` keyword is because a field is shadowed by a method or constructor parameter.

For example, the `Point` class was written like this

```public class Point {
public int x = 0;
public int y = 0;

//constructor
public Point(int a, int b) {
x = a;
y = b;
}
}
```
but it could have been written like this:
```public class Point {
public int x = 0;
public int y = 0;

//constructor
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
```
Each argument to the constructor shadows one of the object's fields — inside the constructor `x` is a local copy of the constructor's first argument. To refer to the `Point` field `x`, the constructor must use `this.x`.

### Using `this` with a Constructor

From within a constructor, you can also use the `this` keyword to call another constructor in the same class. Doing so is called anexplicit constructor invocation. Here's another `Rectangle` class, with a different implementation from the one in the Objects section.
```public class Rectangle {
private int x, y;
private int width, height;

public Rectangle() {
this(0, 0, 0, 0);
}
public Rectangle(int width, int height) {
this(0, 0, width, height);
}
public Rectangle(int x, int y, int width, int height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
...
}
```
This class contains a set of constructors. Each constructor initializes some or all of the rectangle's member variables. The constructors provide a default value for any member variable whose initial value is not provided by an argument. For example, the no-argument constructor calls the four-argument constructor with four 0 values and the two-argument constructor calls the four-argument constructor with two 0 values. As before, the compiler determines which constructor to call, based on the number and the type of arguments.

If present, the invocation of another constructor must be the first line in the constructor.

Term
 Access Levels of modifiers
Definition
Term
 Garbage Collection
Definition
 Some object-oriented languages require that you keep track of all the objects you create and that you explicitly destroy them when they are no longer needed. Managing memory explicitly is tedious and error-prone. The Java platform allows you to create as many objects as you want (limited, of course, by what your system can handle), and you don't have to worry about destroying them. The Java runtime environment deletes objects when it determines that they are no longer being used. This process is called garbage collection. An object is eligible for garbage collection when there are no more references to that object. References that are held in a variable are usually dropped when the variable goes out of scope. Or, you can explicitly drop an object reference by setting the variable to the special value null. Remember that a program can have multiple references to the same object; all references to an object must be dropped before the object is eligible for garbage collection.   The Java runtime environment has a garbage collector that periodically frees the memory used by objects that are no longer referenced. The garbage collector does its job automatically when it determines that the time is right.
Term
 4 types of Recursive methods
Definition
 sigma factoral fibonacci towers of hanoi
Term
 Sigma equation
Definition
 (n/2)(n+1)
Term
 Sorting methods from worst to best
Definition
 worst - bubble mid- selection sort best insertion sort
Term
 String methods
Definition
 s.charAt(0) String s="name";System.out.println(s.length());The output is 4 String s="VaVavavav";System.out.println(s.replace('v','V'));The output is VaVaVaVaV   String s="Vaibhav";System.out.println(s.equalsIgnoreCase("VAIBHAV"));The output is true   String s="abcdefghi";System.out.println(s.substring(5));System.out.println(s.substring(5,8));The output would be" fghi "" fg " String s="AbcdefghiJ";System.out.println(s.toLowerCase()); Output is " abcdefghij "   String s="hey here is the blank space ";System.out.println(s.trim())The output is " heyhereistheblankspace"   String s="AAAAbbbbb";System.out.println(s.to UpperCase());The output is " AAABBBB "
Term
 Factorial Recursive method
Definition
 int myFactorial( int integer){if( integer == 1)     return 1;else       {       return(integer*(myFactorial(integer-1);       }}
Term
 Sigma recursive method
Definition
 static int sigma(int n) {       int f=0;  if (n< 1)      f=0;  else {         f=n+sigma(n-1);       return f;  }
Term
 Two parts of a recursive method
Definition
 In general, a function is said to be deﬁned recursively if its deﬁnition  consists of the following two parts:  1. Base case  This must be a well deﬁned termination  2. Inductive or recursive steps  This consists of well deﬁned inductive (or recursive) steps that  must lead to a termination state.
Term
 fibonacci Recursive code
Definition
 static int fibonacciItem(int n) {  int f=0;     if (n=1 || n=2) {       return =1;      else                        return=fibonacciItem(n-1)+fibonacciItem(n-2);  }
Supporting users have an ad free experience!