New version page

UCF COP 3503C - COP 3503 Final Exam Review

Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

Final Exam InformationDate: 8/5/2010Time: 4PM – 6PMRoom: HEC – 103The questions will vary from short answer, to tracing, toperhaps a bit of coding.Since there's a lot to remember algorithm wise, I'll allow you touse three 8.5"x11" pages of notes, front and back.There will be a "bias" towards questions on topics I haven'tasked about before, however, I will most likely ask questionsAGAIN about some of the concepts I find more important.Final Exam Review OutlineI. Order notation a. definition of O b. definition of  c. definition of , in terms of first two d. function growth chart e. how to ascertain experimental order f. Determining run-time of code segmentsII. Algorithms a. Sorted List Match b. MCSS i. O(n3) algorithm ii. O(n2) algorithm iii. O(n) algorithmIII. Mathematical Preliminaries a. Summations i. Arithmetic Series ii. Geometric Series iii. Combination sums b. Counting i. Combinations ii. Permutations b. Probability i. Sample Space ii. Discrete Random Variable ii. ExpectationIV. Logs a. Number of bits in the binary representation of a value n b. Depth of a complete binary tree c. Steps needed in a binary searchV. Data Structuresa. Disjoint Sets b. AVL Trees i. Restructure Operation ii. Insertion (max 1 restructure) iii. Deletion (multiple restructures possible) c. 2-4 Trees i. Node overflow ii. Fusion operation iii. Insertion iv. Deletion d. Hash Tables i. Hash Function ii. Linear Probing iii. Quadratic Probing iv. Dynamic Table Expansion v. Separate Chaining Hashing e. Binary Heap i. BubbleUp ii. BubbleDown iii. Insert iv. deleteMin v. fixHeap vi. Implementing Priority Queue vii. Heap SortVI. Sorting a. Quick Sort Analysis b. Lower Bound for comparison sorting c. Bucket Sort d. Radix Sort e. Counting SortVII. Graphs a. Definition & Different Types b. Two-Color Problem c. Depth First Search d. Breadth First Search e. Topological SortVIII. Greedy Algorithms a. Fractional Knapsackb. Single Room Schedulingc. Multiple Room Schedulingd. Changee. Kruskal'sf. Prim's g. Dijkstra's h. Huffman Coding i. Containers ProblemIX. Divide and Conquer a. Integer Multiplicationb. Skyline Problem c. Integer "Tiling" d. Subset sum e. Change ProblemX. Dynamic Programming a. Change Problem b. Floyd-Warshall's Algorithm and path reconstruction c. Longest Common Subsequence d. Edit Distance d. 0-1 Knapsack Problem e. Matrix Chain Multiplication f. World Series Problem g. Lotto h. MemoizationXI. Backtracking a. Eight Queens b. Magic Square c. SudokuXII. Network Flow a. Problem Definition b. Back Edges c. Minimum Cut d. Use of BFS e. Bipartite Matching f. Matching Girls to Guys g. Matching students to universities h. Filling an orchestra,

View Full Document
Download COP 3503 Final Exam Review
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...

Join to view COP 3503 Final Exam Review and access 3M+ class-specific study document.

We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view COP 3503 Final Exam Review 2 2 and access 3M+ class-specific study document.


By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?