Week #03
	Pedro Ribeiro - DCC/FCUP

Main learning outcomes for this class

1. Sorting:
   • I know how to sort using the libraries of my language (wether they are numbers or more complicated structures) and I know the complexity of those sorting algorithms.
   • I know some non comparative sorting algorithms such as counting sort and radix sort that allow one to sort in time better than \(\mathcal{O}(n \log n)\).
2. Binary Search and variants:
   • I know what binary search is and its complexity.
   • I know how to call binary search using the libraries of my language.
   • I know how to manually implement binary search.
   • I understand the concept of binary search the answer.
   • I understand the concept of bisection.
   • I understand the concept of ternary search.

Study Material

• Slides made for class : Sorting, Binary Search and Variants
• Sorting: Example code:
  • sort.c | sort.cpp | sort_vector.cpp | Sort.java
  • customsort.c | customsort.cpp | customsort_lambda.cpp | CustomSort.java | Example input: persons.txt
• Sorting, Binary Search and Variants
  • Library binary search on C, C++ and Java
  • Lower bounds on C++ (also available on tree-based data structures such as set) or Java [you also have... upper_bound]
  • Chapter 3 of Competitive Programmer's Handbook book
  • Section 3.3.1 of the Competitive Programming book
  • Wikipedia article about ternary search
  • Binary Search @ PEG Wiki
  • Ternary Search @ PEG Wiki
  • Binary Search @ Top Coder Tutorials

(more) Problems to Submit

Besides the evaluation problems, here are some more suggestions:

• [CodeForces 818F] - Level Generation (consider this one a "mini"-challenge)
• [CSES 1085] - Array Division can be directly solved implementing the strategy described in the slides
• CodeForces problemas tagged as "Binary Search"
• CodeForces problemas tagged as "Ternary Search"

I want my memes!

Pedro Ribeiro - DCC/FCUP | Last update: