Home/Syllabus

Schedule/Notes

Topics

Review 1

Midterm Exam

The midterm exam is going to be at regular class time on Thur, Oct 17.
At the midterm exam you are NOT permitted to use books, computers, phones, calculators, or help from other people.
You are allowed to bring 1 (one) index card with anything you want written on it (both sides). Write down your name on the index card, and turn it in with your exam sheets.
For a complete list of study material, please refer to all posted notes, lab & homework assignments (including textbook problems & implementations), and the practice midterm.

Check list

For the midterm exam:

• Write simple Java codes; understand fundamental OOP concepts; understand the basic concepts of version control (git & github)
• Work with classes/objects & write functions.
• Understand the concepts: ADT vs data structure, computational problem, algorithms vs programs
• Understand the time complexity of an algorithm (asymptotic analysis): average case, worst case, best case; analyze the time complexity (in big-Theta) given a code fragment or an algorithm. Understand the concepts of big-O, big-Omega, big-Theta; lower bound vs upper bound. Derive a big-O notation from a running time expression (e.g., $T(n) = c_1 n^2 + c_2 n^3$).
• Understand the basic data structures, and the cost of operations (e.g., building, access, search, insert, delete) associated with the basic data structures.
• Lists, queues, and stacks:
  1. The difference between these data structures.
  2. The difference between array-based and linked implementations.
  3. The basic operations for each of these basic data structures and their time complexities.
• Trees
  1. Terminologies (depth, height, node, edge, path, etc); binary trees; full binary trees; complete binary trees.
  2. Tree traversal (inorder, preorder, postorder).
  3. BST: search, insertion, deletion, and time complexity of these operations; applications using BST; is BST balanced or not.
  4. AVL tree & rotation operation & the four different cases
  5. Heap: complete tree; siftup, siftdown & heapify; max-heap vs min-heap; heapsort; priority queue (compareTo)
  6. Huffman tree: full binary tree; the three problems
  7. Disjoint-set (union-find): the parent-only tree implementation
• Hash table, hash function, conflicts, open/closed hashing (probe sequence), hash functions we used (you implemented) for names & DNA sequences, efficiency of hash tables.
• Sorting and searching (in a list, tree, and hash table)
• Algorithms:
  1. Principle paradigms: greedy, divide-and-conquer.
  2. Example algorithms falling in each paradigm (e.g., divide-and-conquer in quicksort & merge sort; huffman tree building)
  3. The different sorting algorithms (quadratic algorithms, and faster divide-and-conquer based approaches).
  4. Time (and space) complexity of the algorithms discussed in this course.