Your peers in the course CS 550 Algorithmik I at the Universität Mannheim create and share summaries, flashcards, study plans and other learning materials with the intelligent StudySmarter learning app.

Get started now!

CS 550 Algorithmik I

How to handle multiplicativ constants and additive low order terms?

- neglect
- because of the asymptotic growth order notion of functions

CS 550 Algorithmik I

Which growth order terms fulfill transitivity?

all growth order terms

CS 550 Algorithmik I

What is the relationship between exponential functions with different bases.

- Function with higher bases grow asymptotically strictly faster

CS 550 Algorithmik I

Find the shortest path between vertex E to vertex H using the Bellman-Ford algorithm.

- Execute the Bellman-Ford algorithm with source E
- Check the resulting path for H and the distance H.d for the result

CS 550 Algorithmik I

Given a convex set and a linear target function, what do we know about the local (global) maximum (minimum)?

- each local minimum (maximum) of X w.r.t c is global minimum (maximum) of X w.r.t c.
- if X has a maximum (minimum( w.r.t. c then it is taken in an extremal point of X

CS 550 Algorithmik I

What do we know about extremal points in the set of feasible solutions?

- a point x in X(I) is an extremal point in X(I) if and only if
- x satisfies a subset of n linearly independent restrictions with equality

CS 550 Algorithmik I

When does a point d fulfill n linear independent restriction in I with equality?

If the slacking extension of d is zero at n linearly independent positions

CS 550 Algorithmik I

When is d in the set of feasible solution X(I)?

If and only if the slacking extensions of d hast only nonnegative components

CS 550 Algorithmik I

When is d an extremal point in X(I)?

If and only if d has only nonnegative components and the slacking extension of d is zero at n linearly independent positions

CS 550 Algorithmik I

Determine all extremal points.

- Check all subsets of N linear independent conditions
- Calculate the values so that they equal their condition
- pay attention to possible faster ways
- if there is only one solution based on linear independence

CS 550 Algorithmik I

Execute the exhaustive search algorithm for a linear program.

- Search all subsets of N variables
- Check if the restriction are linearly independent
- if yes, then compute the value satisfying all relations with equality
- test if this value also fulfills all the other inequalities
- If yes put it in the set of possible maxima Ext
- Choose the optimal point from Ext

CS 550 Algorithmik I

How do the x values change in a Pivot step?

Exchange the x values of position p and q

For your degree program CS 550 Algorithmik I at the Universität Mannheim there are already many courses on StudySmarter, waiting for you to join them. Get access to flashcards, summaries, and much more.

Back to Universität Mannheim overview pageStudySmarter is an intelligent learning tool for students. With StudySmarter you can easily and efficiently create flashcards, summaries, mind maps, study plans and more. Create your own flashcards e.g. for CS 550 Algorithmik I at the Universität Mannheim or access thousands of learning materials created by your fellow students. Whether at your own university or at other universities. Hundreds of thousands of students use StudySmarter to efficiently prepare for their exams. Available on the Web, Android & iOS. It’s completely free.

Best EdTech Startup in Europe