Computer Science 331 — Searching and Sorting

Searching and Sorting

Overview

A huge amount of computing time is devoted to searches in collections of data. As explained in the first lecture in this part of the course, searches are much more efficient than they otherwise be if the “key”, being searched for, is part of a set that has a total order, and if the collection of elements that is being searched through, to find the key, is sorted in non-decreasing order.

A variety of efficient sorting algorithms are, therefore, presented and analyzed.

Lecture #14: Basic Algorithms for Searching and Sorting

Required Reading

• Lecture Notes: [ Source ] [ Video ]
• Supplemental Material: Tail Recursion [ PDF ]

Lecture Presentation

• Lecture Outline (Not Completed)
• Supplement for Lecture Presentation

Tutorial #13: More About Binary Search

• Problems To Be Solved

Lecture #15: Merge Sort

Required Reading

• Lecture Notes: [ PDF ] [ Video ]

Lecture Presentation

• Lecture Outline (Not Completed)
• Supplement for Lecture Presentation

Tutorial #14: Merge Sort

• Problems To Be Solved

Lecture #16: Binary Heaps

Required Reading

• Lecture Notes: [ PDF ] [ Video ]
• Supplemental Material — Properties of Binary Heaps: [ PDF ]

Lecture Presentation

• Lecture Outliine (Not Completed)
• Supplement for Lecture Presentation

Java Code: Unbounded Heaps

• MinHeap.java (Interface for a MinHeap): [ Source ] [ Documentation ]
• MaxHeap.java (Interface for a MaxHeap): [ Source ] [ Documentation ]

Java Code: Bounded Heaps

• BoundedMinHeap.java (Interface for a Bounded MinHeap): [ Source ] [ Documentation ]
• BoundedMaxHeap.java (Interface for a Bounded MaxHeap): [ Source ] [ Documentation ]
• HeapFullException.java (Exception Thrown if Heap is Full): [ Source ] [ Documentation ]

Tutorial #15: Implementing an Unbounded Binary Heap

• Problems To Be Solved

Lecture #17: Applications of Binary Heaps

Required Reading

• Lecture Notes: [ PDF ] [ Video ]

Lecture Presentation

• Lecture Outline (Not Completed)
• Supplement for Lecture Presentation

Tutorial #16: Making Heap Sort a Little Bit More Efficient

• Problems To Be Solved

Lecture #18: Quick Sort

Required Reading

• Lecture Notes: [ PDF ] [ Video ]

Lecture Presentation

• Lecture Outline (Not Completed)
• Supplement for Lecture Presentation

Tutorial #17: Quick Sort

• Problems To Be Solved

Assignment #3: A Fast Algorithm for “Selection”

• Problems To Be Solved
  
  
• JUnit Tests
  
  
  • Test_Select_1.java: Tests for a small ArrayList
  • Test_Select_2.java: Tests for a moderately sized ArrayList
  • Test_Select_3.java: Tests for a moderately sized ArrayList
  • Test_Select_4.java: Tests for a moderately sized ArrayList
  • Test_Select_5.java: Tests for a moderately sized ArrayList
  • Test_Select_6.java: Tests for a moderately sized ArrayList
  • Test_Select_7.java: Tests for a moderately sized ArrayList
  • Test_Select_8.java: Tests for a moderately sized ArrayList
  • Test_Select_9.java: Tests for a moderately sized ArrayList
  • Test_Select_10.java: Tests for a moderately sized ArrayList

cpsc 331 computer science faculty of science u of c

cpsc 331 intro and math review analysis of algorithms basic data structures and adts search trees hash tables searching and sorting graph algorithms java develoment exercises assignments tests