2023 Fall 2013 CSC 230 Final Exam Study Guide Final Exam Monday December 9th 2013 6 PM to | Assignment Collections

Fall 2013 CSC 230 :: Final Exam Study Guide Final Exam: Monday, December 9th, 2013. 6 PM to 8 PM Do not be late! (I will be there from 5:45 to 8:15) Exam will be comprehensive so you MUST study earlier material again (in particular review previous study guides). However, the exam will focus most heavily on material covered since Test 2. Not sure right now the exact percentage split, but assume 60-70% of questions will be on reading and materials covered since Test 2. This handout documents only that material! As always, if I wrote it on the board you are likely to see it again. Review resources Handouts / class notes: binary files, direct access C++ code. Assigned Readings since Test 2: hashing techniques, heaps and binary files, graphs Programming assignments Terminology, discussion points, advantages/disadvantages, average/best/worst cases, and practical applications. Terms to be defined or explain/discuss/give examples of: Greedy algorithm (like Kruskal’s or Prim’s for finding Minimum Spanning Tree or Stable Marriage Algorithm), divide and conquer algorithms (like quick sort and merge sort that use recursion), text files versus binary files (pros and cons of each), sequential access, direct (random) access, hash table packing factor, hash function, collisions, mid-square hashing function, hashing function based on folding, secondary hashing, priority queue (and operations on it), complete tree, heap, heap operations [be able to pseudo code add/remove an item to/from a max/min heap], possible implementations of a priority queue, possible implementations of a heap (one via an array based tree technique with children/parent addresses computable), collision resolution mechanisms [linear probing, quadratic probing], tombstones, chaining with separate lists, complexity classes associated with various search/add/delete operations on a wide variety of data structures, b-trees in particular: contents? How to add/remove an item for a b-tree?, graphs, vertices…