COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
This material has been reproduced and communicated to you by or on behalf of Monash University pursuant to Part VB of the Copyright Act 1968 (the Act). The material in this communication may be subject to copyright under the Act. Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act. Do not remove this notice
(FIT3155 S1/2022, ) Unit Synopsis 1 / 14
Copyright By PowCoder代写 加微信 powcoder
Prepared by: [ ] Extended by:
FIT3155: Advanced Data Structures and Algorithms
Unit Synopsis
Faculty of Information Technology, Monash University
(FIT3155 S1/2022, ) Unit Synopsis 2 / 14
What’s this course about?
The subject is about efficient problem-solving with computers. The subject is about space and time efficient data structures and
algorithms.
The subject is not (mainly) about programming.
The subject just happens to use Python as the programming language in which lab work (etc.) is done. This subject is really language agnostic.
Algorithms in this unit will be presented/described in English, pseudo-code, procedural set of instructions, as convenient.
(FIT3155 S1/2022, ) Unit Synopsis 3 / 14
The subject aims to cover:
1 Advanced algorithmic problem-solving strategies, e.g. essential techniques such as
linear programming,
randomised algorithms
approximation algorithms,
advanced analysis such as
amortised analysis,
space- and time-efficient of data structures,
estimation of space and time complexity of algorithms, etc.
(FIT3155 S1/2022, )
Unit Synopsis 4 / 14
Broad overview of the unit’s weekly schedule (Tentative!)
Linear-time and online suffix tree construction using Ukkonen’s algorithm
Adv string pattern matching algorithms Z-algorithm for string preprocessing
Boyer-Moore and Knuth-Morris-Pratt linear-time pattern matching, both using Z-algorithm based preprocessing.
Adv disjoint-set data structure
w/ amortized O(1) Union/Find operations with focus on proofs
Adv heap data structures and analysis Binomial heap
Fibonacci heap
…continued in the next slide
(FIT3155 S1/2022, ) Unit Synopsis 5 / 14
Broad overview of the unit’s weekly schedule (Tentative!) …cont’d.
Generalized self-balancing search trees: B-tree Week 8
Number-theoretic/semi-numerical algorithms Week 9
Variable-length encoding and lossless Data compression.
Linear programming and Dantzig’s Simplex algorithm Week 11
Adv algorithms on Graphs Week 12
Approximation algorithms
(FIT3155 S1/2022, ) Unit Synopsis 6 / 14
Course material
Your main portal will be, as you already know, the unit’s Moodle page.
Material available on moodle will include:
Lecture notes and slides
Additional references
Practical (Lab) sheets
Tutorial sheets
Links to lecture and lab sessions
Lecture recordings
The unit’s Ed discussion page will be used to provide all unit announcements and is the best place to post queries about the unit.
(FIT3155 S1/2022, ) Unit Synopsis 7 / 14
Main textbook references
1 Cormen et al., Introduction to Algorithms Chapters: 18, 20, 29, 31, 33 and 35.
2 Weiss, Data structures and Algorithm analysis Chapters: 7, 8, 11 and 12.
3 Gusfield, Algorithms on Strings, Trees, and Sequences Chapters: 1, 2, and 6.
This subject will aid your development into professional programmers, technicians, software engineers, computer scientists, etc. Of course, you are strongly encouraged to build on this and read beyond what is prescribed for this unit.
(FIT3155 S1/2022, ) Unit Synopsis 8 / 14
Course structure
Lectures: (refer to your timetable for time/venue)
2 hours/week – refer to your timetable for time/venue
Tute+Prac (refer to your timetable for time/venue) 3 hours weekly, starting Week 2.
Assignments
3 assignments due over the teaching period Assignment 1 – 10% – due end of week 4
(released in week 2) Assignment 2 – 20% – due end of week 8
(released in week 6)
Assignment 3 – 10% – due end of week 12
(released in week 10)
(FIT3155 S1/2022, ) Unit Synopsis 9 / 14
Marks and Hurdles – IMPORTANT
To pass FIT3155
Your marks must average to at least 50% of the total marks for this unit, and
You must pass each of the hurdles (see next slide).
(FIT3155 S1/2022, ) Unit Synopsis 10 / 14
Assessment – IMPORTANT
In-semester assessment contributes to 40% of total unit marks
Assessed Prac marks = 40 (across 3 assignments). 100
HURDLE 1: You should score at least 45% of the in-semester marks (≥ 18 marks).
End-of-Semester Examination = 60% of total semester marks
End-of-Semester (written) exam carries 60 marks. HURDLE 2: You should score at least 45% of the exam
marks (≥ 27 marks). 60
(FIT3155 S1/2022, )
Unit Synopsis 11 / 14
Student responsibilities
Responsibilities
Regularly attend the weekly activities.
Diligent self-study (nominally 7 hours/week).
This subject is best understood practically. Internalizing its concepts by coding them up is the key to excel in it.
No noise and distractions during the lectures.
Mute your microphone if you are not currently using it. Be polite and patient.
(FIT3155 S1/2022, ) Unit Synopsis 12 / 14
Plagiarism and Cheating
Monash University takes plagiarism and cheating very seriously. There are severe penalties for them.
Read Monash University’s [Plagiarism and cheating Policy]
It is OKAY to work together in trying to understand concepts.
Peer Assisted learning (PAL) is fun and a great way to cross-fertilize each others’ thinking – but each student must be conscientious in her/his work, write code for the entire assignments alone, and be able to explain and modify it on request
All scripts will be screened through a powerful software for detecting software plagiarism.
(FIT3155 S1/2022, ) Unit Synopsis 13 / 14
Language and Learning Officer
Mr Noriaki Sato
Individual/group consultations and courses Hargrave-
http://www.lib.monash.edu/contacts/
learning-skills.html
http://www.monash.edu.au/lls/llonline
(FIT3155 S1/2022, ) Unit Synopsis 14 / 14
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com