This website was created for CPS 350 as a review for everything we've learned as of March 25, 2020. Because of the corona virus, this test became open-note so if we put in the work now we can use this on the test!

1. Logical Operators

2. Loops: For each, while, do-while, for-each.

3. Primitive Variables

4. Getting User Input

5. Classes: subclasses and superclasses usage, abstract classes/methods, concrete classes (stuff you can make objects of)

   1. Inheritance, Dynamic Lookup Method, Polymorphism, Overloading/Overriding

6. Objects (String) (Nuke++)

7. Methods:

   1. private, package, public, protected (child can access it, but not public).

   2. Return types: objects, primitives, a class, strings

8. Packages (Our autcomplete has its own package of classes; like java.util... we import it).

9. Interfaces (Mike Chase is terrible with them)

   1. Make Sure to Hyperlink to Comparable/Comparator under Data Structures

10. Variables: Instance, Local Primitives, References, Default Values, Scope

    1. Integer overflow.

11. Memory Allocation: Stacks vs. Heaps, Address Space (1-21-20), Lifetime of Objets)

12. Generic Classes & Components (ie. Type <T>, <Key>), Generic Stacks, Tight Type Checks, Type Safety, Type Casts, Unchecked Cast, Generic Array Implementation, Type Erasure, Autoboxing (Automatic Cast), Wrapper Object Type

13. Post-Fix

14. Exceptions: Dealing with unexpected errors

    1. Catching exceptions

    2. Errors vs. Exceptions

    3. Try/Catch Blocks

    4. throws keyword & Postpone handling.

    5. The finally block

    6. Extending existing exception classes & defining your own.

15. Iterators (from 1-28-20 powerpoint)

    1. The Iterator interface (methods: hasNext(), next()

    2. The Iterable interface

1. ArrayLists

2. LinkedLists

3. TreeMap

4. PriorityQueue

5. Methods: add, contains, etc.

1. Proof by Induction

   1. Show examples

   2. Prove the base case, Something with P(k), prove the induction case

   3. How to prove the running time of recursive functions (like MergeSort 2-18-20)

   4. Formal Proofs

2. Computing Discrete Sums

3. Big Oh Notation

4. Recurrence Relations (How to do proof by induction); see #1.

   1. How to solve for them.

   2. Show examples

   3. Eliminating low-order terms and coefficients

5. Space Complexity

   1. Object References are 8-bytes

   2. Chars are 2 bytes

   3. Ints are 4 bytes

   4. How to calculate space for arrays & addition entries.

   5. Calculating space for obects

   6. What is padding

1. Arrays

   1. Circular Arrays- Start Index and End Index

   2. Array Lists

2. Linked Lists & Nodes

3. Queues (Impelemented via Arrays and Linked Lists)

1. Priority Queues: (As trees)

2. Binary Search Trees- Binary Trees that use a binary sort algorithm

3. Self-Balancing Binary Search Trees

4. Heaps

5. Hash Tables

6. Graphs

7. Disjoint Sets

8. Trees

   1. Complete vs. Incomplete (what that means)

   2. How heaps use complete binary trees

   3. Height

   4. Leafs

   5. Binary min-heap (aka binary heap)

   6. Binary Heap API Public Methods

      1. Requirement: items are generic and comparable

      2. Duplicate keys are allowed.

   7. "Heap property" (Percolate up)

   8. Operations: min (returns root.data), insert, deleteMin, insert

   9. How to insert one more node & the trace.

   10. How to restore the heap property.

   11. Array representation of the binary heap

       1. In a complete binary tree, you can specify parent/children/left and right childs by using multiplication and division. (ie. left child is i*2) "No left child behind."

• Terminology: Abstract Data Types

1. What does In-Place & Stable Mean

2. Insertion Sort

3. Selection Sort:

4. Merge Sort

   1. Divide and Conqueor

   2. Partitioning

   3. Merging

   4. 3-Way Partitioning

   5. Show the recursion somehow

   6. Practical Improvements

      1. Bottom-Up Mergesort

      2. Use insertion sort for small subarrays (<10 items).

5. Quick Sort

   1. Terminology: Pivot, Partition, lows and hi's,

   2. Improvements

      1. Chose the median of the sample.

      2. Three Way Quicksort Dijkstra (Improves efficiency if there are many duplicates).

6. Linear Sort

   1. Has to be a primitive (number or character).

   2. What are keys?

   3. Deals with the frequency

7. Radix Sort (doesn't matter) (specialization of lexiciographic-sort; uses bucket sort) 2-27.

8. Bucket Sort

   1. Key-Indexed counting

9. Heap Sort (Related to priority queues?)

   1. Smaller keys mean higher priority

   2. Operations insert(Key k); Key deleteMin(); boolean isEmpty();

   3. Run time when ordered & unordered for which sort.

10. What does a comparison sort mean?

11. Types of orders: Standard (numbers), Chronological (dates or times), Lexicographic (Strings)

12. The Comparable Interface (Using default, natural ordering)

    1. Bult-In Types: Integer, Double, String, Date

    2. User-Defined Comparable Types: Date data type

    3. Implementing the Comparable Interface

13. The Comparator Interface (Using an alternative ordering)

    1. Implemting an interface

    2. Compare() Methods

14. Arrays.sort

15. Stable & Unstable Sorts: Preserves the Relative Order; talk about each algorithm

16. In-Place: Making more arrrays or not

    1. Auxillary Arrays

    2. Does it use extra space (yes if not stable).

For Each Algorithm, list:

• Best-case

• Worst-case

• Average-case

• Time complexity

• Space Complexity

• Stabe/Instable

• In-place: (A sorting algorithm is in-place if it uses ≤ c log(N) extra memory.

• 
  

1. Linear Search: Run time, implementations

2. Binary Search

3. Binary Search Trees

For the future!