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 und he, opens an external URL in a new windowre

.

{{ labelInLang('cid') }} {{ labelInLang('title') }} {{ labelInLang('registration') }} {{ labelInLang('type') }} {{ labelInLang('hours') }} {{ labelInLang('teachers') }} {{ labelInLang('rhythm') }}
{{ item._id }} ({{ item.term }}) {{ item.title }}
{{ 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 }}
{{ 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, opens an external URL in a new window

There will be 7 exercise sheets on the topics of the lecture. The exercise preliminary meeting will take place on Wednesday, 09 March 2022 during the lecture. The first exercise session with the issue of the first exercise sheet on Wednesday, 16 March 2022.

510.211   UE Algorithms and Data Structures

1 UE

Feichtinger

MI 12:00-12:45

Room: BA 9909

Start: 09.03.2022, preliminary discussion on 09.03.22 in the context of the first VL

510.214   UE Algorithms and Data Structures

1 UE

Feichtinger

MI 12:45-13:30

Room: BA 9909

Start: 09.03.2022, preliminary discussion on 09.03.22 in the context of the first VL

510.215   UE Algorithms and Data Structures

1 UE

Feichtinger

MI 13:45-14:30

Room: HF 9904

Start: 09.03.2022, preliminary discussion on 09.03.22 in the context of the first VL

510.216   UE Algorithms and Data Structures

1 UE

Bertram

MI 14:30-15:15

Room: HF 9904

Start: 09.03.2022, preliminary discussion on 09.03.22 in the context of the first VL

 

Exercise mode

  • The exercise will be held in presence (depending on regulations this could still change to hybrid/digital)
  • Weekly exercises (with exceptions at easter and for the Upper Austrian Holiday)
  • Discussion of open questions/sample solutions
  • Illustration of the exercises by examples
  • Presentation of the current task
  • No compulsory attendance

Exercise submission

  • Electronic exercise submission in Moodle course, opens an external URL in a new window
  • At least 14 days processing time
  • Submission every Wednesday at 23:59:00 CEST (hard deadline!).
  • 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:
    algo_ue[#]_[student ID].zip (Example: algo_ue02_01255105.zip)
  • Only hand in the provided Java classes
  • The defined interfaces must not be changed!
  • Format your source code!
  • Only single papers will be accepted. Detected plagiarism will be punished. Changing variable names or similar does not prevent plagiarism! In case of suspected plagiarism all involved exercises will be graded with 0 points!

Grading

  • A total of 7 exercise sheets, each with different tasks related to the lecture.
  • Up to 36 points can be earned in each exercise.
  • The sum of the 6 best exercises determines the grade.
  • The 6 best exercises of the 7 exercises will be included in the grade.
  • Exercises not handed in will be graded with 0 points.

Grades

Grade

Minimum

Maximum

Sehr gut (very good)

>=189

<=216

Gut (good)

>=162

<189

Befriedigend (satisfactory)

>=135

<162

Genügend (adequate)

>=108

<135

Nicht Genügend (unsatisfatory)

0

<108

 

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 }}
{{ 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 }}
{{ 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 }}