Transcript What is Research? - Muhammad Aamir Cheema

Outline





Who am I?
What is research?
My Research
Higher studies opportunities in Australia
Getting jobs in IT industry
Presented by:
Muhammad Aamir Cheema, Lecturer IT at James
Cook University Australia, Sydney campus
Who Am I? A Student




BSc. Electrical Engineering UET Lahore
(2001-2005)
Masters by research University of New South
Wales (UNSW) Sydney (2005-2007)
Currently a PhD Student at UNSW Sydney
Research Area: Databases
Who Am I? A Teacher



Tutor @ University of New South Wales, Sydney
Lecturer IT @ James Cook University Sydney
Campus
Courses Taught:






Database Systems Implementation
Database Systems
Operating Systems and Architectures
E-Business Technologies
Portable Programming
C++
What is Research?

Formally “a form of systematic enquiry that
contributes to knowledge.”
Is research boring and difficult???
NOT AT ALL if you like solving puzzles
Informally,
Research ≈ Solving Puzzles
Let’s Play a Game1
Task: Find the missing number
Given: Data set consists of numbers from 1 to 20
Version 1:
 Numbers are not displayed on the screen
Version 2:
 Find the missing number from the list below
4,2,8,18,1,20,17,9,16,15,13,3,12,19,6,5,14,7,10
Version 1 is more difficult because:
1. No element can be seen twice
2. We cannot memorize all the numbers
1- Data Streams: Algorithms and Applications, S. Muthukrishnan
Brute Force Solution for
Version 2
4,2,8,1,10,9,5,3,6
Is 1 missing?
 Is 2 missing?
 Is 3 missing? . . .
Algorithm:
 For each number i from 1 to n
 Check whether i is missing or not

Performance:
Space Usage:
Running Time:
(n-1) elements  O(n)
O(n2)
Sorting: A faster solution
4,2,8,1,10,9,5,3,6
1,2,3,4,5,6,8,9,10
Sort the numbers
 Scan the list to find missing number
Performance:
Space Storage: O(n)
Running Time: sorting time + final scan
nlogn +
n


O(nlogn)
Bucket: Even faster approach
4,2,8,1,10,9,5,3,6
Algorithm:
 create an empty array of size n
 For each element i in the list

Mark the element at index [ i ]
Unmarked index is the missing number
Performance:
Space Requirement: O(n)
Running Time:
O(n)

Solution for Version 1???
What we have done so far:

Developed solution for Version 2

Performance: Space Usage: O(n)
Running Time: O(n)
Version 1:
A solution is required that
1.
2.
Accesses each element only once Running Time: O(n)
Memorizes only one number
Space Usage: O(1)
An example application: data passing through a network node
(e.g; a router cannot store all the data passing through it
and can see each element only once)
Hint
Given: numbers are from 1 to 10
Task: Nine numbers from the data are sent to
user one by one, find the missing number
Sum of the numbers from 1 to 10 is 55
Solution
Given: Numbers are from 1 to n
Algorithm:
 Find the sum of 1 to n numbers S=n(n+1)/2
 For each number i

S=S-i
S is missing number
Performance:
Space Usage: O(1)
Running Time: O(n)

My Research
Nearest Neighbors Problem
Given a set of objects O, find k objects closest
to any given query object
 Objects are represented by their location
coordinates
Applications:



Find 5 taxis nearest to my current location
Find 3 hotels closest to Islamabad Airport
A Brute Force Solution
Algorithm:
Let q be the query object
 For each object x


Find the distance of x from q
Report the k objects with the minimum
distance from q
Problems with the brute force
approach

Distance of all objects from the query object
is to be calculated Running Time = O(n)
What if all the objects are moving (e.g cars on a
road)???
 To update the results, compute distance of all
objects again
A better solution

Compute the distance of only the objects in
vicinity of the query object q
How to find the objects that lie in vicinity of q?
Use some spatial Index. i.e; grid index
CircularTrip1


Explore the objects around q in an iteratively increased circle
Use grid based index (visit the cells around q that intersect the
circle)
p1
r
q
p2
1- Muhammad Aamir Cheema, Yidong Yuan, Xuemin Lin, "CircularTrip: An
Effective Algorithm for Continuous kNN Queries", DASFAA 2007, Thailand.
Updating the result on movement of objects





Incoming objects: any non-result object p
entering inside the circle

Insert p into answer list
Outgoing objects: any result object leaving the
circle

delete p from answer list
Hanlde all the object updates as mentioned
above
Case 1: answer list contains k or more than k
objects

Keep k closest objects and discard other
Case 2: answer list contains less than k objects

Same as initial computation except the
starting radius is distk
p
1
q
distk
p2
Higher Studies Opportunities
in Australia

Student Visa




Apply in any institution you like
Get admission letter
Take IELTS exam (you need 6 band overall)
Show bank statement
Permanent Visa





Get three year work experience in Pakistan
Take IELTS (minimum 7 band in each module)
Apply for Permanent residence (PR) visa
Go there and get education with benefits of being a citizen
of Australia (e.g; more scholarship opportunities, HEC loan
etc)
Higher studies opportunities in
Australia

Student Visa



Quick (you will not need to wait to complete 3 yrs work
experience to get PR)
You become eligible for PR once you complete your
degree (duration must be at least 2 years) in Australia
Permanent Visa

Less expensive (once you are citizen your chances of
getting scholarship grow enormously)
When Australia?


Education in Australia is not cheap but
Australia is accomodating
Prefer European countries or try HEC
scholarships if you are not interested in
settling abroad
Getting Jobs in IT industry
University degrees teach you little bit of
everything
 A regular student becomes “Jack of all trades
but master of none”
 To get good jobs, you must become “Jack of all
trades AND master of ONE”
Moral: Be master in at least on skill. e.g; JAVA,
C++, networking, web development etc.

Try to learn something about everything and everything about something
Contact Information



www.cse.unsw.edu.au/~macheema
Google search “Muhammad Aamir Cheema”
[email protected]
THANKS