CSC 143/Chapter 13

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 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 Goodies

Puzzle 6

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

Puzzles/Crypto Level 2/Puzzle 6