Shared Flashcard Set

Details

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

Additional Computer Science Flashcards

 


 

Cards

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 [15] {6} 8 2 14 7 [15 move one forword]
6 15 {8} 2 14 7
temp = 8 6 [15] {8} 2 14 7 [15 move one forword]
[6] 15 2 14 7
[15 move one forword and compare with previous element no movement insert temp after 6]
6 8 15 2 14 7
temp = 2 6 8 [15] {2} 14 7 [15 move one forword]
6 [8] 15 14 7
[8 move one forword]
[6] 8 15 14 7
[6 move one forword insert temp into proper place]
2 6 8 15 {14} 7
temp =14 2 6 8 [15] {14} 7 [15 move one forword]
2 6 [8] 15 7
[ insert temp just after when previous element is not greater.
temp = 7 2 6 8 14 [15] {7} [15 move one forword]
2 6 [8] 14 15
[14 move one forword]
2 [6] 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} [6] 8 2 14 24 16 18 [no swapping move forward]

5 {6} [8] 2 14 24 16 18 [no swapping move forward]

5 6 {8} [2] 14 24 16 18 [swapping move forward]

5 6 2 {8} [14] 24 16 18 [no swapping move forward]

5 6 2 8 {14} [24] 16 18 [no swapping move forward]

5 6 2 8 14 {24} [16] 18 [swapping move forward]

5 6 2 8 14 16 {24} [18] [swapping move forward]

5 6 2 8 14 16 18 24 [swapping move forward first phase over again start with first index]

{5} [6] 2 8 14 16 18 24 [no swapping move forward]

5 {6} [2] 8 14 16 18 24 [swapping move forward]

5 2 {6} [8] 14 16 18 24 [no swapping move forward]

5 2 6 {8} [14] 16 18 24 [no swapping move forward their is no further swaping in the phase start next phase]

{5} [2] 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 it
private—only in the class definition itself
int 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

Overloading

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
ArrADT isPresent
Definition
[image]
Term
Arr ADT isFUll
Definition
[image]
Term
ArrADT is Empty
Definition
[image]
Term
ArrADT Delete
Definition
[image]
Term
ArrADT Insert
Definition
[image]
Term
ArrADT getAverage
Definition
[image]
Term
 Arr ADT findsLeast
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 first 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 defined recursively if its definition 

consists of the following two parts: 

1. Base case 

This must be a well defined termination 

2. Inductive or recursive steps 

This consists of well defined 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!