CSC 421: Algorithm Design & Analysis
Spring 2017

Midterm Review


Thu, Mar 2
  • The test will include extra points (Mistakes Happen!), e.g., 103 or 104 points, but graded on a scale of 100.

Types of questions
  • factual knowledge: TRUE/FALSE, multiple choice
  • conceptual understanding: short answer, discussion
  • synthesis and application: explain/trace/modify code, analyze an algorithm, ...
  • Sample Midterm Questions
Study advice
  • review online lecture notes
  • review the text book (if not mentioned in class, won't be on test)
  • look over quizzes, homework assignments
  • reference other sources for examples, different perspectives
Course material Java/Data Structures review OO design: cohesion, coupling, interfaces, inheritance, polymorphism data structures: List, Set, Map, Graph, Stack, Queue algorithm efficiency: big-Oh, rate-of-growth, iteration, recursion Brute force approach focus on solving in simplest way - don't worry about extensibility/reuse exhaustive search, generate & test, nP-hard problems examples: invoice handling, string matching, N-queens, knapsack, dictionary Decrease & conquer approach reduce problem to a similar problem of a smaller size top-down (recursive) vs. bottom-up (iterative) implementations decrease by constant: insertion sort, topological sorting decrease by constant factor: binary search, fake coin problem decrease by variable amount: search/insert into BST, quick select Divide & conquer approach reduce problem to multiple subproblems, combine answers Master Theorem examples: merge sort, quick sort, closest pair, large int multiplication, exhaustive tree recursion (e.g., size, contains, toString) Transform & conquer approach transform problem into a more easily solved one examples: presorting, BSTs (AVL, red-black), heaps, Horner's rule problem reduction: lcm --> gcd, graph searches space vs. time additional storage can often allow for a more efficient algorithm examples: ArrayList resize, linked structures, heap sort, hash tables examples: AnagramFinder, BinaryTree string matching: brute force, Horspool, Boyer-Moore Greedy approach solve by making a sequence of choices/actions, select locally optimal examples: minimal change, job scheduling, minimal spanning tree: Prim's algorithm shortest path: modified BFS, Dijkstra's algorithm data compression: Huffman codes