CISC 220

Midterm Review

Prof. Christopher Rasmussen

http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021 

​

University of Delaware

Fall, 2021

Midterm Details

• Thursday, October 21
• Covers all lectures through Thursday, Oct. 14 class
• Closed book, no notes, no calculators, cell phones, etc.
• Worth 20% of your grade (same as final)
• Question types (see posted 2010 midterm)
• Data structure ADTs, application examples
• Definitions, compare/contrast approaches, etc.
• Write C++ code for some small functions
• No questions about file I/O or inheritance
• Calculate, name, rank big-O complexities of various operations
• Carry out operations and show steps (tree traversals, rotations, etc.)

​

Topics Covered

• C++ background, concept of abstract data type (Drozdek, 1.1-1.4 (skip 1.4.5), 1.7-1.8)
• Algorithm analysis (Drozdek, 2.1-2.3, 2.5-2.7)
• Linked lists (Drozdek, 3.1-3.2, 3.7-3.8)
• Stacks & queues (Drozdek, 4.1-4.2, 4.4-4.5)
• Trees (Drozdek, 6.1-6.3, 6.4-6.4.2, 6.5-6.6 (skip 6.6.1, 6.7-6.7.2 (skip 6.7.1))
• Expression trees (6.12 in 4th ed., 6.10 in 3rd.)

​

C++ background

• Drozdek Chapter 1 slides
• Pointers: & and *
• Arrays (and their relationship to pointers)
• New/delete -- Dynamic vs. static allocation
• Classes vs. objects
• Constructor, copy constructor, destructor
• “Shallow” copying and defaults constructor/destructor/assignment vs. overloading
• Operator overloading
• Function and class templates, STL

Linear data structures, lists

• Drozdek Chapter 3 slides, Chapter 4 slides
• Array-based implementation of stacks, queues
• Code details for insert(), remove() functions
• Stack: insert = push, remove = pop
• Queue: insert = enqueue, remove = dequeue
• Big-O time complexity
• Inefficiency of shift operation for queues => circular array
• Singly-linked list implementation of stacks, queues
•  queue needs tail pointer for efficiency
• Doubly-linked list implementation of deques
• enqueue and dequeue at both ends
• For which of these operations is SLL inefficient?

​

Algorithm Analysis

• Drozdek Chapter 2 slides
• Counting "worst case" number of primitive operations
• Be able to do this for functions with nested for loops, conditionals, etc.
• Big-O definition: f(n) is O(g(n)) if there are positive c, n₀ such that f(n) <= g(n) for n >= n₀
• Simplification of operation count function by dropping constant factors, pulling out biggest term
• Major big-O categories and ordering
• Constant = O(1)
• Logarithmic = O(log n)
• Linear = O(n)
• Linearithmic = O(n log n)
• Quadratic = O(n²)
• Polynomial = O(n^k), Exponential = O(kⁿ)

Trees

• Drozdek Chapter 6 slides
• Terminology: Child, parent, leaf, height, etc.
• Representation
• General case: nodes + first child/next sibling pointers
• Binary trees: nodes +left/right child pointers
• Traversals
• Pre-order, post-order, in-order
• Expression trees
• Binary trees for representing arithmetic or logical expressions
• Internal nodes = operators, leaves = operands
• Which traversal to use for printing, evaluation, etc.
• Binary search trees
• Search order property: keys in left subtree smaller, right keys bigger
• Details of contains/insert/remove/etc.

AVL trees

• Drozdek Chapter 6 slides
• Self-balancing binary trees to keep O(log n) performance
• Definition of height balance property
• Balance notation...calculating height difference (+1, 0, -1, etc.) at each node
• Definition of left, right rotation at a node
• Analysis of node balance after insert/remove:
• Which nodes need to have height balance updated?
• How to decide whether single, double, or no rotation is necessary to fix?
• How many rotations need to be done in the worst case after an insert()?  After a remove()?

​