Data structures and algorithms

The course is a compulsory course in the N1SOF Software Engineering and Management Bachelor's Programme.

The course can also be part of the following programmes:

1. Applied Data Science Master's Programme (N2ADS)
2. Mathematical Sciences, Master's Programme (N2MAT)
3. Bachelor's Programme in Mathematics (N1MAT)

To be eligible for this course, students must have successfully completed:

• 15 hec in programming (e.g., DIT009 Fundamentals of programming, 7.5 hec, and DIT044 Object-oriented programming, 7.5 hec, or equivalent)
• 7.5 hec in discrete mathematics (e.g., DIT008 Discrete mathematics, DIT984 Discrete mathematics for computer scientists, the sub-course Introductory algebra of MMG200 Mathematics 1, or equivalent).

Data structures and algorithms are fundamental building blocks in almost all software products. Knowledge and skills in data abstraction, data structures, and algorithms are important in the construction, use, and maintenance of adaptable, reusable, correct, and efficient program components.

The course gives knowledge and skills in the construction and use of algorithms and data structures, an introduction to various techniques for the analysis of algorithms, and insights in the advantages of using data abstraction in program development.

The following topics are covered by the course:

• abstract data types
• data structures and algorithms focusing on imperative och object-oriented languages
• common data structures such as arrays, linked lists, unbalanced and balanced trees, heaps, and hash tables
• how these can be used to implement abstract data types such as stacks, queues, priority queues, maps, sets, and graphs
• standard algorithms for these data structures, including their resource demands
• searching and sorting algorithms
• using different libraries for data structures and algorithms
• basic complexity analysis of data structures and algorithms

On successful completion of the course the student will be able to:

Knowledge and understanding

• explain basic abstract data types and data structures, including lists, queues, hash tables, trees, and graphs
• explain some of the algorithms used to manipulate and query these data structures in an efficient way, and explain why they are correct

Competence and skills

• apply basic abstract data types and data structures, and algorithms related to these
• implement and use abstract data types as interfaces, and data structures as classes, in an object-oriented programming language
• read, specify, and describe algorithms, at a higher level of abstraction than code

Judgement and approach

• analyse the efficiency of basic algorithms and data structures
• make informed choices between different data structures and algorithms for different applications

The teaching consists of lectures, exercises and supervised group work.

Language of instruction: English

The course is examined by an individual written exam (4.5 hec), and assignments carried out in groups (3.0 hec).

If a student who has twice received a failing grade for the same examination component wishes to change examiner ahead of the next examination session, such a request should be made to the department in writing and should be approved by the department unless there are special reasons to the contrary (Chapter 6 Section 22 of the Higher Education Ordinance).

If a student has received a recommendation from the University of Gothenburg for study support for students with disabilities, the examiner may, where it is compatible with the learning outcomes of the course and provided that no unreasonable resources are required, decide to allow the student to sit an adjusted exam or alternative form of assessment.

In the event that a course has ceased or undergone major changes, students are to be guaranteed at least three examination sessions (including the ordinary examination session) over a period of at least one year, but no more than two years after the course has ceased/been changed. The same applies to internships and professional placements (VFU), although this is restricted to just one additional examination session.

Sub-courses

1. Written hall examination (Skriftlig salstentamen), 4.5 credits
   Grading scale: Pass with distinction (5), Pass with credit (4), Pass (3) and Fail (U)
2. Pass with credit (4), Pass (3) and Fail (U)
   Grading scale: Pass (G) and Fail (U)

The grading scale comprises: Pass with distinction (5), Pass with credit (4), Pass (3) and Fail (U). The final grade is given based on the grade for the written exam.

The results of and possible changes to the course will be shared with students who participated in the evaluation and students who are starting the course.

The course can be taught together with Chalmers.

Course literature to be announced the latest 8 weeks prior to the start of the course.

The course replaces the course DIT182, 7.5 hec. The course cannot be included in a degree which contains DIT182. Neither can the course be included in a degree which is based on another degree in which the course DIT182 is included.