Welcome to idontget.com
 Your Source for Exams, Homework, Quizzes and Notes for all the Stuff You Don't Get!
Skip This Page Next Time
[First Page] [Prev] Page 1 of 27 pages [Next] [Last Page]
Class Date Description

CSC245
Spring 2004
Exam 2 Solutions Page 1
Venn Diagram, Power Set, Cardinality, Cartesian Product, Boolean Algebra

CSC245
Spring 2004
Exam 2 Solutions Page 2
Injective, Bijective, Non-Bijective, Prolog

CSC245
Spring 2004
Exam2 Solutions Page 3
Finiteness, Euclidean Algorithm to Compute GCD, Number Systems: Base 2, Base 10, Base 4, Base 17, Sets: Cardinality, Pairwise Relatively Prime

CSC245
Spring 2004
Exam2 Solutions Page 4
Matrices: Addition, Location, Multiplication, XOR, Transposition

CSC245
Spring 2004
Exam2 Solutions Page 5
Matrices: Boolean product, Integer Notation, Sequences, Arithmetic Rules

CSC245
Spring 2004
Exam3 CoverageNoteSheet
Small review sheet with exam coverage notes

CSC245
Spring 2004
Exam3 SummaryStudyNotes Page 1
Permutations/Combinations, Pascal's Triangle, Binomial Theorem, Generalized Permutations and Combinations

CSC245
Spring 2004
Exam3 SummaryStudyNotes Page 2
Product Rule, Multiplication Principle, Sun Rule, Addition Principle, Exclusion, Inclusion, Permutations, Pigeon Hole Principle

CSC245
Spring 2004
Exam3 SummaryStudyNotes Page 3
Proof by Weak Induction, Structural Induction

CSC245
Spring 2004
Exam3 SummaryStudyNotes Page 4
Example: Proof by Induction (3 by weak, 1 by strong)

CSC245
Spring 2004
Exam3 SummaryStudyNotes Page 5
Principle of Mathematical Induction, Weak vs Strong Induction, Example: Weak Induction

CSC245
Spring 2004
Exam3 SummaryStudyNotes Page 6
Definition of Inductive Hypothesis: Well-ordering property, Recursion, Exclusion Rule, Example: Induction

CSC245
Spring 2004
Exam3 SummaryStudyNotes Page 7
Sum rule, Divide & Conquer f(n)

CSC245
Spring 2004
Exam3 SummaryStudyNotes Page 8
Example: Permutation/Combination, Example: Recursive Relations (Type 1)

CSC245
Spring 2004
Quiz10 - Week 12
Fill in the blank proof by weak induction

CSC245
Spring 2004
Quiz11 - Week 13
Using the Sum and Product Rule, Using the pigeon hole principle

CSC345
Fall 2005
Exam 1 Study Guide Cover Page
This study guide covers CSC345 from the beginning of the class to the first exam

CSC345
Fall 2005
Exam 1 Study Guide Page 1
- Java 1.5 changes
- for each/for loop
- scanner class
- printf
- generics
Storing an array in memory
- 1-D array (continuous allocation)
- 2-D array
- Big-Oh of searching different types of datastructures, Big-Oh search for linked list, Big-Oh search for array, Big-Oh search for sorted array
- Row major order
- Column major order
- Indexing calculations for arrays

CSC345
Fall 2005
Exam 1 Study Guide Page 2
Linked lists
- how many pointer changes does a linked list undergo when adding a new node?
- Concept of multilist
- Insertion methods
- Orthogonal list
- Sparse matrix
- Recursion with linked lists to unlink all nodes
- Base case
- General case

CSC345
Fall 2005
Exam1 Study Guide Page 3
- Instance characteristic: Measure of the size of a problem
Examples:
- Searching a linked list
- Scalar matrix multiplication

- Step-Counting to determine big-oh
- Big-Oh (1892): let f(n) and g(n) be functions that map positive integers to positive real numbers. We say that f(n) is O(g(n)) or f(n) <- O(g(n)) if there exists a real constant c > 0 ...

Proof by weak induction
f(n) = 7n + 8
g(n) = n
c*g(n) = 8n
c = 8
Use n=1
7(1)+8 = 15 ...
Choose n0.

Proof (by weak induction):7n+8 <= 8n for all n >= 8 ... QED

CSC345
Fall 2005
Exam 1 Study Guide Page 4
Big-Oh performance for array indexing, binary search, min/max, quicksort, mergesort, bubblesort, matrix multiplication.

Big Oh definition
Little Oh definition
Big Omega definition
Little omega definition
Big theta definition
O()
o()
w()
Omega()

Properties
Symmetry:
Transpse Symmetry:
Transitivity:
Transpose Symmetry Example:

CSC345
Fall 2005
Exam 1 Study Guide Page 5
Recurrence Relations
The five (5) Steps to solving recurrence relations
Example 1:
T(0)=c
T(n)=K+T(n-1)

Example 2:
T(1)=c
T(n)=T(n/2)+T(n/2)+K

CSC345
Fall 2005
Exam 1 Study Guide Page 6
Quicksort (Divide and Conquer)
Procedure to use Quicksort (3 steps)
Step 1) Pick an element called the pivot.
Step 2)
Step 3)
Worst case Big-Oh
Average case Big-Oh

Shell Sort (non-recursive)
Worst Case:
Average Case:

Bubble Sort - 4 step process explained
Step 1) Compare adjacent elements, if the first is greater than the second, swap them.
Step 2)
Step 3)
Step 4)
Best Big-Oh for key comparisons and data movements
Worst Big-Oh for key comparisons and data movements
Average Big-Oh for key comparisons and data movements

Insertion sort
Step 1) Insert values to the right of the first key into a list created by the first element, shift elements until...
Best, Worst, Average Big-Oh for key comparisons and data movements

CSC345
Fall 2005
Exam 2 Solutions Page 1
Cover Page
Grade: 67/80

CSC345
Fall 2005
Exam 2 Solutions Page 2
Problem 1:
Consider the sequence of seven two-letter words: ...
(a) Insert the sequence of words into a binary search tree, show the final tree
(b) Insert the same sequence into an AVL tree. Show the tree after the completion of each rotation and show the final tree.

CSC345
Fall 2005
Exam 2 Solutions Page 3
Problem 2:
Delete the word ... from this binary search tree (BST) and draw the resulting tree next to it.
Problem 3:
Short-Answer questions..
(a) Before Interpolation Search can be effectively used, which three conditions about the data need to exist?
(b) Using the 2-3 tree, 2-3-4 tree, etc.., search tree naming convention, what is the appropiate name for...
(c) Is a binary tree of four nodes, with each node holding,..., that satisfies the structure property, properly called a min heap, a max heap, both or neither? Why?

CSC345
Fall 2005
Exam 2 Solutions Page 4
Problem 4:
(a) Can this tree be considered to be a splay tree? Explain.
(b) No matter how you answered part (a), splay ... to the root of the tree. After each splay operation has been performed, show the subtree rooted at ...

CSC345
Fall 2005
Exam 2 Solutions Page 5
Problem 5:
Hashing
(a) What is the goal of hashing?
(b) Explain the difference between Quadratic Probing and Double Hashing.
(c) Consider the sequence of integers ..... Hash these values, in the order shown, into the hash table given below using as your hash function h(n) = n... Use linear probing for collision resolution.
(d) Consider the hash function h(n) = 2(...) and a table with 22 slots (numbered 0 through 21). Name one advantage of this hash function/hash table combination when collision are handled with linear probing. If you feel that there is no advantage, explain why. Repeat the same question but consider chaining instead of linear probing.

CSC345
Fall 2005
Exam 2 Solutions Page 6
Problem 6: Optimal Binary Search Tree
(a) How does the goal of optimal BSTs differ from the goal of splay trees?
(b) Consider the tree given below and these probabilities. To which portion of the tree does AST(5,6) refer? Wat is the AST of just the subtree rooted at k2(be)?

CSC345
Fall 2005
Exam 2 Solutions Page 7
Problem 7:
In our code for Binary Search Tree, we sometimes used a sentinel node to "anchor" the tree. In those versions of the code, BinaryNode objects insert() methods didnt create any nodes at all, but the SentinelNode objects insert() methods did. Why do SentinalNodes create new nodes?

Problem 8:
Consider Improbed External Merge Sort (IEMS) with four three-record buffers, and 3-way External Merge Sort (3wEMS) with four files. Which of these will perform better? Explain your answers.

Problem 9: Consider a complete (2-level) AVL tree of 3 nodes.
(a) What is the minimum number of insertions needed to force an AVL Single rotation? Explain your answer using a small diagram.
(b) What is the minimum number of insertions needed to force an AVL Double rotation? Explain using a small diagram.
(c) What is the maximum number of insertions that can be made before any variety of rotation will be necessary? Explain using a small diagram.

CSC345
Fall 2005
Exam 2 Study Guide Cover Page

CSC345
Fall 2005
Exam 2 Study Guide - Table of Contents
Optimal BSTs (Binary Search Trees)
Improve External Mergesort
AVL Trees
Splay Trees
Hashing
External Mergesort (2-way/3-way)
Heaps
Heapsort

Binay Search Tree Deletion
1) No child
2) Node has one child
3) Two children

Quadratic Probing formula
Double Hashing formula

CSC345
Fall 2005
Exam 2 Study Guide Page 1
Sort Stability
How to stable sort a phonebook
Step 1) Sort on...
Step 2) Sort on...

Bubblesort:
Quicksort:
Mergesort:

Best, Worst, Average Big-Oh

Picture of Buffered Reading using a disk

Improved External Mergesort
Pass 0) Fill up...
Pass 1-n) n-1 buffers for...
Efficiency:
Pass 0) Number runs created...
Total...

Polyphase Mergesort
-Reduces the number of intermediate files needed by ...
- Ideal for merging files that are too ...

CSC345
Fall 2005
Exam 2 Study Guide Page 2
Searching

Sequential Search/Linear Search
Average Big-Oh

Binary Search
Average Big-Oh
Worst Big-Oh
Search a sorted array by dividing the search interval in half
Example shown.

Interpolation Search also known as the Phonebook Search
Use when
1) Sorted list
2) Dire...
3) Uniform ...
4) Huge ...
Begin searching at Lo + ...
Efficiency of Interpolation Search: Worst, Average, Best

CSC345
Fall 2005
Exam2 Study Guide Page 3
Improved External Merge Sort
Good for:
1) Large ...
2) Limited ...
Pass 0) Ceiling( Record... )

CSC345
Fall 2005
Exam 2 Study Guide Page 4
Hashing

Main goal of hasing = O(1) = Big-Oh(1)

Hash table shown size = 7.
- m is not good for poswers of 2 (m should always be ...)

m is usually ___ because ...
Alternative to ... is ....
- Use bit masking to achive modulus operation
- Significantly ...

Arrange generic hash value using ...
Clustering - hash function causes keys to fall ...

Linear probing:
Quadratic probing:
Double hashing:

Chaining
- Simple to ...
- Insensitive to ...
- Degrade ...
- If the hash table is ...
- Slightly more ...
- Used in cases where ...

CSC345
Fall 2005
Exam 2 Study Guide Page 5

Hashing Strategies: Open-Addressing, Perfect Hashing, Universal Hashing

CSC345
Fall 2005
Exam2 Study Guide Page 06

CSC345
Fall 2005
Exam2 Study Guide Page 07

CSC345
Fall 2005
Exam2 Study Guide Page 08
[First Page] [Prev] Page 1 of 27 pages [Next] [Last Page]