CS-2852
Study Guide for Final Exam

Study the material according to the outcomes below. If you can address these, you'll be prepared for the Final Exam

Course outcomes to date:

• Understand the semantic behavioral differences (from a user's perspective) between a List, a Stack, and a Queue.
  • Explain what operations are supported by a (pure) Queue
  • Explain what operations are supported by a (pure) Stack
  • Explain what operations are supported by a List.
     
• Be able to analyze the time complexity of algorithms, both sequential and recursive.
  • Derive analytical expressions f(n) for worst-time complexity of arbitrary algorithms
  • Determine Big-O worst-case time complexity of arbitrary algorithms
  • Determine the performance advantage of one algorithm vs. another, given the time complexity of each.
     
• Have a thorough understanding of commonly used library data structures
  • Explain the differences in internal structure between ArrayList, LinkedList, TreeMap, TreeSet, HashSet, and HashMap
  • Explain the differences between singly-linked and doubly-linked lists.
  • Explain what specific behavior is implemented by data structures such as Stack and Queue (even though these structures may use an ArrayList or LinkedList internally)
  • Implement a secondary data structure (such as a queue or stack) according to a specified interface
  • Explain and estimate the performance differences between these data structures for various algorithmic operations, such as add(), contains(target), remove(index), and get(index).
  • Indicate whether a given Binary Tree is also a Binary Search Tree
  • Identify whether a given Binary Search Tree is a Red/Black tree, according to the rules of Red/Black trees.
  • Determine the effect of rotations when applied to nodes of Binary Search Trees
  • Explain the advantages and disadvantages of various data structures in terms of performance (speed) of specific methods, as well as in terms of memory usage.
  • Determine the effect on performance for a Binary Search Tree which is balanced vs. unbalanced.
  • Determine the effect on performance for a HashMap or HashSet when the table has many vs. few index collisions.
  • Explain the differences between a simple Binary Search Tree and an AVL-balanced Binary Search
  • Write a custom hashCode() method for user-defined classes
  • Determine what attributes of a specific data element would be suitable to form a unique Key to be used in a HashMap
  • Determine the index in a hash table a specified key, with a specified hashcode, would map.
  • Illustrate the relationship between elements stored in a hashtable, including the case where collisions occur

   

• Determine/use appropriate algorithms (and associated data structures) to solve complex problems.
  • Given a an example of an application which uses a data structure, justify the choice of one type of data structure over another.
     
• Understand the use of recursion in problem solving
  •  Write recursive methods to perform specific algorithms, such as traversing the internal structure of a Binary Search Trees