Review 2
Final exam: 8:00-10:00AM, Tues., Dec 17th
General rules for the exam: at the final exam you are not allowed to use books, computers, phones, calculators, or help from other people.You are allowed to bring 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.
Style of the exam: the final exam will be similar to the midterm exam in terms of style; there will be many questions with relatively short answers.
You will be asked to use data structures and algorithms, explain techniques that have been used in class, requested in the written homework, and used in implementing the programming homework.
Most answers will be relatively short, so prepare to write many short, clear answers. One common mistake on such exams is to write very long answers, where this is really not asked for, and to run out of time. Clarity will serve better than length, so practice giving concise solutions to problems on data structures and algorithms, as seen in the course material.
The final exam topics include both:
- anything covered in lecture, in-class practice, homework, and labs after the midterm
- important topics that have been pertinent through the course, including algorithm analyse, BST, and hashing.
Check list
- Java and Object Oriented Programming
-
Time Complexity
- analzye the time complexity of an algorithm
- understand the time complexity of important algorithms that we have discussed
-
Search problem & algorithms
- search problem for unsorted lists
- search problem for sorted lists
-
Hashing
- hash tables: advantages, disadvantages, common uses
- hash functions
- hash collision and collision resolution
- Binary Search Trees (BST), revisited
- AVL trees (balanced BST), understand the rotation operations
- disjoint set as a tree (parent-pointer only implementation)
- K-D trees (multi-dimensional keys; range search)
- tries ; suffix trees (for string matching) + suffix array
- 2-3 trees, B-trees, B+-trees (just the basic concepts)
-
graph terminology:
sparse, dense, acyclic, undirected, directed, labeled, weighted, subgraph, DAG, cycle, path, length, vertex, edge, reachable, adjacent, etc.
- graph representations: adjacency list, adjacency matrix, edge list
- graph traversals: Depth-First Search (DFS), Breadth-First Search (BFS)
- connected components (and applications, e.g., to answer if two people are connected or not in a SN; and solve the library and road problem)
- topological sorting
- shortest path problems/algorithms: single-source shortest paths (BFS, Dijkstra's algorithm); all-pairs shortest paths (Floyd's algorithm)
- Minimum-Cost Spanning Tree (MST); Prim's (how it is different from Dijkstra's) & Kruskal's algorithms (how to check if adding an edge creates a cycle)
- Dynamic Programming (DP) algorithms (knapsack problem; edit distance; LCS; Floyd's)
- Greedy algorithms (activity selection; Kruskal's)
- Divide and conquer