Final exam topics

Final Exam Review Sheet -- CS 235, Fall 2018

The final will be comprehensive — any topic covered in the class from the beginning is fair game.  However, because the midterm already covered topics addressed in the first half of the course, the final will be weighted slightly more heavily towards the content covered since the midterm.

Below are the list of general topics that are fair game for the final exam.  Under each topic are lists of topics or questions you should be familiar with.  These sub-topics are not necessarily exhaustive, but they should be helpful in stirring up (perhaps horrible) memories of what we have covered in the course in order to help you realize what you do and do not know.

 

Topics likely covered for the midterm:

  • Command-line arguments
    • Know how to give command-line parameters to a program using the command-line.
    • Know how to receive command-line arguments in your program.
  • Definitions, operations, and uses of lists, sets, maps, stacks, queues, priority queues.  Be able to identify when you would use each data structure.
  • Recursion
    • Mathematical induction
    • Basic principles of recursion
    • Be able to read, understand, and correct errors in recursive functions
  • Big Oh notation
    • What is Big-Oh notation and why is it important?
    • Identify the Big-Oh of snippets of code
    • Know (or know how to compute) the Big-Oh of various functions
  • Logarithms
    • Understand what a logarithm is and how log n increases with increased n
  • Binary Search
    • Understand the algorithm and why it is useful
  • Sorting: selection sort, insertion sort, merge sort, quick sort
    • Understand the algorithms and their strengths and weaknesses

 

Topics covered after the midterm:

  • Linked Lists
    • Know how to implement and manipulate linked lists.  You should be able to write code that manipulates linked lists, such as inserting or removing from a linked list.
    • Know the Big-Oh of the various operations
  • Trees
    • basic definitions (what is a tree? what is the height of the tree? what is the height/depth of a node, etc.)
  • Tree Traversal
    • Be able to write code that performs pre-order, in-order, or post-order traversals.
    • Identify when to use pre-order, in-order, or post-order traversals
    • Breadth-first searches
  • Binary Search Trees (BSTs)
    • Definition
    • Understand Insert, Remove, Find (and the Big-Oh of these functions)
  • AVL trees
    • Definition
    • Understand Insert, Remove Find (and the Big-Oh of these functions)
  • Hash Tables
    • Hash codes
    • Hash functions - Insert, remove, find with chaining (and the Big-Ohs)
    • Know the advantages and disadvantages of using Hash Tables vs. self-balancing trees (such as AVL trees)
  • Binary Heaps
    • What data structure do binary heaps implement
    • Definition
    • Insert, remove (and Big-Oh of operations)
    • Implementing Heaps
    • Heap sort — general idea of how it works