From charlesreid1

Chapter 13: Searching and Sorting

Sections:

13.1 Searching and sorting in the Java class libraries

13.2 Program complexity

13.3 Implementing searching and sorting algorithms

13.4 Case study: implementing merge sort

Section 13.1: Searching and Sorting in Java Class Libraries

Material

Binary search

Sorting

Shuffling

Custom ordering with comparators

Section 13.2: Program Complexity

Material

Empirical analysis

Complexity classes

Section 13.3: Implementing Searching and Sorting Algorithms

Material

Sequential search

Binary search

Recursive binary search

Searching objects

Selection sort

Section 13.4 Case Study: Implementing Merge-Sort

Material

Splitting and merging arrays

Recursive merge sort

Complete program

Chapter 13 Summary

Deliverables

Chapter 13 Homework

HW Questions

(Recommended) Self-check problems: #1, #2, #9 #10, #11, #15, #18, #22, #24, #28, #30

(Required) Exercises: #1, #2, #3, #4, #5, #6, #12, #16, #20

(Required) Projects: #4

HW Details

Self-check:

  • 1,2 - how search works
  • 9, 10, 11 - code complexity and runtime
  • 15 - number of operations to big-oh notation
  • 18, 22 - binary search
  • 24 - selection sort
  • 28, 30 - following sort algorithms

Exercises:

  • 1, 2, 3 - binary search
  • 4, 5, 6 - complexity class of algorithms
  • 12 - state of array
  • 16 - comparator for String object
  • 20 shuffling algorithm

Projects:

  • 4 - anagrams of all words in an input file, store the legal anagrams (instructions could use some clarification)

Chapter 13 Code

Lecture Code

Worksheet Code

Chapter 13 Goodies

Quotes

Profiles

Puzzle 6

Modular exponentiation, Fermat's Little Theorem, Euler's Theorem, relative prime

Puzzles/Crypto Level 2/Puzzle 6

Flags