41052 Advanced Algorithms
Warning: The information on this page is indicative. The subject outline for a
particular session, location and mode of offering is the authoritative source
of all information about the subject for that offering. Required texts, recommended texts and references in particular are likely to change. Students will be provided with a subject outline once they enrol in the subject.
Subject handbook information prior to 2024 is available in the Archives.
Credit points: 6 cp
Subject level:
Undergraduate
Result type: Grade and marksRequisite(s): 31251 Data Structures and Algorithms
Description
Algorithms are the heart of computer science and information technology. This subject moves beyond the basic material that introduces algorithms and data structures and looks at some of the more complicated algorithms, how to implement them and what they can be used for. Alongside this the subject delves into practical concerns of methods for dealing with apparently intractable computational problems, tools for selecting and evaluating algorithms and communicating effectively algorithmic strategies.
Subject learning objectives (SLOs)
Upon successful completion of this subject students should be able to:
| 1. | Understand computational problems and consider possible solutions in the context of their application areas. (D.1) |
|---|---|
| 2. | Apply advanced data structures, programming techniques and algorithmic paradigms to create efficient algorithms for computational problems. (C.1) |
| 3. | Evaluate the computational complexity of a problem or algorithm. (D.1) |
| 4. | Communicate the functioning of complex algorithms in collaboration with peers. (E.1) |
Course intended learning outcomes (CILOs)
This subject also contributes specifically to the development of the following Course Intended Learning Outcomes (CILOs):
- Design Oriented: FEIT graduates apply problem solving, design and decision-making methodologies to develop components, systems and processes to meet specified requirements. (C.1)
- Technically Proficient: FEIT graduates apply abstraction, mathematics and discipline fundamentals, software, tools and techniques to evaluate, implement and operate systems. (D.1)
- Collaborative and Communicative: FEIT graduates work as an effective member or leader of diverse teams, communicating effectively and operating within cross-disciplinary and cross-cultural contexts in the workplace. (E.1)
Teaching and learning strategies
This subject mixes classical maieutics with hands-on practical work to encourage the challenging of assumptions and the scaffolded development of self-constructed abstract models of the topic material. This approach is supported with suitable source material for grounding knowledge and custom test driven development to encourage explorative programming.
Content (topics)
• Advanced Data Structures (for example: Heaps, Tries, Fibonacci Trees, Directed Graphs, Union Find Structures)
• Polynomial Time Algorithms (for example: Advanced Sorting Algorithms, Flow Networks, Linear Programming, limits of Polynomial time computability)
• Dealing with Intractability
- Approximation Algorithms
- Parameterized Algorithms
- Heuristics and Metaheuristics
- Integer Linear and Constraint Programming
Assessment
Assessment task 1: Programming Assignment 1
| Intent: | Demonstrate the ability to implement a non-trivial algorithmic solution to a computational problem and justify the choice of solution through algorithmic and computational complexity arguments. Prepare a report detailing the design and its justifications. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 2, 3 and 4 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1, D.1 and E.1 |
| Type: | Project |
| Groupwork: | Individual |
| Weight: | 30% |
| Length: | Code + ~500 words. |
Assessment task 2: Algorithmic Research
| Intent: | Demonstrate abstract understanding of algorithms (as separate from implementation issues) and convey this understanding to fellow students. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 1, 3 and 4 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): D.1 and E.1 |
| Type: | Report |
| Groupwork: | Individual |
| Weight: | 30% |
| Length: | 100 words + 10 minutes |
Assessment task 3: Programming Assignment 2
| Intent: | Demonstrate the ability to combine simpler algorithms to produce a solution to a complicated computational problem. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 1, 2, 3 and 4 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1, D.1 and E.1 |
| Type: | Project |
| Groupwork: | Group, group and individually assessed |
| Weight: | 30% |
| Length: | Code + ~1000 words. |
Assessment task 4: Knowledge Quizzes
| Intent: | Promote understanding of algorithmic theory that supports the subject material. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 2, 3 and 4 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1, D.1 and E.1 |
| Type: | Quiz/test |
| Groupwork: | Individual |
| Weight: | 10% |
| Length: | N/A |
Minimum requirements
To pass this subject students must achieve an overall mark of 50% or greater.
Recommended texts
General Algorithms Books
- Corman, Leiserson, Rivest, Stein, “Introduction to Algorithms”, MDP, 4th Ed. 2022.
- Skiena, “The Algorithm Design Manual”, Springer, 2nd Ed., 2008.
- Sedgewick and Wayne, “Algorithms”, Addison-Wesley, 4th Ed., 2016.
- Kleinberg and Tardos, “Algorithm Design”, Pearson, 1st Ed., 2005.
- Roughgarden, “Algorithms Illuminated”, v1-4, 2017-2021.
- Edmonds, “How to Think About Algorithms”, Cambridge University Press, 1st Ed., 2008.
- Knuth, “The Art of Computer Programming”, Good luck!
- Levitin, "Introduction to the Design and Analysis of Algorithms", Addison-Wesley, 1st Ed., 2003.
More Specialised Books
- Cygan, et. al, "Parameterized Algorithms", Springer, 1st Ed., 2015.
- Fomin and Kratsch, "Exact Exponential Algorithms", Springer, 1st Ed., 2010.
- Vazirani, "Approximation Algorithms", Springer, 1st Ed., 2003.
- Ausiello, et. al, "Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties", Springer, 1st Ed., 1999.
- Neri, Cotta and Moscato, "Handbook of Memetic Algorithms", Springer, 2nd Ed., 2012.
- Greenlaw, Hoover and Ruzzo, "Limits to Parallel Computation: P-Completeness Theory", OUP, 1995.