INFO5011: Introduction to Competitive Programming and Problem Solving (2019 - Semester 2)

Download UoS Outline

Unit: INFO5011: IT Advanced Topic B (6 CP)
Mode: Normal-Day
On Offer: Yes
Level: Postgraduate
Faculty/School: School of Computer Science
Unit Coordinator/s: Chang, Lijun
Session options: Semester 1, Semester 2
Versions for this Unit:
Campus: Camperdown/Darlington
Pre-Requisites: [Special permission by the School of Computer Science].
Brief Handbook Description: This unit will cover some topic of active and cutting-edge research within IT; the content of this unit may be varied depending on special opportunities such as a distinguished researcher visiting the University.

In 2019 semester 2, the topic will be an introduction to competitive programming and problem solving. We will look at advanced algorithm design techniques and data structures that are frequently used in programming competitions but are not well covered by COMP2823 and COMP3927. The main purpose of this unit of study is to train USYD’s programming competition teams for ICPC divisional contest and regional contest (https://acm-usyd.github.io/). This unit of study may also be useful when preparing for technical interviews of companies such as Google and Facebook.

To enrol in this unit of study, you should (1) have strong (C/C++, or Java, or Python) programming background, (2) have basic knowledge about data structures and algorithms (e.g., how to analyse the time complexity of an algorithm), and (3) be comfortable with designing and implementing complex data structures and algorithms.
Assumed Knowledge: None.
Department Permission Department permission is required for enrollment in this session.
Lecturer/s: Chang, Lijun
Timetable: INFO5011 Timetable
Time Commitment:
# Activity Name Hours per Week Sessions per Week Weeks per Semester
1 Lecture 2.00 1 13
2 Independent Study and Homework 10.00
Policies & Procedures: IMPORTANT: School policy relating to Academic Dishonesty and Plagiarism.

In assessing a piece of submitted work, the School of Computer Science may reproduce it entirely, may provide a copy to another member of faculty, and/or to an external plagiarism checking service or in-house computer program and may also maintain a copy of the assignment for future checking purposes and/or allow an external service to do so.

Other policies

See the policies page of the faculty website at http://sydney.edu.au/engineering/student-policies/ for information regarding university policies and local provisions and procedures within the Faculty of Engineering and Information Technologies.

Note that the "Weeks" referred to in this Schedule are those of the official university semester calendar https://web.timetable.usyd.edu.au/calendar.jsp

Week Description
Week 1 Lecture: Introduction (Maximum Range Sum)
Week 2 Lecture: Problem Solving Paradigms I (Complete Search, Dynamic Programming, Greedy)
Week 3 Lecture: Advanced Dynamic Programming I
Week 4 Lecture: Graph Algorithms (DFS/BFS, Shortest Path, MST, SCC)
Week 5 Lecture: Problem Solving Paradigms II (Binary Search, Divide and Conquer, Meet in the Middle, Matrix Power)
Week 6 Lecture: Number Theory, Combinatorial Counting, and String Matching
Week 7 Lecture: Data Structures for Online Query Problems (Segment Tree, Binary Indexed Tree)
Week 8 Lecture: Advanced Dynamic Programming II
Week 9 No Lecture, Public Holiday
Week 10 Lecture: Combinatorial Games and Suffix Array
Week 11 Lecture: Computational Geometry
Week 12 Lecture: Network Flow and Bipartite Matching
Week 13 Lecture: Miscellaneous Topics

Course Relations

The following is a list of courses which have added this Unit to their structure.

Course Year(s) Offered
Bachelor of Advanced Computing/Bachelor of Commerce 2018, 2019, 2020
Bachelor of Advanced Computing/Bachelor of Science 2018, 2019, 2020
Bachelor of Advanced Computing/Bachelor of Science (Health) 2018, 2019, 2020
Bachelor of Advanced Computing/Bachelor of Science (Medical Science) 2018, 2019, 2020
Bachelor of Advanced Computing (Computational Data Science) 2018, 2019, 2020
Bachelor of Advanced Computing (Computer Science Major) 2018, 2019, 2020
Bachelor of Advanced Computing (Information Systems Major) 2018, 2019, 2020
Bachelor of Advanced Computing (Software Development) 2018, 2019, 2020
Bachelor of Computer Science and Technology (Honours) 2014 2013, 2014
Graduate Certificate in Information Technology 2015, 2016, 2017, 2018, 2019, 2020
Graduate Diploma in Information Technology 2015, 2016, 2017, 2018, 2019, 2020
Graduate Certificate in Information Technology (till 2014) 2013, 2014
Graduate Diploma in Information Technology (till 2014) 2013, 2014
Master of Information Technology 2015, 2016, 2017, 2018, 2019, 2020
Master of Information Technology Management 2016, 2017, 2018, 2019, 2020
Master of IT/Master of IT Management 2017, 2018, 2019, 2020
Master of Information Technology (till 2014) 2014

Course Goals

This unit contributes to the achievement of the following course goals:

Attribute Practiced Assessed
Unit has not been assigned any attributes yet.

These goals are selected from Engineering & IT Graduate Outcomes Table 2018 which defines overall goals for courses where this unit is primarily offered. See Engineering & IT Graduate Outcomes Table 2018 for details of the attributes and levels to be developed in the course as a whole. Percentage figures alongside each course goal provide a rough indication of their relative weighting in assessment for this unit. Note that not all goals are necessarily part of assessment. Some may be more about practice activity. See Learning outcomes for details of what is assessed in relation to each goal and Assessment for details of how the outcome is assessed. See Attributes for details of practice provided for each goal.