New version page

# UCF COP 3503C - COP 3503 Final Exam Review

Pages: 6
Documents in this Course

4 pages

6 pages

6 pages

17 pages

6 pages

7 pages

3 pages

19 pages

34 pages

16 pages

8 pages

51 pages

2 pages

21 pages

5 pages

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