Advanced Math Concepts in Programming

Course Information

• Course name: IT245 Data Structure
• Program: IT Program
• College: College of Computing and Informatics
• University: Saudi Electronic University
• Academic years: 2011-1432

Module 1: Introduction to Data Structures

• Why Data Structure?

  • Example problem: Searching for a number (k) in a set of N numbers.
  • Solution with a basic array: Store numbers, iterate until k is found.
  • Number of checks:
    • Best case: 1
    • Worst case: N
    • Average case: N/2
  • Alternative solution efficiency problem: Sorting a set of N numbers and checking the 'k'th element
  • Problem with basic solutions: They take a considerable amount of time for large datasets (millions).

• The Message: Appropriate data structures improve design and performance.

• The Challenge: Design appropriate structures and associated algorithms to solve a problem & analyze to optimize performance.

Contents

• Why Data Structure?
• Mathematics Review
• Implementing Generic Components Pre-Java 5
• Implementing Generic Components Using Java 5: Generics
• Algorithms as a technology

Weekly Learning Outcomes

• Recall major mathematics concepts
• Review Java primitive data types, classes, objects, and interfaces
• Introduce algorithm design

Required Reading

• Chapter 1: Data structures and algorithm analysis in Java by Mark Allen Weiss
• Chapter 1: Introduction to Algorithms by Thomas H. Cormen

Recommended Reading

• Beyond Basic Arithmetic (link provided)

Mathematics Review

• Exponents: XA^B = X^A+B, X^A/X^B = X^A-B, (X^A)^B = X^AB, X^N + X^N = 2X^N ≠ X^2N, 2^N + 2^N = 2^N+1
• Logarithms: In Computer Science, logarithms are base 2 unless otherwise specified. X^A = B if and only if log_xB = A. Review Page 3, Chapter 1 (Required Book)
• Series: Σ_i=0^N2ⁱ = 2^N+1 - 1, S = 1 + A + A² + A³ + ... = 1/(1-A)
• Recursion:
  • Function defined in terms of itself is recursive
  • f(x) = 0 if x = 0, = 2f(x - 1) +x², otherwise
  • Base cases are handled at start
  • Recursive calls always progress toward a base case
  • Work is not duplicated by recursive calls
• Example: Printing numbers recursively
• Design rules for recursive functions:
  • Base cases
  • Making progress
  • Design rule
  • Compound interest rule

Implementing Generic Components Pre-Java 5

• Generic implementation describes basic functionality.
• Example: Sorting an array of items (logic independent of object type).
• Using Object for Genericity:
  • MemoryCell class using Object
  • Example of TestMemoryCell class demonstrating Object use to store and retrieve generic data in the class.
  • Primitive types cannot be used directly. Only reference types compatible with Object

Implementing Generic Components Using Java 5: Generics

• Generic classes and interfaces
• When a generic class is specified, the class declaration includes one or more type parameters.
• Line 1 example of type parameter specification.
• Generic types allow specifying a type parameter, for example, GenericsMemoryCell<Integer>
• The Diamond Operator (Java 7+): Allows writing GenericMemoryCell<Integer> m = new GenericMemoryCell<>(); for instance in place of GenericMemoryCell<Integer> m = new GenericMemoryCell<Integer>();
• Auto-Boxing/Unboxing between primitives and wrapper objects (important for handling primitives in Collections)
• JDK 5 auto-boxing/unboxing example demonstrated to wrap int to Integer and unwrap Integer to int
• Enhanced for-each loop (JDK 5) example of using for loop with Java collections
• Generic wildcard (?) and bounded type parameters
  • ? extends T: Upper bounded wildcard (accepts type T or subtypes).
  • ? super T: Lower bounded wildcard (accepts type T or supertypes).
  • ?: Unbounded wildcard (accepts all types)

Algorithms as a Technology

• Definition of algorithm
• Characteristics of an algorithm:
  • Well-defined inputs
  • Well-defined outputs
  • Clear and unambiguous
  • Finite-ness
  • Feasible
  • Language independent
• Example problem: Adding three numbers to demonstrate algorithm design and implementation process.
• Algorithm efficiency:
  • Different algorithms can vary considerably in efficiency.
• Algorithms in advanced technologies like web services

Additional Information

• Reference provided for Java Generics and Algorithms.