### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Lecture Notes CS 25100 - LE1

Purdue

### View Full Document

## 19

## 0

## Popular in Data Structures And Algorithms

## Popular in ComputerScienence

This 13 page Bundle was uploaded by patel445 on Sunday April 3, 2016. The Bundle belongs to CS 25100 - LE1 at Purdue University taught by Dr.Aliaga in Spring 2016. Since its upload, it has received 19 views. For similar materials see Data Structures And Algorithms in ComputerScienence at Purdue University.

## Reviews for Lecture Notes

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 04/03/16

(2,4)Trees - A multi-way search tree is an ordered tree such that Each internal node has at least two children and stores d 1 key-element items ( ki, oi ), where d is the number of children For a node with children v1 v 2 … v d storing keys k1 k 2 … k d1 keys in the subtree of v1 are less than k1 keys in the subtree of vi are between ki1 and ki ( i = 2, …, d 1) keys in the subtree of v d are greater than k d1 The leaves store no items and serve as placeholders - We can extend the notion of inorder traversal from binary trees to multi-way search trees - Namely, we visit item ( ki, oi ) of node v between the recursive traversals of the subtrees of v rooted at children vi and vi 1 - An inorder traversal of a multi-way search tree visits the keys in increasing order - Similar to search in a binary search tree -Reaching an external node terminates the search unsuccessfully - Similar to search in a binary search tree - Reaching an external node terminates the search unsuccessfully - Similar to search in a binary search tree - Reaching an external node terminates the search unsuccessfully - A (2,4) tree (also called 2-4 tree or 2-3-4 tree) is a multi-way search with the following properties - Theorem: A (2,4) tree storing n items has height O(log n ) -Search Depends on height of tree, thus searching in a (2,4) tree with n items takes O(log n ) - We reduce deletion of an item to the case where the item is at the node with leaf children - Otherwise, we replace the item with its inorder successor (or, equivalently, with its inorder predecessor) and delete the latter item - Deleting an item from a node v may cause an underflow, where node v becomes a 1-node with one child and no keys - To handle an underflow at node v with parent u, we consider two cases in the next slides Avl Trees - AVL trees are balanced - An AVL Tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at most 1 - Insertion is as in a binary search tree - Always done by expanding an external node - perform the rotations needed to make b the topmost node of the three - Removal begins as in a binary search tree, which means the node removed will become an empty external node. Its parent, w, may cause an imbalance. - Let z be the first unbalanced node encountered while travelling up the tree from w. Also, let y be the child of z with the larger height, and let x be the child of y with the larger height. - We perform restructure(x) to restore balance at z. - As this restructuring may upset the balance of another node higher in the tree, we must continue checking for balance until the root of T is reached - a single restructure is O(1) using a linked-structure binary tree - find is O(log n) height of tree is O(log n), no restructures needed - insert is O(log n) initial find is O(log n) Restructuring up the tree, maintaining heights is O(log n) - remove is O(log n) initial find is O(log n) Restructuring up the tree, maintaining heights is O(log n) Algorithms -An algorithm is a step-by-step procedure for solving a problem in a finite amount of time. -Most algorithms transform input objects into output objects. -The running time of an algorithm typically grows with the input size. -Average case time is often difficult to determine -We focus on the worst case running time. –Easier to analyze -Crucial to applications such as games, finance and robotics -It is necessary to implement the algorithm, which may be difficult -Results may not be indicative of the running time on other inputs not included in the experiment. -In order to compare two algorithms, the same hardware and software environments must be used -Uses a high-level description of the algorithm instead of an implementation -Characterizes running time as a function of the input size, n. -Takes into account all possible inputs -Allows us to evaluate the speed of an algorithm independent of the hardware/software environment -Changing the hardware/ software environment Affects T(n) by a constant factor But does not alter the growth rate of T(n) -The linear growth rate of the running time T(n) is an intrinsic property of algorithm arrayMax - In a log-log chart, the slope of the line corresponds to the growth rate of the function - The growth rate is not affected by constant factors or lower- order terms - Given functions f( n) and g ( n ), we say that f( n) is O (g ( n)) if there are positive constants c and n0 such that f( n ) cg ( n) for n n 0 -The asymptotic analysis of an algorithm determines the running time in big-Oh notation - To perform the 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-Oh notation -We further illustrate asymptotic analysis with two algorithms for prefix averages Hashing - A log file is a dictionary implemented by means of an unsorted sequence We store the items of the dictionary in a sequence (based on a doubly-linked lists or a circular array), in arbitrary order - The log file is effective only for dictionaries of small size or for dictionaries on which insertions are the most common operations, while searches and removals are rarely performed (e.g., historical record of logins to a workstation) - A hash function h maps keys of a given type to integers in a fixed interval [0, N 1] - The integer h (x ) is called the hash value of key x - When implementing a dictionary with a hash table, the goal is to store item ( k, o ) at index i h ( k ) - We design a hash table for a dictionary storing items (SSN, Name), where SSN (social security number) is a nine-digit positive integer - Ideally, storage and access performance is O(1)! - The goal of the hash function is to “disperse” the keys in an apparently uniform random way -- but it is not random! - Linear probing handles collisions by placing the colliding item in the next (circularly) available table cell - Uses a concept called “open addressing”: the colliding item is placed in a different cell of the table - Each table cell inspected is referred to as a “probe” - Double hashing uses a secondary hash function d( k) and handles collisions by placing an item in the first available cell of the series ( i jd( k)) mod N for j 0, 1, … , N 1 - The secondary hash function d( k) cannot have zero values - In the worst case, searches, insertions and removals on a hash table take O ( n) time - The worst case occurs when all the keys inserted into the dictionary collide - The load factor n N affects the performance of a hash table - The expected running time of all the dictionary ADT operations in a hash table is O(1) - In practice, hashing is very fast provided the load factor is not large Heaps - A priority queue stores a collection of items - Main methods of the Priority Queue ADT - Keys in a priority queue can be arbitrary objects on which an order is defined - Two distinct items in a priority queue can have the same key - A comparator encapsulates the action of comparing two objects according to a given total order relation - A generic priority queue uses a comparator as a template argument, to define the comparison function () - The comparator is external to the keys being compared. Thus, the same objects can be sorted in different ways by using different comparators - When the priority queue needs to compare two keys, it uses its comparator - We can use a priority queue to sort a set of comparable elements - The running time of this sorting method depends on the priority queue implementation - Selectionsort is the variation of PQsort where the priority queue is implemented with an unsorted sequence Running time of Selectionsort: Inserting the elements into the priority queue with n insertItem operations takes O ( n) time Removing the elements in sorted order from the priority queue with n removeMin operations takes time proportional to 1+2 +…+n - A heap is a binary tree storing keys at its internal nodes and satisfying the following properties: - We can use a heap to implement a priority queue We store a (key, element) item at each internal node We keep track of the position of the last node For simplicity, we show only the keys in the pictures - Method insertItem of the priority queue ADT corresponds to the insertion of a key k to the heap - After the insertion of a new key k, the heaporder property may be violated - Algorithm upheap restores the heaporder property by swapping k along an upward path from the insertion node - Upheap terminates when the key k reaches the root or a node whose parent has a key smaller than or equal to k - After replacing the root key with the key k of the last node, the heaporder property may be violated - Algorithm downheap restores the heaporder property by swapping key k along a downward path from the root - Upheap terminates when key k reaches a leaf or a node whose children have keys greater than or equal to k - In a regular queue, you can explicitly keep the headindex and tailindex, or the headindex and the size - In a priority queue, you can explicitly keep the headpointer (root) and the tailpointer (last node), or the headpointer and the size Queues - The Queue ADT stores arbitrary objects - Insertions and deletions follow the first-in first-out scheme - Insertions are at the rear of the queue and removals are at the front of the queue - Main queue operations: enqueue(Object o): inserts an element o at the end of the queue dequeue(): removes and returns the element at the front of the queue - Auxiliary queue operations: front(): returns the element at the front without removing it size(): returns the number of elements stored empty(): returns a Boolean indicating whether no elements are stored - Exceptions Attempting the execution of dequeue or front on an empty queue throws an EmptyQueueException - Direct applications Waiting lists, bureaucracy Access to shared resources (e.g., printer) Multiprogramming - Indirect applications Auxiliary data structure for algorithms Component of other data structures - Operation enqueue throws an exception if the array is full - This exception is implementationdependent - Operation dequeue throws an exception if the queue is empty - This exception is specified in the queue ADT - In an enqueue operation, when the array is full, instead of throwing an exception, we can replace the array with a larger one - Similar to what we did for an array-based stack - The enqueue operation has amortized running time O(n) with the incremental strategy O(1) with the doubling strategy - Informal C++ interface for our Queue ADT - Requires the definition of class EmptyQueueException - A corresponding built-in STL class exists Red Black Trees - Currently, we perform constant time “tree-correction” operations that maintain the O(log n ) tree height - A red-black tree is a representation of a (2,4) tree by means of a binary tree whose nodes are colored red or black - In comparison with its associated (2,4) tree, a red-black tree has same logarithmic time performance simpler implementation with a single (binary-tree-like) node type - A red-black tree can also be defined as a binary search tree that satisfies the following properties: - Since a red-black tree is a binary tree, the search algorithm for a red- black search tree is the same as that for a binary search tree - By the above theorem, searching in a red-black tree takes O(log n ) time - To perform operation insertItem ( k, o ), we execute the insertion algorithm for binary search trees - To perform operation insertItem(k, o), we search for key k - Assume k is not already in the tree, and let w be the leaf reached by the search - We insert k at node w and expand w into an internal node - A restructuring remedies a child-parent double red when the parent red node has a black sibling - It is equivalent to restoring the correct replacement of a 4-node - The internal property is restored and the other properties are preserved - There are several restructuring configurations depending on whether the double red nodes are left or right children - A recoloring remedies a child-parent double red when the parent red node has a red sibling - The parent v and its sibling w become black and the grandparent u becomes red, unless it is the root - It is equivalent to performing a split on a 5-node - The double red violation may propagate to the grandparent u - To perform operation remove ( k ), we first execute the deletion algorithm for binary search trees - To perform operation, we search for key k (e.g., remove 4) - If node v has one leaf child u, we remove v and u from the tree with operation removeAboveExternal ( u ) - To perform operation remove ( k ), we first execute the deletion algorithm for binary search trees - Divide-and conquer is a general algorithm design paradigm: - The base case for the recursion are subproblems of constant size - Analysis can be done using recurrence equations Stacks - An abstract data type (ADT) is an abstraction of a data structure - An ADT specifies: Data stored Operations on the data Error conditions associated with operations - The Stack ADT stores arbitrary objects - Insertions and deletions follow the last-in first-out scheme - Think of a spring-loaded plate dispenser - Main stack operations: push(object o): inserts element o pop(): removes and returns the last inserted element - Auxiliary stack operations: top(): returns a reference to the last inserted element without removing it size(): returns the number of elements stored empty(): returns a Boolean value indicating whether no elements are stored - In the Stack ADT, operations pop and top cannot be performed if the stack is empty - Attempting the execution of pop or top on an empty stack throws an EmptyStackException - Direct applications Page-visited history in a Web browser Undo sequence in a text editor Saving local variables when one function calls another, and this one calls another, and so on. - Indirect applications Auxiliary data structure for algorithms Component of other data structures - The C++ run-time system keeps track of the chain of active functions with a stack - When a function returns, its frame is popped from the stack and control is passed to the method on top of the stack - A simple way of implementing the Stack ADT uses an array - We add elements from left to right - The array storing the stack elements may become full - We show how to use a stack as an auxiliary data structure in an algorithm - In a push operation, when the array is full, instead of throwing an exception, we can replace the array with a larger one Skip Lists - A skip list for a set S of distinct (key, element) items is a series of lists S0, S1 , … , Sh such that Each list Si contains the special keys and List S0 contains the keys of S in increasing order Each list is a subsequence of the previous one, i.e., S0 S1 … Sh List Sh contains only the two special keys - We search for a key x in a a skip list as follows: We start at the first position of the top list At the current position p, we compare x with y key (after (p)) x y: we return element (after (p)) x y: we “scan forward” x y: we “drop down” If we try to drop down past the bottom list, we return NO_SUCH_KEY - A randomized algorithm performs coin tosses (i.e., uses random bits) to control its execution - Its running time depends on the outcomes of the coin tosses - We analyze the expected running time of a randomized algorithm under the following assumptions the coins are unbiased, and the coin tosses are independent - The worst-case running time of a randomized algorithm is often large but has very low probability (e.g., it occurs when all the coin tosses give “heads”) - We use a randomized algorithm to insert items into a skip list - We repeatedly toss a coin until we get tails, and we denote with i the number of times the coin came up heads - To remove an item with key x from a skip list, we proceed as follows: - We can implement a skip list with quad-nodes - The space used by a skip list depends on the random bits used by each invocation of the insertion algorithm - We use the following two basic probabilistic facts: - Fact 1: The probability of getting i consecutive heads when flipping a coin is 1 2i - Fact 2: If each of n items is present in a set with probability p, the expected size of the set is np - The running time of the search an insertion algorithms is affected by the height h of the skip list - We show that with high probability, a skip list with n items has height O(log n ) - The drop-down steps are bounded by the height of the skip list and thus are O(log n) with high probability - To analyze the scan-forward steps, we use yet another probabilistic fact: - When we scan forward in a list, the destination key does not belong to a higher list - By Fact 4, in each list the expected number of scanforward steps is 2 - A skip list is a data structure for dictionaries that uses a randomized insertion algorithm - Using a more complex probabilistic analysis, one can show that these performance bounds also hold with high probability - Skip lists are fast and simple to implement in practice Trees - In computer science, a tree is an abstract model of a hierarchical structure - A tree consists of nodes with a parent-child relation - Applications: Organization charts File systems Programming environments - Root: node without parent (A) - Internal node: node with at least one child (A, B, C, F) - External node (a.k.a. leaf ): node without children (E, I, J, K, G, H, D) - Ancestors of a node: parent, grandparent, grand-grandparent, etc. - Depth of a node: number of ancestors - Height of a tree: maximum depth of any node (3 - Descendant of a node: child, grandchild, grand-grandchild, etc. - Subtree: tree consisting of a node and its descendants - We use positions to abstract nodes - Generic methods: integer size() boolean isEmpty() objectIterator elements() positionIterator positions() - Accessor methods: position root() position parent(p) positionIterator children(p) - Query methods: boolean isInternal(p) boolean isExternal(p) boolean isRoot(p) - Additional update methods may be defined by data structures implementing the Tree ADT - A binary tree is a tree with the following properties: Each internal node has two children The children of a node are an ordered pair - We call the children of an internal node left child and right child - Alternative recursive definition: a binary tree is either a tree consisting of a single node, or a tree whose root has an ordered pair of children, each of which is a binary tree - Applications: arithmetic expressions decision processes searching - A traversal visits the nodes of a tree in a systematic manner - In a preorder traversal, a node is visited before its descendants -Application: print a structured document - In a postorder traversal, a node is visited after its descendants - Application: compute space used by files in a directory and its subdirectories - Binary tree associated with a decision process internal nodes: questions with yes/no answer external nodes: decisions - The BinaryTree ADT extends the Tree ADT, i.e., it inherits all the methods of the Tree ADT - A node is represented by an object storing Element Parent node Left child node Right child node

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.