a guest Jul 18th, 2019 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Python Basics
  2. Not a "focus" of the exam per se, but you definitely need to be able to write correct code. We won't be testing things like deep vs shallow copy as we did in midterm 1, for example -- but it will be hard to answer questions if you are not able to read and write python code fluently.
  3. Asymptotic Analysis
  4. Again, not a main focus point, but you will need to understand asymptotic analysis (Big-Oh and friends) to be able to answer questions. For example, we may ask you to implement something to run in $$O(n)$$ (or linear time)
  5. Dynamic Arrays
  6. Again, much of what we've done since midterm 1 builds on the ideas from this topic (e.g., implementations of Stack and Queue) so you will need to be familiar with them.
  7. Recursion
  8. We've been using recursion quite a bit (e.g., with linked lists and binary trees), so you will need to be very comfortable with recursion for the exam.
  9. Abstraction: Interface vs Implementation
  10. You need to be comfortable with the idea that the interface (methods/operations it provides) of an Abstract Data Type are separate from the implementation of that ADT.
  11. There may be multiple ways to implement a given ADT.
  12. The running times of an ADT's operations depends on the implementation.
  13. Stacks
  14. The Stack ADT
  15. The Stack data model (LIFO)
  16. Operations on a stack
  17. Ways to implement a Stack
  18. Dynamic Array Implementation (done in class, as ArrayStack) and the running times of the operations in this implementation
  19. Linked List Implementation, using a Doubly LL (done in lab) and the running times of the operations in this implementation
  20. Queues
  21. The Queue ADT
  22. First-in First-out (FIFO) data model
  23. Operations on a queue
  24. Implementing a Queue with a "circular array"
  25. Understand the concept of circular arrays and how the mod operation helps achieve the "circular" part
  26. Linked Lists
  27. Motivations for Linked Lists as opposed to Dynamic Arrays
  28. The tradeoffs of using linked lists vs arrays
  29. singly vs doubly linked list
  30. The DoublyLinkedList class we wrote in lecture
  31. Running times of the DoublyLinkedList operations
  32. How we can use linked lists (specifically, doubly LLs) to implement data structures such as stacks and queues
  33. Rooted Trees
  34. Definitions of properties in trees
  35. Child, parent, descendant, ancestor
  36. Subtree
  37. Edge, Path
  38. "Level" of a node, height of a tree
  39. Binary Tree, Full binary tree, complete binary tree
  40. Implementing methods for trees. Examples include:
  41. Counting the number of nodes in the tree
  42. Computing the sum of the values in the nodes
  43. Computing the height of a tree
  44. Traversing a tree with recursion (variants of "depth-first" traversal):
  45. Preorder
  46. Inorder
  47. Postorder
  48. Traversing a tree "breadth-first"
  49. Use a Queue!
  50. Recursion, Recursion, Recursion!
  51. Map ADT
  52. Operations of a Map
  53. Key/Value association (the Map data model)
  54. Implementing a Map
  55. With an unsorted array
  56. inefficient: O(n) running time for operations
  57. We implemented this in lecture, as UnsortedArrayMap
  58. Actual (real-world) implementations of the Map ADT don't do this -- it's too inefficient!
  59. With a sorted array
  60. inefficient: find is O(log n) but insert/delete are O(n)
  61. We didn't implement this, but understand the idea of how it would work and why it's still inefficient
  62. Again, this is not done in real-world implementations of Map ADT
  63. With a linked list: inefficient
  64. O(n) running time for operations, for both sorted and unsorted
  65. We didn't implement this, but understand the idea of how it would work and why it's still inefficient
  66. Real world implementations of Map ADT don't do this -- it's too inefficient
  67. With a Binary Search Tree -- more efficient
  68. We are implementing this in lecture now
  69. Will not be tested on the implementation details (for this exam, anyway)
  70. Just know what the "Binary Search Tree" property is
  71. We haven't gone over the running times of the operations for this implementation yet. Won't be tested on Midterm 2.
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand