Book reading: competitive programming

Sept. 2, 2016

Plan to spend 30 minutes a time, up to 10 hours to read a short book - 152 pages first.

Competitive programming course:

Free download - version 1


Julia spent more than 1 hour to look into lead board of HackerRank, and then, she found the book to read:

https://algo.is/
competitive programming course

https://sites.google.com/site/stevenhalim/

Free download - version 1

Competition course


Julia is looking for a book talking about suffix array etc. advanced data structure. She found one today.

Write down some great ideas after reading. 

1. 10 terms Julia's favorite from the book:
1. Simple array that is pre-preprocessed with Dynamic Programming - Data Structure term (page 7)
2. Page 11, a form of Hash Table - ‘Direct Addressing Table’ (DAT) 

2. Page 8 Question:
2. Given a list of integers L of size up to 1M items, determine whether a value v exists in L?

(More details in Section 2.2.1).

Page 16 - Balanced Binary Search Tree (BST): C++ STL <map>/<set> 
Java TreeMap/TreeSet 
argument: implement a bug-free balanced BST like AVL Tree or Red-Black (RB) Tree is tedious and hard to do under time constrained contest environment. 

3. Look into those typical problems, first, remember the terms - Page 17 - Page 18 
Spend 30 minutes for each problem - warmup, and get traditional problems into daily routine - talk, warmup, and study some implementation using C# as well. (9/11/2016 - 1:21pm)

Programming exercises to practice using basic data structures and algorithms (with libraries):
• Static array, C++ STL <vector>, <bitset>, Direct Addressing Table
1. UVa 482 - Permutation Arrays (simple array manipulation)
2. UVa 594 - One Two Three Little Endian (manipulate bit string easily with <bitset>)
3. UVa 11340 - Newspaper (Direct Addressing Table)

• C++ STL <algorithm>
1. UVa 146 - ID Codes (use next permutation)
2. UVa 10194 - Football a.k.a. Soccer (multi-fields sorting, use sort)
3. UVa 10258 - Contest Scoreboard (multi-fields sorting, use sort)

• Sorting-related problems
1. UVa 299 - Train Swapping (inversion index3 problem solvable with bubble sort)
2. UVa 612 - DNA Sorting (inversion index + stable sort)
3. UVa 10810 - Ultra Quicksort (inversion index - requires O(n log n) merge sort)
4. UVa 11462 - Age Sort (counting sort problem, see [4])
5. UVa 11495 - Bubbles and Buckets (inversion index - requires O(n log n) merge sort)

• C++ STL <stack>
1. UVa 127 - “Accordian” Patience (shuffling <stack>)
2. UVa 514 - Rails (use <stack> to simulate the process)
3. UVa 673 - Parentheses Balance (classical problem)
4. UVa 727 - Equation (Infix to Postfix conversion)

• C++ STL <queue>
1. UVa 336 - A Node Too Far (<queue> used inside BFS, Section 4.3)
2. UVa 10901 - Ferry Loading III (simulation with <queue>)
3. UVa 11034 - Ferry Loading IV (simulation with <queue>)

• C++ STL <map>/<set>
1. UVa 10226 - Hardwood Species (use <map>)
2. UVa 11239 - Open Source (use <map> and <set> to check previous strings efficiently)
3. UVa 11308 - Bankrupt Baker (use <map> and <set> to help managing the data)
4. UVa 11136 - Hoax or what (use multiset in <set>)

• C++ STL priority queue in <queue>
1. UVa 908 - Re-connecting Computer Sites (priority queue in Kruskal’s, Section 4.4)
2. UVa 11492 - Babel (priority queue in Dijkstra’s, Section 4.5)
3. LA 3135 - Argus (Beijing04)

Find a website about Ultra quicksort:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1751


Nov. 24, 2016
C# book reading: