CS3 Test 2 Study Guide

Term 20053

Original guide from Prof. Heliotis

• Recursion
  • More complex examples
  • understand how to trace recursive funtions with multiple recursive calls
• Sorting
  • Specific sorts
    • selection sort
    • insertion sort
    • binary search tree
    • quick sort
    • heap sort
    • merge sort
    • counting sort
    • radix sort
  • Analysis of
    • execution time
    • memory required
• Trees
  • Binary and n-ary trees
  • Terms: height/depth, completeness, balance, parent-child-sibling, root, subtree, ancestor, decendant, leaf, interior node, level, full,
  • Traversals
    • breadth-first
    • depth-first
      • pre-order
      • in-order
      • post-order
  • Implementations
    • array - based (balanced binary trees)
    • link node - based
• Graphs
  • Terms: vertex/node, edge/arc, weights, degree, path, cycle, simple path, simple cycle, loop, connectedness, strongly connected, weakly connected, adjacent, path length, degree, in-degree, out-degree, neighbors, sparse, dense, full
  • Implementations
    • linked nodes (extension of a tree)
    • adjacency matrix
    • adjacency list
    • set of nodes & set of edges
  • Analysis of Implementations
    • execution time
      • find/insert/remove edge or vertex
      • process all the neighbors of a vertex
    • memory required

Study Questions

1. What is the ideal pivot value for quick sort?

2. For which sorts could you define a "Big Theta" time complexity, i.e., where their worst- and best-case execution times are the same order?

3a. What universal assumption(s) do all sorting algorithms make about the data they're sorting?

3b. Which of the sorts listed above makes other assumptions about the data?

4. If a tree is recursively defined as a value and zero or more trees, there is one special tree that cannot be defined this way. Which is it?

5. I have a calculator that uses what is called "reverse Polish notation". For example, to calculate ( 5 + 32 ) / ( 13 * ( 0.7 + 2 ) ), I punch the following key sequence ("E" stands for "Enter"):

    5 E 3 2 + 1 3 E 0 . 7 E 2 + * /

6. When is an array a good choice for the implementation of a tree?

7. A data structure is defined as follows:

• The structure consists of nodes and arcs.
• Each arc connects two nodes in the structure.
• Arcs are directed (one node is the source, the other, the sink).
• You can view arcs as "child pointers".
• There are no cycles allowed in the structure.

8. Implement the graph of the cities of New York (with mileages) in three ways you know. Which one uses the least space? Assume characters are one byte, distances are 8-byte floating-point numbers, and object references are 4-byte pointers.