Go to JKU Homepage
LIT Cyber-Physical Systems Lab
What's that?

Institutes, schools, other departments, and programs create their own web content and menus.

To help you better navigate the site, see here where you are at the moment.

Algorithms and Data structure

VL Algorithms and Data structure (Lecture)

Algorithms are the basis of software development. They bridge computer science theory and programming.

In this lecture students learn about the important core characteristics and classes of algorithms with a focus on their practical use to implement software systems and solve concrete problems.

Content:

* Algorithms: definition, algorithms vs. programs, representing algorithms, abstraction layers and characteristics of algorithms

* Specifications: objectives, Interface descriptions, requirements, representing specifications

* Step-wise refinement: "divide & conquer", systematic problem solving, examples

* Algorithms with a memory: term and definition, ways to implement algorithms with a memory

* Complexity: terms and definitions, runtime analysis, runtime measurements, asymptotic complexity, minimal complexity of problems

* Dynamic data structures: classes and references, linear lists, unsorted lists, sorted lists, ring lists, double-connected lists, stacks, queues, sets

* Recursion: term and definition, classification, termination, applications, transforming recursive into iterative algorithms

* Sorting: selection sort, insertion sort, shell sort, quick sort, merge sort, sorting lists, heap sort, topological sort, complexity of sorting algorithms

* Trees: term and definition, binary search trees, balanced trees, topdown-234-trees, black-red-trees, B-trees

* Graphs: term and definition, depth-first-search, breadth-first-search, smallest spanning tree, shortest path, transitive hull, serialization of graphs

* Exhaustion: n-queens problem, schema to search a solution, using exhaustion to find a solution, optimization, representing solution vectors, approximation, non-deterministic algorithms

* Classification of algorithms

 

Methods:

The lecture mostly is based on algorithms in pseudo code. This allows learning algorithms independent of a concrete programming language.

Some parts of the lecture are supported by demo videos. Some algorithms are constructed on the blackboard or whiteboard step by step.

The exercises are meant to detail and deepen what is learnt in the lecture. Exercises are thus defined based on the contents of the lecture. Students shall use a recent object-oriented programming language (e.g., Java) to practice designing and implementing the algorithms that are presented in the lecture, using simple yet realistic examples. In the exercise units, students and lecturers discuss exercises including example solutions.

 

Course work:

VO: lecture exam at the end ot the semester

UE:  evaluation of elaborated sentences

 

Documents:

The lecture is mainly based on slides. Slides and additional material will be made available for download in PDF format.

 

Literature:

  • Aho A.V., Hopcroft J.E., Ullman J.D.: Data Structures and Algorithms.  Addison-Wesley 1983.
  • Goodrich, M. T., Tamassia, R., and Goldwasser, M. H.: Data structures and algorithms in Java. John Wiley & Sons. 2014.
  • Knuth D.E.: The Art of Computer Programming. Addison-Wesley 1973.

              --> Band 1: Fundamental Algorithms.

              --> Band 2: Seminumerical Algorithms.

              --> Band 3: Sorting and Searching.

  • Pomberger G., Dobler H.: Algorithmen und Datenstrukturen. Pearson 2008.
  • Saake G., Sattler K.: Algorithmen und Datenstrukturen. dpunkt 2006.
  • Sedgewick R.: Algorithmen in Java. Pearson 2014.
  • Wirth N.: Algorithmen und Datenstrukturen. Teubner Studienbücher Informatik 1986.

 

Links

Visualization und animation of different Algorithmen: here, opens an external URL in a new window and here, opens an external URL in a new window.

.

{{ labelInLang('cid') }} {{ labelInLang('title') }} {{ labelInLang('registration') }} {{ labelInLang('type') }} {{ labelInLang('hours') }} {{ labelInLang('teachers') }} {{ labelInLang('rhythm') }}
{{ item._id }} ({{ item.term }}) {{ item.title }}: {{ item.subtitle }}
{{ labelInLang('moreinfo') }}
{{ labelInLang('expand') }} {{ labelInLang('collapse') }}
{{ labelInLang('register') }} {{ item.type }} {{ item['hours-per-week'] }} {{ teacher.firstname }} {{ teacher.lastname }} {{ item.teachers.teacher.firstname }} {{ item.teachers.teacher.lastname }} {{ item.rhythm }}
{{ item._id }} ({{ item.term }})
{{ labelInLang('title') }} {{ item.title }}: {{ item.subtitle }}
{{ labelInLang('moreinfo') }}
{{ labelInLang('expand') }} {{ labelInLang('collapse') }}
{{ labelInLang('registration') }} {{ labelInLang('register') }}
{{ labelInLang('type') }} {{ item.type }}
{{ labelInLang('hours') }} {{ item['hours-per-week'] }}
{{ labelInLang('teachers') }} {{ teacher.firstname }} {{ teacher.lastname }} {{ item.teachers.teacher.firstname }} {{ item.teachers.teacher.lastname }}
{{ labelInLang('rhythm') }} {{ item.rhythm }}
 

UE Algorithms and Data Structures (exercises for Mechatronik, ELIT, Engineering)

The exercises for Algorithms and Data Structures serve to deepen the contents of the lecture of the same name. The exercises are accordingly closely adapted to the lecture material and handed out.

Information about the lecture can be found here

There will be 9 exercise sheets on the topics of the lecture. The exercise preliminary meeting will take place on Wednesday, 08 March 2023 during the lecture. The first exercise session with the issue of the first exercise sheet on Wednesday, 15 March 2023.

510.211   UE Algorithms and Data Structures

1 UE

Feichtinger

MI 12:00-12:45

Room: HS 14

Start: 15.03.2023, preliminary discussion on 08.03.2023 in the context of the first VL

510.214   UE Algorithms and Data Structures

1 UE

Feichtinger

MI 12:45-13:30

Room: HS 14

Start: 15.03.2023, preliminary discussion on 08.03.2023 in the context of the first VL

510.215   UE Algorithms and Data Structures

1 UE

Feichtinger

MI 13:45-14:30

Room: HS 14

Start: 15.03.2023, preliminary discussion on 08.03.2023 in the context of the first VL

Exercise mode

  • Discussion of open questions/sample solutions
  • Illustration of the exercises by examples
  • Presentation of the current task
  • No compulsory attendance

Tutorium

A virtual Tutorium with the tutors is held every Tuesday 4:15pm – 5:00pm. The Zoom link is provided in  Moodle.

Exercise submission

  • Electronic submission of exercises in the Moodle course
  • Each exercise has at least a 7 day processing period. Hard deadline at 23:59:00!.
  • Only ZIP archives and/or PDF are accepted as submission formats.
  • PDF for (hand-)written assignments; ZIP for programming assignments.
  • The files to be submitted must follow a naming convention:
    • algo1_ue<nr>_<matrNr>.zip (example: algo1_ue02 _01255105.zip).
  • All classes relevant for the solution are to be stored in a Java package.
  • Only individual work will be accepted. Detected plagiarism will be penalized. At minimum ALL involved parties get 0 points WITHOUT exception. Further actions will be determined. Changing variable names or similar does not prevent plagiarism.

Grading

  • A total of 9 exercise sheets, each with different tasks related to the lecture.
  • 3 of the first 4 exercises and 3 of the second 4 exercises must be submitted. Exercise 9 is for preparation of the exam.
  • A maximum of 24 points can be achieved in each exercise.
  • The 8 best exercises of the 9 exercises will be included in the grade.
  • The sum of the achieved points of 8 best graded exercises determines the grade.
  • Exercises not handed in will be graded with 0 points.

Grades

Grade

Minimum

Maximum

Sehr Gut

>=168

<=192

Gut

>=144

<168

Befriedigend

>=120

<144

Genügend

>=96

<120

Nicht Genügend

0

<96

Material

The exercise details and supplementary material for the course are available for download in the Moodle course.

{{ labelInLang('cid') }} {{ labelInLang('title') }} {{ labelInLang('registration') }} {{ labelInLang('type') }} {{ labelInLang('hours') }} {{ labelInLang('teachers') }} {{ labelInLang('rhythm') }}
{{ item._id }} ({{ item.term }}) {{ item.title }}: {{ item.subtitle }}
{{ labelInLang('moreinfo') }}
{{ labelInLang('expand') }} {{ labelInLang('collapse') }}
{{ labelInLang('register') }} {{ item.type }} {{ item['hours-per-week'] }} {{ teacher.firstname }} {{ teacher.lastname }} {{ item.teachers.teacher.firstname }} {{ item.teachers.teacher.lastname }} {{ item.rhythm }}
{{ item._id }} ({{ item.term }})
{{ labelInLang('title') }} {{ item.title }}: {{ item.subtitle }}
{{ labelInLang('moreinfo') }}
{{ labelInLang('expand') }} {{ labelInLang('collapse') }}
{{ labelInLang('registration') }} {{ labelInLang('register') }}
{{ labelInLang('type') }} {{ item.type }}
{{ labelInLang('hours') }} {{ item['hours-per-week'] }}
{{ labelInLang('teachers') }} {{ teacher.firstname }} {{ teacher.lastname }} {{ item.teachers.teacher.firstname }} {{ item.teachers.teacher.lastname }}
{{ labelInLang('rhythm') }} {{ item.rhythm }}