Studying at York
Software 2: Object Oriented Data Structures & Algorithms - COM00016C
Module summary
Object Oriented Data Structures and Algorithms
Module will run
| Occurrence | Teaching period |
|---|---|
| A | Spring Term 2022-23 to Summer Term 2022-23 |
Module aims
Students begin to program key data structures such as stacks, queues, trees and graphs. They are introduced to the idea of complexity of an algorithm, and how to characterise time and space through formal notations and proof techniques. Students are taught using an object oriented language like Java, and learn the basics of test driven development for testing their code and demonstrating its successful running. Students are also introduced to several algorithm design paradigms such as greedy algorithms.
Module learning outcomes
|
S201 |
Implement an object oriented design. This includes organizing program code into modules using methods following the software engineering principles of modularity and abstraction, and assembling data and methods into classes at an introductory level following the software engineering principles of encapsulation and data hiding. |
|
S202 |
Write and test code that conforms to specific interfaces. Identify and correct bugs which prevent the program from functioning as intended. |
|
S203 |
Integrate standard library code with their own programs using appropriate software tools. Store and retrieve data from simple text files (sufficient to save and restore state for simple programs). understand and apply object serialization. |
|
S204 |
Organize and document program code following the principles of software engineering. Generate documentation, manually and programmatically, to explain the design and implementation of their own code, or example code which is supplied to them. |
|
S205 |
Analyze problems in order to confidently design algorithms to solve simple problems,and be able to explain how algorithms and Processing programs work. Develop small programs that implement basic algorithmic designs. |
|
S206 |
Analyze worst-case running times of algorithms using asymptotic analysis and apply the knowledge to sorting and searching algorithms, categorising efficiency in time and memory use. |
|
S207 |
Compare between different abstract data structures from linked lists to graphs in order to be able to choose an appropriate data structure for a design situation. This includes the major search, sort, and graph algorithms and their analyses. |
|
S208 |
Apply algorithmic design paradigms such as greedy and dynamic programming paradigms. Present an argumentation for the choice of a paradigm for a given problem. |
|
S209 |
Describe what an approximation algorithm is, the benefit of using approximation algorithms, and analyse the approximation factor for such an algorithm. |
|
S210 |
Argue the correctness of algorithms using inductive proofs and invariants. |
|
S211 |
Discuss the practice of code reuse and how it interacts with personal copyright, trademarks, license and intellectual property rights. |
Indicative assessment
| Task | % of module mark |
|---|---|
| Online Exam -less than 24hrs (Centrally scheduled) | 50 |
| Online Exam -less than 24hrs (Centrally scheduled) | 50 |
Special assessment rules
None
Indicative reassessment
| Task | % of module mark |
|---|---|
| Online Exam -less than 24hrs (Centrally scheduled) | 50 |
| Online Exam -less than 24hrs (Centrally scheduled) | 50 |
Module feedback
Feedback is provided through work in practical sessions, formative assessments, and after the final assessment as per normal University guidelines.
Indicative reading
Steven S. Skiena - The algorithm design manual - 2nd ed., (2010), Springer
Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser - Data Structures and Algorithms in Java (2014), Wiley Etextbooks
Mitsunori Ogihara - Fundamentals of Java programming (2018), Springer