Informatics Recruitment! (1 Viewer)

[GoldyOrNugget]

Having just completed my HSC, I will now step into my role on BOS as the unofficial informatics representative starting with some outreach/information.

Most of you would know of the AMC. That's the absurdly hard pen-and-paper competition run annually by the Australian Mathematics Trust. Some of you would be aware that the AMC is merely the first funnel/filter in a series of increasingly more difficult competitions that culminate in the selection of 6 Australian school students to represent Australia at the International Mathematics Olympiad.

In parallel, the AMT also runs the informatics program -- specifically, the Australian Informatics Competition and Olympiad. Because the skills required in informatics are not taught in high school, I have the impression that many students sit the AIC, go "huh, those were some interesting logic problems" and never even find out what informatics really is. This is rather unfortunate.

Informatics, in the olympiad/competition context, is the study of algorithms, where an algorithm is a fancy name for a procedure or sequence of steps. Whereas a mathematics question asks "solve this problem", an informatics question asks "find a method that solves the general case of this problem". There is a significant overlap between informatics and discrete mathematics. Here's a few examples demonstrating the difference between the typical problems of an informatics and mathematics competition:

Maths: determine if the number 9933 is prime.
Informatics: produce a sequence of steps to determine if a given number is prime

Maths: find the minimum value of the function f(x) = (x-1)² + 3
Informatics: determine a method whereby, given an arbitrary convex function, one can find its minimum value

In informatics, one writes computer programs to implement these procedures, but I stress that informatics is about the mathematical reasoning behind problems, not about writing code. It provides a twist to the standard maths olympiad combo of combinatorics, geometry, number theory and algebra. Here are some of the areas touched on in informatics:

- Graph theory: simply put, the study of connections/relationships between things. A map can be a graph where intersections are 'things' and the roads between them are connections. A social network is a graph where people are 'things' and friendships are connections. A game of chess can be represented as a (very big) graph where each state of the board is a 'thing' and connections exist to all subsequent possible board states. Standard problems you might face are: given a description of a social network, determine if two people are friends; given a map of Sydney, find the shortest path between any two given locations; now using that map, where each road has a width, determine the minimum number of barricades that must be used to prevent all access to the Opera House from Mascot Station.

- Computational geometry: how does one determine whether a point lies on a line? How do you determine if two line segments intersect? How does one determine whether a point lies in a polygon? If there's a polygon between you and me, how do I know if I can see you? Here's a tough comp. geom. I tackled the other day.

- Combinatorics & dynamic programming: informatics combinatorics involves counting stuff, but it's rarely possible to just use a formula. If I have a bag which fits 100kg of items, and I have a bunch of items in front of me, each with a value and each with a weight, how can I maximise the amount of value in my backpack without exceeding 100kg? Dynamic programming refers to a mathematical technique whereby a problem is expressed in terms of smaller versions of itself (a recurrence) -- in informatics, one must derive these (often very challenging) recurrences and implement them.

- Data structures: say I tell you to find the first occurrence of the word 'helicopter' in a novel. That would take you ages! You'd have to essentially scan through every page. But if I tell you to look up 'helicopter' in a dictionary, you'd be able to do it almost instantly. Why is this? Can we quantify the relative amount of time it takes you to look up each of these things? Now what if I tell you to look up 1000 different words? Can we structure our data in a way that allows you to look words up even faster than a dictionary? What if I'm now dynamically adding and removing words from that dictionary in real time? What benefits are bestowed if we consider non-linear data structures? Google is so successful in part because its data structures are so damn clever.

Of course, the greatest problems are the ones that don't fit into any of these categories neatly -- when you need to apply combinatorics to a computational geometry problem, or when you work out a particularly clever data structure that allows you to optimise a tough dynamic programming problem (both of these examples came up in this recent selection exams for the Australian informatics team). And then, there are those problems where you just go 'wtf?' and you just explore and play around until you make an observation that lets you score full marks

So, who am I? I've sat the AIC and AIO the past 5 years, winning bronze, silver, and 3 gold medals in the latter, participated in UNSW ProgComp (essentially UNSW's annual informatics contest) the past 4 years, and did Sydney Uni's national computer science school challenge in 2009-2011. I was on the Australian informatics team this year and won a bronze medal at the IOI in Italy. Currently, I'm in an odd state of flux between student and tutor in the programme, which means I'm perfectly positioned to provide information and guidance! If you're in years 8-11, you're at the perfect age to get involved in the program.

For more information, talk to your maths teacher, reply here, PM me, or email me at dan(dot)goldbach(at)gmail.com.

 

[Gigacube]

Whilst we're on the topic of Informatics, if you're interested in learning more of the programming side of things, apply for the NCSS Summer School. Applications close Friday 23rd November, 2012.

It's a whole 10 days of fun and you'll meet great people who have also participated in the AIC and AIO. There's a few of us on the forums who have been so feel free to ask questions as well.

 

[SpiralFlex]

This is an excellent post by Daniel. Informatics is such an underrated subject here in Australia.

Edit: I wish I did NCSS.

You should consider tutoring Informatics or becoming a mentor.

 

[GoldyOrNugget]

Gigacube what year did you go? I went at the beginning of this year, it was pretty fun. Too many people though, they should be more selective.

[HR][/HR]

For those who are interested, here's a rundown of the high school programming/informatics scene.

- The AIC is a 1 hour 15 question pen and paper competition held in May. Because of this format, speed and accuracy are prioritised over perseverance and creativity, so many people who do well in AIC are not capable of doing well in the AIO and vice versa. Your results from the AIC should be taken with a grain of salt, and do not otherwise matter.

- The AIO is a 3 hour 3 question programming contest held in September. About 25 strong performers are invited to the 10-day December Training School, which is much like the NCSS summer school but more intense and smarter people . Remember that very few Australian students are any good at informatics, so pretty much if you're competent at all, you can earn yourself an invitation. From here, there are a bunch of invitation-only competitions which become gradually harder.

- UNSW ProgComp is a 2 hour 5 question team programming contest held in June/July. Teams are comprised of 3 members with 1 computer between them. Questions are typically easier than the AIO, and speed is more important. The top scores are traditionally dominated by informatics people. If you come in the top 8 teams, you get flown to UNSW in September for the grand final. Several thousand dollars worth of prize money and UNSW scholarships are up for grabs.

- The NCSS challenge is a 5 week national contest (I use that term loosely here, because the aim is to learn and have fun) held by Sydney Uni. 5-6 programming questions are given per week, and you can enter in 3 difficulty divisions. The junior division is intended for people who've never programmed before. The advanced division gets crazy hard in the final weeks and often exceeds AIO difficulty. If you put in a solid attempt (you don't have to do particularly well), you get an invitation to the 10-day NCSS summer school held in January. About 70 people attend that. The summer school is more geared towards project work and learning to program rather than problem solving, but they usually run an advanced lecture stream with 2nd year computational linguistics content which is very challenging.

- UNSW offers its first year higher computing course (COMP1917) for a few high school students a year. It counts as credit to your degree. This is a great opportunity to meet people with similar interests and learn some cool stuff. It's highly selective, but if you do informatics, you're pretty much guaranteed entry. See: http://www.computing.unsw.edu.au/school-programs/high-school-computing/

[HR][/HR]

Now for people who want to get started right now, the Australian informatics training site is here: http://orac.amt.edu.au/jaz/. I suggest you bookmark that URL after you sign up. It's not an easy site to navigate, but you want to start on the Starter Problem sets. 'Walkthroughs' for the starter problems can be found here: http://orac.amt.edu.au/tiki/. If you get stuck, need help or just want to speak to other people, the community has a permanent informal IRC chatroom on FreeNode called '#aioc'. You can access this at http://webchat.freenode.net by choosing a nickname and typing in the channel #aioc. You can also always email or PM me, I'm bored and will probably help you out.

Since registration on the training site can take a while, here's a simple problem to get you going. 'Bugs', from AIO 2004 (back then the AIO was actually called the AIC, but really it's AIO).

[HR][/HR]

You do not like bugs. This is unfortunate, since your town has been taken over by a plague of small insects. Thankfully these insects only come out every seven years — they appear all over town, make very loud noises for a few months, lay their eggs and then disappear, until a new generation of insects emerges from the eggs seven years later and the cycle starts over again.

It is well known that the insects only emerge during years that are exact multiples of seven. For instance, they appeared in the years 1995 and 2002 (since 1995 = 7 x 285 and 2002 = 7 x 286). You do a quick calculation and deduce that they will reappear in the year 2009. Flipping your calendar several years forward, you start making your plans for a very long holiday.

You must write a program to help you and your townsfolk plan ahead for the appearance of these insects in years to come. Your program must read in a year and output the first year after that in which the insects will emerge.

Input
The input will consist of a single line containing a single integer. This integer will represent a year, and will be between 1 and 10,000 inclusive.

Output
Your output should consist of a single line containing a single integer. This integer must be the first year after the input year in which the insects will reappear.

Sample Input 1
2004

Sample Output 1
2009

Sample Input 2
1991

Sample Output 2
1995

 

[Gigacube]

I also went this year Goldy. I do agree that there were a lot of people but I enjoyed being able to talk to a lot of like-minded people from across Australia and NZ. Do you think they'll accept more for the 2013 one?