• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Jul 18th, 2019 94 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
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
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
27. Motivations for Linked Lists as opposed to Dynamic 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
49. Use a Queue!
50. Recursion, Recursion, Recursion!
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.
Top