Please see the listed topics. Also, please no copy/paste from the book site. I h

Question

Please see the listed topics. Also, please no copy/paste from the book site. I have read these already. I need 2 pages of notes that cover the listed topics. Best would be someones personally created notes for a data structure exam. I am aware of current cheat sheets and notes from online. I am looking for a tried a true 2 page document that will be enough to pass a data structure exam.

http://algs4.cs.princeton.edu/home/

Introduction to Java, Iteration and Recursion (1.1)

Data Abstraction, Objects, References (1.2)

Bags, Queues and Stacks: Linked Structures (1.3)

More Linked Structures (1.3)

Analysis (1.4)

Union-Find (1.5)

Elementary Sorts, Comparators (2.1)

Priority Queues (2.4)

Mergesort, Quicksort (2.2, 2,3)

Explanation / Answer

Java

Java is an object oriented programming language programming language created by James Gosling from Sun Microsystems (Sun) in 1991. The first publicly available version of Java (Java 1.0) was released in 1995.Sun Microsystems was acquired by the Oracle Corporation in 2010. Oracle has now the steermanship for Java.From the Java programming language the Java platform evolved. The Java platform allows software developers to write program code in other languages than the Java programming language which still runs on the Java virtual machine. The Java platform is usually associated with the Java virtual machine and the Java core libraries.

Recursion:

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion

Many mathematical functions can be defined recursively:

Many problems can be solved recursively, eg games of all types from simple ones like the Towers of Hanoi problem to complex ones like chess. In games, the recursive solutions are particularly convenient because, having solved the problem by a series of recursive calls, you want to find out how you got to the solution. By keeping track of the move chosen at any point, the program call stack does this housekeeping for you! This is explained in more detail later.

Example: Factorial

One of the simplest examples of a recursive definition is that for the factorial function:

Iteration:

Iteration

Data abstraction refers to, providing only essential information to the outside world and hiding their background details, i.e., to represent the needed information in program without presenting the details.

Data Abstraction

Data abstraction is a programming (and design) technique that relies on the separation of interface and implementation.

Let's take one real life example of a TV, which you can turn on and off, change the channel, adjust the volume, and add external components such as speakers, VCRs, and DVD players, BUT you do not know its internal details, that is, you do not know how it receives signals over the air or through a cable, how it translates them, and finally displays them on the screen.

Objects

As the name object-oriented implies, objects are key to understanding object-oriented technology. You can look around you now and see many examples of real-world objects: your dog, your desk, your television set, your bicycle.

These real-world objects share two characteristics: they all have state and they all have behavior. For example, dogs have state (name, color, breed, hungry) and dogs have behavior (barking, fetching, and slobbering on your newly cleaned slacks). Bicycles have state (current gear, current pedal cadence, two wheels, number of gears) and behavior (braking, accelerating, slowing down, changing gears).

Software objects are modeled after real-world objects in that they, too, have state and behavior. A software object maintains its state in variables and implements its behavior with methods.

Refereneces:

References might be implemented by storing the address. Usually Java references will be implemented as pointers, but that's not required by the specification. They may be using an additional layer of indirection to enable easier garbage collection. But in the end it will (almost always) boil down to (C-style) pointers being involved in the implementation of (Java-style) references.

Bags:

Queues:

A queue (pronounced /?kju?/ kew) is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once an element is added, all elements that were added before have to be removed before the new element can be invoked. A queue is an example of a linear data structure.

Stacks:

A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack. The basic concept can be illustrated by thinking of your data set as a stack of plates or books where you can only take the top item off the stack in order to remove things from it. This structure is used all throughout programming.

The basic implementation of a stack is also called a LIFO (Last In First Out) to demonstrate the way it accesses data, since as we will see there are various variations of stack implementations.

There are basically three operations that can be performed on stacks . They are 1) inserting an item into a stack (push). 2) deleting an item from the stack (pop). 3) displaying the contents of the stack(pip).

Union-Find

The union-find system maintains a collection of disjoint sets that cover a "universal" set of interest. For example the universe might be the set of vertices of a graph. At any time the sets in the collection are disjoint and cover the universe. This means that each element of the universe is in exactly one set of the collection.

The key functions are initialize(), union(x, y), y = find(x). We will use a metaphore of companies. The elements in the universe are "workers", find(x) returns the CEO of the company x works for. union(x, y) performs a merger of the companies that x and y work for. initialize() establishes a situation in which everyone is self employed, each worker in the universe is a company of one.

The system works by maintaining a vector of "bosses". For each worker x, boss[x] records the current boss of x. If x is a CEO, boss[x] == x. Union is by rank. Always rank[x] < rank[boss[x]], unless x is a CEO.

Priority queue:

A priority queue acts like a queue in that you dequeue an item by removing it from the front. However, in a priority queue the logical order of items inside a queue is determined by their priority. The highest priority items are at the front of the queue and the lowest priority items are at the back. Thus when you enqueue an item on a priority queue, the new item may move all the way to the front.

Merge Sort:

Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems.

To sort A[p .. r]:

1. Divide Step

If a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].

2. Conquer Step

Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].

3. Combine Step

Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).

Note that the recursion bottoms out when the subarray has just one element, so that it is trivially sorted.

Quick Sort:

When deciding on the best sorting algorithm we often look at its worst-case running time, and base our decision solely on that factor. That is why beginning programmers often overlook quicksort as a viable option because of its T(n^2) worst-case running time, which could be made exponentially unlikely with a little effort. In fact, quicksort is the currently fastest known sorting algorithm and is often the best practical choice for sorting, as its average expected running time is O(n log(n)).

Quicksort, like mergesort, is a divide-and-conquer recursive algorithm. The basic divide-and-conquer process for sorting a subarray S[p..r] is summarized in the following three easy steps:

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.