Design and Analysis of Algorithms
Objectives
Knowledge
Define and identify three algorithm design techniques: greedy strategies, dynamic programming and transform-and-conquer.
Know the fundamental graph algorithms, the required abstract data types and the data structures used to implement them efficiently.
Understand amortized analysis.
Define some complexity classes and understand some open problems.
Application
Design and analyse a dynamic programming algorithm.
Formulate a clean graph problem from a real-world problem and adapt a classical algorithm to solve it.
Choose, compare, adapt, and use suitable data structures for a given problem.
Calculate the running time of an algorithm based on the amortized running times of the inner functions and perform their amortized analysis.
Evaluate solutions and justify choices.
Make NP-complete proofs.
General characterization
Code
8154
Credits
6.0
Responsible teacher
Margarida Paula Neves Mamede
Hours
Weekly - 5
Total - 67
Teaching language
Português
Prerequisites
Students should:
(a) be proficient in object-oriented programming;
(b) be familiar with the fundamental data structures (linked lists, hash tables, binary search trees, binary heaps);
(c) be able to calculate the time and the space complexities of algorithms.
Bibliography
Main References
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (4th ed.). The MIT Press, 2022.
Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.
Complementary References
Anany Levitin. Introduction to The Design and Analysis of Algorithms (3rd ed.). Addison-Wesley, 2012.
S. Sridhar. Design and Analysis of Algorithms. Oxford University Press, 2014.
Dexter Kozen. The Design and Analysis of Algorithms. Springer, 1992.
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.
Steven S. Skiena. The Algorithm Design Manual (3rd ed.). Springer, 2020.
Steven S. Skiena and Miguel A. Revilla. Programming Challenges: The Programming Contest Training Manual. Springer, 2003.
Teaching method
There are three hours of lectures and a lab session each week. In the laboratory, students design, analyse and implement algorithms.
Evaluation method
Assessment Components
Assessment has two components: the laboratory component and the theoretical-practical component.
Laboratory Component
The laboratory component comprises three programming projects. Each programming project consists in the design, analysis and implementation of an algorithm for solving a programming contest problem, in the writing of a report and in a discussion. The first two parts (program and report) are done in teams of two students; the discussion is done individually.
A team delivers a programming project if their program is accepted by Mooshak and the corresponding report is delivered on Moodle within the deadline. Grades for delivered programming projects range from 10 to 20 points (out of 20).
Discussions (to assess each student''s understanding of the delivered programming projects) are mandatory, in person, and individual. The discussion of a programming project consists in making changes to the delivered code so that the new program solves a variant of the original problem, defined in the discussion statement, which differs slightly from the problem solved in the programming project. Discussion grades and their criteria are the following:
- 20: the change is generally correct;
- 16: the change is confusing or very incomplete, but the direction taken is not wrong;
- 12: the change is not correct, with "some things done well and others very poorly";
- 4: no change was made, or the changes made are minor (e.g., only changing the input reading), or the changes made do not make sense.
In general, the student''s grade in a programming project is the minimum between the grade of the delivered programming project (carried out in a team) and their grade in the discussion of that programming project (which is zero if the student was absent). But the student''s grade may be lower when the performance of their team partner in the discussion of all programming projects is very poor (rated 4). Consequently, the grades of the two team members may differ (ranging from 0 to the grade of the programming project).
The laboratory component grade (LComp) is the mean of the student''s grades in the three programming projects (P1, P2 and P3):
In order to succeed (and to have access to the exam), it is required that LComp >= 7.0 .
Discussions will take place at the end of the semester, only with students who have delivered at least two programming projects.
Theoretical-Practical Component
The theoretical-practical component comprises two tests. If the mean of the test grades is less than 9.5 and LComp >= 7.0, students can do an indivisible final exam. The tests and the exam are written, open-book, and done individually in person. Each student can consult any material, as long as it is on paper and the student brought it to the test or exam. Electronic devices (e.g., calculators, mobile phones, smartwatches, tablets, and laptops) are not allowed.
Pre-registration is required for the tests.
The theoretical-practical component grade (TPComp) is the mean of the test grades (T1 and T2) or the exam grade (Ex):
In order to succeed, it is required that TPComp >= 9.5 .
Final Grade
The final grade (F), defined only if LComp >= 7.0, is:
- F = TPComp, if TPComp < 9.5;
- F = 0.3 LComp + 0.7 TPComp, if TPComp >= 9.5 .
All grades (P1, P2, P3, T1, T2, Ex, LComp, and TPComp) are rounded to the nearest tenth, except the final grade (F) which is rounded to the nearest whole number.
Fraud and Plagiarism
Issues of fraud and plagiarism will be dealt with in accordance with the FCT NOVA Knowledge Assessment Regulation.
Students are allowed to talk to their colleagues about the programming projects and discuss solutions, but they are prohibited from sharing code (even only "a few lines") under any circumstances, whether orally or in writing. Writing code must be an internal task within each team. For example, displaying code on the screen, dictating code, sending files with code, or placing them on sites accessible to third parties is not permitted. It is considered that:
- a team that gives or receives code is committing fraud;
- a team in which only one member is working is committing fraud;
- students who collaborate in larger groups, sharing code, are committing fraud.
The use of AI tools (such as ChatGPT or Copilot) must be explicitly mentioned in the code. A team that uses these tools while carrying out a programming project and omits their usage is considered to be committing plagiarism.
Subject matter
(1) Dynamic programming.
(2) Introduction to the study of graphs. Fundamental definitions. The abstract data types undirected graph and directed graph. Implementations of graphs.
(3) Elementary graph algorithms. Depth-first and breadth-first traversals. Topological sorting.
(4) Minimum spanning trees. Kruskal’s algorithm. The disjoint sets abstract data type.
(5) Amortized analysis. The potential method.
(6) Prim’s algorithm. The adaptable priority queue abstract data type.
(7) Flow networks. Maximum flows. The Ford-Fulkerson method. The algorithms of Edmonds-Karp and Dinic. Maximum bipartite matchings. Minimum cuts.
(8) Shortest paths. The algorithms of Dijkstra, Bellman-Ford, and Floyd-Warshall.
(9) Introduction to the Theory of Complexity. The classes P, NP, PSPACE, and EXPTIME. The suffixes hard and complete. Problem reductions. Some open problems.