Week #02 | |

Pedro Ribeiro - DCC/FCUP |

**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**if 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 O(n log n).

- I know
**Binary Search and variants:**- I know that
**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**.

- I know that

**Slides made for class**: Sorting, Binary Search and Variants- The problem [UVA 907] - Winterim Backpacking Trip can be directly solved implementing the strategy described in the slides

**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**- 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:**- CodeForces problemas tagged as "Binary Search"
- CodeForces problemas tagged as "Ternary Search"
- SPOJ problemas tagged as binary search
- UHunt: Problem Solving Paradigms > Divide and Conquer
- [SPOJ PIE] - Pie (binary search the answer)

Pedro Ribeiro - DCC/FCUP |
**Último update:**