EECS 2011 Prof. J. Elder Midterm Review and Data Structures Overview

midterm review n.w
1 / 68
Embed
Share

Explore key topics covered in the EECS 2011 midterm review by Prof. J. Elder, focusing on data structures, object-oriented design principles, software engineering, and important functions in algorithm analysis. The content includes discussions on runtime analysis, Java collections, recursion, trees, priority queues, heaps, and more.

  • EECS
  • Data Structures
  • Object-Oriented Design
  • Software Engineering
  • Algorithm Analysis
rayaanacharya
jveron Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Midterm Review EECS 2011 Prof. J. Elder - 1 - Last Updated: February 11, 2015

  2. Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps EECS 2011 Prof. J. Elder - 2 - Last Updated: February 11, 2015

  3. Data Structures So Far Array List Priority Queue (Extendable) Array Unsorted doubly-linked list Sorted doubly-linked list Node List Heap (array-based) Singly or Doubly Linked List Adaptable Priority Queue Stack Sorted doubly-linked list with location- aware entries Array Singly Linked List Heap with location-aware entries Queue Tree Array Linked Structure Singly or Doubly Linked List Binary Tree Linked Structure Array EECS 2011 Prof. J. Elder - 3 - Last Updated: February 11, 2015

  4. Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps EECS 2011 Prof. J. Elder - 4 - Last Updated: February 11, 2015

  5. Data Structures & Object-Oriented Design Definitions Principles of Object-Oriented Design Hierarchical Design in Java Abstract Data Types & Interfaces Casting Generics Pseudo-Code EECS 2011 Prof. J. Elder - 5 - Last Updated: February 11, 2015

  6. Software Engineering Software must be: Readable and understandable Allows correctness to be verified, and software to be easily updated. Correct and complete Works correctly for all expected inputs Robust Capable of handling unexpected inputs. Adaptible All programs evolve over time. Programs should be designed so that re-use, generalization and modification is easy. Portable Easily ported to new hardware or operating system platforms. Efficient Makes reasonable use of time and memory resources. EECS 2011 Prof. J. Elder - 6 - Last Updated: February 11, 2015

  7. Seven Important Functions Seven functions that often appear in algorithm analysis: Constant 1 Logarithmic log n Linear n N-Log-N n log n Quadratic n2 Cubic n3 Exponential 2n In a log-log chart, the slope of the line corresponds to the growth rate of the function. EECS 2011 Prof. J. Elder - 7 - Last Updated: February 11, 2015

  8. Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps EECS 2011 Prof. J. Elder - 8 - Last Updated: February 11, 2015

  9. Some Math to Review properties of logarithms: logb(xy) = logbx + logby logb (x/y) = logbx - logby logbxa = alogbx logba = logxa/logxb properties of exponentials: a(b+c) = aba c abc = (ab)c ab /ac = a(b-c) b = a logab bc = a c*logab Summations Logarithms and Exponents Existential and universal operators Proof techniques Basic probability existential and universal operators $g"b Loves(b, g) "g$b Loves(b, g) EECS 2011 Prof. J. Elder - 9 - Last Updated: February 11, 2015

  10. Definition of Big Oh cg n ( ) ( ) f n ( ) f n ( ( )) O g n ( ) g n n c n 0 : n , ( ) n f n cg n ( ) , 0 0 EECS 2011 Prof. J. Elder - 10 - Last Updated: February 11, 2015

  11. Arithmetic Progression The running time of prefixAverages1 is O(1 + 2 + + n) 7 6 5 The sum of the first n integers is n(n+ 1) 2 4 3 There is a simple visual proof of this fact 2 1 Thus, algorithm prefixAverages1 runs in O(n2) time 0 1 2 3 4 5 6 EECS 2011 Prof. J. Elder - 11 - Last Updated: February 11, 2015

  12. Relatives of Big-Oh big-Omega f(n) is (g(n)) if there is a constant c > 0 and an integer constant n0 1 such that f(n) c g(n) for n n0 big-Theta f(n) is (g(n)) if there are constants c1 > 0 and c2 > 0 and an integer constant n0 1 such that c1 g(n) f(n) c2 g(n) for n n0 EECS 2011 Prof. J. Elder - 12 - Last Updated: February 11, 2015

  13. Time Complexity of an Algorithm The time complexity of an algorithm is the largest time required on any input of size n. (Worst case analysis.) O(n2): For any input size n n0, the algorithm takes no more than cn2 time on every input. (n2): For any input size n n0, the algorithm takes at least cn2 time on at least one input. (n2): Do both. EECS 2011 Prof. J. Elder - 13 - Last Updated: February 11, 2015

  14. Time Complexity of a Problem The time complexity of a problem is the time complexity of the fastest algorithm that solves the problem. O(n2): Provide an algorithm that solves the problem in no more than this time. Remember: for every input, i.e. worst case analysis! (n2): Prove that no algorithm can solve it faster. Remember: only need one input that takes at least this long! (n2): Do both. EECS 2011 Prof. J. Elder - 14 - Last Updated: February 11, 2015

  15. Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps EECS 2011 Prof. J. Elder - 15 - Last Updated: February 11, 2015

  16. Arrays EECS 2011 Prof. J. Elder - 16 - Last Updated: February 11, 2015

  17. Arrays Array: a sequence of indexed components with the following properties: array size is fixed at the time of array s construction int[] numbers = new int [10]; array elements are placed contiguously in memory address of any element can be calculated directly as its offset from the beginning of the array consequently, array components can be efficiently inspected or updated in O(1) time, using their indices randomNumber = numbers[5]; numbers[2] = 100; EECS 2011 Prof. J. Elder - 17 - Last Updated: February 11, 2015

  18. Arrays in Java Since an array is an object, the name of the array is actually a reference (pointer) to the place in memory where the array is stored. reference to an object holds the address of the actual object Example [ arrays as objects] A B 12 24 37 53 67 int[] A={12, 24, 37, 53, 67}; int[] B=A; A B 12 24 37 5 67 B[3]=5; Example [ cloning an array] 12 24 37 53 67 A int[] A={12, 24, 37, 53, 67}; B 12 24 37 53 67 int[] B=A.clone(); B[3]=5; 12 24 37 53 67 A 12 24 37 5 67 B EECS 2011 Prof. J. Elder - 18 - Last Updated: February 11, 2015

  19. Example Example [ 2D array in Java = array of arrays] int[][] nums = new int[5][4]; int[][] nums; nums = new int[5][]; for (int i=0; i<5; i++) { nums[i] = new int[4]; } EECS 2011 Prof. J. Elder - 19 - Last Updated: February 11, 2015

  20. Array Lists EECS 2011 Prof. J. Elder - 20 - Last Updated: February 11, 2015

  21. The Array List ADT (6.1) The Array List ADT extends the notion of array by storing a sequence of arbitrary objects An element can be accessed, inserted or removed by specifying its rank (number of elements preceding it) An exception is thrown if an incorrect rank is specified (e.g., a negative rank) EECS 2011 Prof. J. Elder - 21 - Last Updated: February 11, 2015

  22. The Array List ADT public interface IndexList<E> { /** Returns the number of elements in this list */ public int size(); /** Returns whether the list is empty. */ public boolean isEmpty(); /** Inserts an element e to be at index I, shifting all elements after this. */ public void add(int I, E e) throws IndexOutOfBoundsException; /** Returns the element at index I, without removing it. */ public E get(int i) throws IndexOutOfBoundsException; /** Removes and returns the element at index I, shifting the elements after this. */ public E remove(int i) throws IndexOutOfBoundsException; /** Replaces the element at index I with e, returning the previous element at i. */ public E set(int I, E e) throws IndexOutOfBoundsException; } EECS 2011 Prof. J. Elder - 22 - Last Updated: February 11, 2015

  23. Performance In the array based implementation The space used by the data structure is O(n) size, isEmpty, get and set run in O(1) time add and remove run in O(n) time In an add operation, when the array is full, instead of throwing an exception, we could replace the array with a larger one. In fact java.util.ArrayList implements this ADT using extendable arrays that do just this. EECS 2011 Prof. J. Elder - 23 - Last Updated: February 11, 2015

  24. Doubling Strategy Analysis We replace the array k = log2n times The total time T(n) of a series of nadd(o) operations is proportional to n + 1 + 2 + 4 + 8 + + 2k= n+ 2k + 1 1 = 2n 1 geometric series 2 Thus T(n) is O(n) 4 1 1 The amortized time of an add operation is O(1)! 8 =1-rn+1 1-r n ri Recall: i=0 EECS 2011 Prof. J. Elder - 24 - Last Updated: February 11, 2015

  25. Stacks Chapter 5.1 EECS 2011 Prof. J. Elder - 25 - Last Updated: February 11, 2015

  26. The Stack ADT The Stack ADT stores arbitrary objects Auxiliary stack operations: Insertions and deletions follow the last-in first-out scheme object top(): returns the last inserted element without removing it integer size(): returns the number of elements stored Think of a spring-loaded plate dispenser Main stack operations: boolean isEmpty(): indicates whether no elements are stored push(object): inserts an element object pop(): removes and returns the last inserted element EECS 2011 Prof. J. Elder - 26 - Last Updated: February 11, 2015

  27. Array-based Stack Algorithmsize() returnt + 1 A simple way of implementing the Stack ADT uses an array Algorithmpop() ifisEmpty() then throw EmptyStackException else t t - 1 returnS[t + 1] We add elements from left to right A variable keeps track of the index of the top element S t 0 1 2 EECS 2011 Prof. J. Elder - 27 - Last Updated: February 11, 2015

  28. Queues Chapters 5.2-5.3 EECS 2011 Prof. J. Elder - 28 - Last Updated: February 11, 2015

  29. Array-Based Queue Use an array of size N in a circular fashion Two variables keep track of the front and rear f index of the front element r index immediately past the rear element Array location r is kept empty normal configuration Q f r 0 1 2 wrapped-around configuration Q r f 0 1 2 EECS 2011 Prof. J. Elder - 29 - Last Updated: February 11, 2015

  30. Queue Operations Algorithmsize() return (N f + r) mod N We use the modulo operator (remainder of division) AlgorithmisEmpty() return (f=r) Note: N-f +r =(r +N)-f Q f r 0 1 2 Q r f 0 1 2 EECS 2011 Prof. J. Elder - 30 - Last Updated: February 11, 2015

  31. Linked Lists Chapters 3.2 3.3 EECS 2011 Prof. J. Elder - 31 - Last Updated: February 11, 2015

  32. Singly Linked List ( 3.2) A singly linked list is a concrete data structure consisting of a sequence of nodes next Each node stores node elem element link to the next node A B C D EECS 2011 Prof. J. Elder - 32 - Last Updated: February 11, 2015

  33. Running Time Adding at the head is O(1) Removing at the head is O(1) How about tail operations? EECS 2011 Prof. J. Elder - 33 - Last Updated: February 11, 2015

  34. Doubly Linked List Doubly-linked lists allow more flexible list management (constant time operations at both ends). prev next Nodes store: element link to the previous node elem node link to the next node Special trailer and header (sentinel) nodes trailer nodes/positions header elements EECS 2011 Prof. J. Elder - 34 - Last Updated: February 11, 2015

  35. Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps EECS 2011 Prof. J. Elder - 35 - Last Updated: February 11, 2015

  36. Iterators An Iterator is an object that enables you to traverse through a collection and to remove elements from the collection selectively, if desired. You get an Iterator for a collection by calling its iterator method. Suppose collection is an instance of a Collection. Then to print out each element on a separate line: Iterator<E> it = collection.iterator(); while (it.hasNext()) System.out.println(it.next()); EECS 2011 Prof. J. Elder - 36 - Last Updated: February 11, 2015

  37. The Java Collections Framework (Ordered Data Types) Iterable Interface Abstract Class Collection Class List Abstract Collection Queue Abstract List Abstract Queue Priority Queue Abstract Sequential List Vector Array List Stack Linked List EECS 2011 Prof. J. Elder - 37 - Last Updated: February 11, 2015

  38. Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps EECS 2011 Prof. J. Elder - 38 - Last Updated: February 11, 2015

  39. Linear Recursion Design Pattern Test for base cases Begin by testing for a set of base cases (there should be at least one). Every possible chain of recursive calls must eventually reach a base case, and the handling of each base case should not use recursion. Recurse once Perform a single recursive call. (This recursive step may involve a test that decides which of several possible recursive calls to make, but it should ultimately choose to make just one of these calls each time we perform this step.) Define each possible recursive call so that it makes progress towards a base case. EECS 2011 Prof. J. Elder - 39 - Last Updated: February 11, 2015

  40. Binary Recursion Binary recursion occurs whenever there are two recursive calls for each non-base case. Example 1: The Fibonacci Sequence EECS 2011 Prof. J. Elder - 40 - Last Updated: February 11, 2015

  41. Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps EECS 2011 Prof. J. Elder - 41 - Last Updated: February 11, 2015

  42. Formal Definition of Rooted Tree A rooted tree may be empty. Otherwise, it consists of A root node r A set of subtrees whose roots are the children of r r B C D E F G H I J K subtree EECS 2011 Prof. J. Elder - 42 - Last Updated: February 11, 2015

  43. Tree Terminology 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. Descendant of a node: child, grandchild, grand-grandchild, etc. Siblings: two nodes having the same parent Depth of a node: number of ancestors (excluding self) Height of a tree: maximum depth of any node (3) Subtree: tree consisting of a node and its descendants A B C D E F G H I J K subtree EECS 2011 Prof. J. Elder - 43 - Last Updated: February 11, 2015

  44. Position ADT The Position ADT models the notion of place within a data structure where a single object is stored It gives a unified view of diverse ways of storing data, such as a cell of an array a node of a linked list a node of a tree Just one method: object element(): returns the element stored at the position EECS 2011 Prof. J. Elder - 44 - Last Updated: February 11, 2015

  45. Tree ADT We use positions to abstract nodes Generic methods: Query methods: integer size() boolean isInternal(p) boolean isEmpty() boolean isExternal(p) Iterator iterator() boolean isRoot(p) Iterable positions() Update method: Accessor methods: object replace(p, o) position root() Additional update methods may be defined by data structures implementing the Tree ADT position parent(p) positionIterator children(p) EECS 2011 Prof. J. Elder - 45 - Last Updated: February 11, 2015

  46. Preorder Traversal A traversal visits the nodes of a tree in a systematic manner AlgorithmpreOrder(v) visit(v) foreach child w of v preOrder (w) In a preorder traversal, a node is visited before its descendants 1 Make Money Fast! 2 5 9 1. Motivations 2. Methods References 6 7 8 3 4 2.3 Bank Robbery 2.1 Stock Fraud 2.2 Ponzi Scheme 1.1 Greed 1.2 Avidity EECS 2011 Prof. J. Elder - 46 - Last Updated: February 11, 2015

  47. Postorder Traversal In a postorder traversal, a node is visited after its descendants AlgorithmpostOrder(v) foreach child w of v postOrder (w) visit(v) 9 cs16/ 8 3 7 todo.txt 1K homeworks/ programs/ 4 5 6 1 2 Robot.java 20K h1c.doc 3K h1nc.doc 2K DDR.java 10K Stocks.java 25K EECS 2011 Prof. J. Elder - 47 - Last Updated: February 11, 2015

  48. Properties of Proper Binary Trees Notation Properties: n number of nodes e = i + 1 e number of external nodes n = 2e - 1 i number of internal nodes h i h height h (n - 1)/2 e 2h h log2e h log2(n + 1) - 1 EECS 2011 Prof. J. Elder - 48 - Last Updated: February 11, 2015

  49. BinaryTree ADT The BinaryTree ADT extends the Tree ADT, i.e., it inherits all the methods of the Tree ADT Additional methods: position left(p) position right(p) boolean hasLeft(p) boolean hasRight(p) Update methods may be defined by data structures implementing the BinaryTree ADT EECS 2011 Prof. J. Elder - 49 - Last Updated: February 11, 2015

  50. Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps EECS 2011 Prof. J. Elder - 50 - Last Updated: February 11, 2015

Related


Midterm Review of International Drug Policy Commitments

Midterm Review of International Drug Policy Commitments

wilbur
Unveiling the Authorship of the Book of James

Unveiling the Authorship of the Book of James

blanka
Midterm Planning Meeting (MPM) Agenda and Objectives

Midterm Planning Meeting (MPM) Agenda and Objectives

kirsten
Life and Legacy of James Armistead Lafayette: A Patriot Spy

Life and Legacy of James Armistead Lafayette: A Patriot Spy

dacre
Physics Midterm 1 Review Guide

Physics Midterm 1 Review Guide

fatimah
Review for Midterm 1 - Physics Concepts and Study Tips

Review for Midterm 1 - Physics Concepts and Study Tips

kame_6
Enhancing Sports and Physical Education at St. James: A Look at the 2014-2015 Initiatives

Enhancing Sports and Physical Education at St. James: A Look at the 2014-2015 Initiatives

tays_67
Analysis of the 2022 Midterm Elections: Red Wave Expectation and Realities

Analysis of the 2022 Midterm Elections: Red Wave Expectation and Realities

rabu_inh
The Epistle of James: Encouraging Genuine Faith and Unity among Jewish Christians

The Epistle of James: Encouraging Genuine Faith and Unity among Jewish Christians

lcha
APUSH Midterm Review Agenda

APUSH Midterm Review Agenda

beem_nu
Design Overview of Midterm Project Team No. 22 - Pedibus

Design Overview of Midterm Project Team No. 22 - Pedibus

jonn_7
Importance of Midterm Review in Project Management: Insights from a Mauritius Case Study

Importance of Midterm Review in Project Management: Insights from a Mauritius Case Study

reng867
Importance of Midterm Review in Mauritius Constituency Workshop

Importance of Midterm Review in Mauritius Constituency Workshop

mmant
Comprehensive Review and Study Tips for CS200 Midterm 2

Comprehensive Review and Study Tips for CS200 Midterm 2

ldim
Stunning Images of James

Stunning Images of James

romanikl
Analyzing the Reign of James I of England: Success or Failure?

Analyzing the Reign of James I of England: Success or Failure?

alexzand
Economic Review and Outlook 2011: Global Trends and Regional Impacts

Economic Review and Outlook 2011: Global Trends and Regional Impacts

rhak
EE359 Lecture 12: Adaptive Modulation & Transmit Diversity Midterm Review

EE359 Lecture 12: Adaptive Modulation & Transmit Diversity Midterm Review

jeo_b
EARLY ALERT GRADE PROPOSAL

EARLY ALERT GRADE PROPOSAL

quam_l
CSE 311 Midterm Review!

CSE 311 Midterm Review!

elc_la
CSE 421 Section 6 Midterm Review Details and Options

CSE 421 Section 6 Midterm Review Details and Options

kahl_9
Insights from ENSUF Midterm Event at JPI Urban Europe

Insights from ENSUF Midterm Event at JPI Urban Europe

uale

More Related Content