Transcript Introduction to HKOI

Introduction to HKOI
Self Introduction
Ice Breaking Game
Ice Breaking Game





Level 1
Form a big circle
The person holding the deck of cards will start the
game, by introducing himself, and then passes the deck
of cards to his left.
In each preceding turn, the person holding the deck of
cards will repeat what the previous person has said, and
then introduces himself. After that, he will passes the
deck to his left.
The game ends when the deck of cards return to the
first person.
Ice Breaking Game





Level 2
Form a big circle
The person holding the deck of cards will start the game, by
introducing himself and drawing a card from the deck. After that,
he will pass the deck of cards to the kth person on his left, where
k is the number written on the card he draw.
In each preceding turn, the person holding the deck of cards will
repeat what the previous person has said, and then introduces
himself. After that, he will draw a card from the deck and pass
the deck of cards to the kth person on his left, where k is the
number written on the card he draw.
The game ends when the deck runs out of cards.
Problems


Just like in Final Events
Usually starts with a story or a situation in daily life.


Specifies a set of well-defined inputs, and the
corresponding outputs




e.g. A group of people is playing an ice-breaking game
What can be the input and output of the ice-breaking game
we played?
Sometimes, there may be more than one correct output, and
the problem only requires you to output any one of the them.
Be careful of the format of the input and output!
Example: sorting
Algorithms



“Informally, an algorithm is any well-defined computational
procedure that takes some value, or set of values, as input and
produces some value, or set of values, as output. An algorithm is
thus a sequence of computational steps that transform the input
into the output.” [CLRS]
An algorithm (算法) is a method to solve a problem.
There may be more than one algorithms corresponding to a
problem.




Take sorting as an example. Bubble sort and insertion sort are algorithms
that solves the problem.
We usually regard algorithms as language independent.
An algorithm, by definition, must eventually terminates.
Many important algorithms are named after Computer Scientists.
Algorithms

Tree-Search algorithms



Graph algorithms






Depth-First Search
Breath-First Search
Dijkstra’s
Floyd-Warshall
Bellman-Ford
Prim’s
Kruskal’s
Convex Hull algorithm

Graham’s scan
NT
Q
WA
SA
NSW
V
T
Data Structures



Data structures (數據結構) are how we organize and store the
input data, or intermediate results of computation
Helps to speed up algorithms
Different data structures have different properties



different types of data
different types of operations
Examples





Array
Stack
Queue
Heap
Binary Search Tree
Complexity


We want to know how well an algorithm “scales” (i.e.
when there is a large input).
Usually, minor improvements are not critical in
competitions.



A reasonable implementation can pass.
So, we want to hide the lower order terms.
We do not know the exact time each operation takes.

So, we want to measure the time by counting the number of
basic operations.
Complexity
3000
2400
1800
1200
600
0
0
5
f(n)=10n
10
f(n)=30n
15
f(n)=30n log n
20
f(n)=n^2
f(n)=n^3
f(n)=2^n
45
40
35
30
25
f(n)=3^n
f(n)=n!
Complexity


Big-O notation
Definition
We say that
f(x) is in O(g(x))
if and only if
there exist numbers x0 and M such that
|f(x)| ≤ M |g(x)| for x > x0
Complexity






Bubble sort
For i := 1 to n do
For j := 2 to i do
if a[j] > a[j-1] then swap(a[j], a[j-1]);
Worst case number of swaps = n(n-1)/2
Time Complexity = O(n2)
Total space needed = size of array + space of variables
Space Complexity = 32*n +32*3 = O(n) +O(1) = O(n)
Complexity


Binary search
While a<=b do
m=(a+b)/2
If a[m]=key, Then return m
If a[m]<key, Then a=m+1
If a[m]>key, Then b=m-1




Worst case number of iterations = lg n
Time Complexity = O(log n)
Total space needed = size of array + space of variables
Space Complexity = O(n)
Complexity

Usually, the time complexity of the algorithm gives us a rough estimation of
the actual run time.







O(n) for n ~ 108-109
O(n log n) for n ~ 5x105
O(n2) for n ~ 1000-10000
O(n3) for n ~ 100~1000
O(n4) for n ~ 50-100
O(kn) (k>1) or O(n!) for very small n, usually < 20
Keep in mind




The constant hidden by Big-O notation (including the algorithm and the details
implementation)
Computers vary in speeds, so the time needed will be different. In fact, computers
are getting faster these days.
Read the instructions carefully for the time limit.
Test the program/computer before making assumptions!
Training Session

Topics are divided into two categories, such that
students may master the necessary skills after two years
of training




Intermediate: designed for students who have never entered
training team in the past
Advanced: designed for students who are familiar with
intermediate topics
All topics are open to all trainees.
We strongly recommend that students make sure they
have the necessary background knowledge before they
attend a training session.
Training Session


On Saturdays (including some public holidays)
Venue


AM Session





Questions and discussions
Making friends
PM Session


regular training topics
10:00am – 1:00pm
Lunch


HW312(Intermediate) and HW311(Advanced), Haking Wong Building, The
University of Hong Kong
2:00pm – 5:00pm
Detailed schedule is available in the official website (http://www.hkoi.org/)
Training notes will be uploaded after each training session.
Training Topics


Algorithms and Data Structures
Linux
Free, popular and powerful
 Competition environment


C++

Advantage of Stardard Template Library (STL)
Training References

Books

“Introduction to Algorithms” by Cormen,
Leiserson, Rivest, Stein [CLRS]


Heapsort, Quicksort, Sorting in Linear Time,
Elementary Data Structures, Binary Search Trees,
Dynamic Programming, Greedy Algorithms, Data
Structures for Disjoint Sets, Elementary Graph
Algorithms, Minimum Spanning Trees, Single-Source
Shortest Path, All-Pairs Shortest Path
Online

Wikipedia (http://en.wikipedia.org/)
Online Judge






HKOI Judge (HKOJ)
https://judge.hkoi.org
After each training, some problems are open
for practice.
Update your personal information.
Take attendance on your own every training.
Rank, score and attendance are for reference
only.
Team Formation Test



29 May 2010
Trainees with outstanding performance can
represent Hong Kong in international and
national competitions
The delegation selection algorithm is based on
the score of the Team Formation Test (TFT)
External Competitions

International Olympiad of Informatics (IOI)



http://www.ioi2010.org/
14-21 August 2010 @ Canada
National Olympiad of Informatics (NOI)

全國信息學奧林匹克競賽