Algorithms and Data Structures (WS15/16) Exercises for Units 14 and 15 Problem 1 Try to get some feel for the behavior of the splay tree data structure. Draw a binary search tree with 5-10 nodes, and work out a few splay

Source URL: www-tcs.cs.uni-sb.de

• Binary trees
• Computing
• Computer programming
• Splay tree
• Software engineering
• Binary search tree
• Tree
• Search tree
• Optimal binary search tree
• Link/cut tree

Algorithms and Data Structures Winter TermExercises for UnitLet R be a set of 2k + 1 red points in the plane and let B be a set of 2k + 1 blue points. Assume that R ∪ B is in non-degenerate position, i.

Source URL: www-tcs.cs.uni-sb.de

Algorithms and Data Structures (WS15/16) Example Solutions for Unit 3 Problem 1 Algorithm: for the simplicity let’s assume that n = 2k, algorithm can be easily modified if n = 2k + 1 by using one additional comparison

Source URL: www-tcs.cs.uni-sb.de

• Analysis of algorithms
• Online algorithms
• Adversary model
• Algorithm
• Mathematics

Algorithms and Data Structures Winter TermExercises for Unit 4 1. Consider the problem Disjointness of testing whether two sets A = {a1 , . . . , an } and B = {b1 , . . . , bn } of real numbers are disjoint.

Source URL: www-tcs.cs.uni-sb.de

• Disjoint sets
• Sine
• Exponential time hypothesis
• Pi

Algorithms and Data Structures Winter TermExercises for Unit 11 s 1. For this question assume we have n buckets, B1 , . . . , Bn , initially empty, and an unlimited

Source URL: www-tcs.cs.uni-sb.de

• Search algorithms
• Hashing
• Cuckoo hashing
• Hash function
• 2-choice hashing
• Locality-sensitive hashing

Algorithms and Data Structures (WS15/16) Example Solutions for Unit 5 Problem 3 We need to prove that f (x) ≥ cxp 1 + Rx

Source URL: www-tcs.cs.uni-sb.de

• Logarithms
• Asymptotic analysis
• Recurrence relations
• AkraBazzi method
• Arithmetic functions

(1-2)分野対応表_ASJ_ASA_TCs_20160528.xlsx

Source URL: www.asj.gr.jp

• Acoustics
• Bioacoustics
• Sound
• Architectural acoustics
• ASA Silver Medal
• Acoustical Society of America

Algorithms and Data Structures Winter TermExercises for Unit 8 s 1. Compute the square of the following polynomial using the Fourier transform method discussed

Source URL: www-tcs.cs.uni-sb.de

• Fourier analysis
• Algebra
• Elementary algebra
• Fourier transform
• Joseph Fourier
• Inequality
• Polynomial
• Multiplication algorithm
• Algebraic number field

Algorithms and Data Structures Winter TermExercises for Units 12 and 13 s 1. If you feel uneasy with treaps, draw a few examples and test insertions and deletions.

Source URL: www-tcs.cs.uni-sb.de

• Binary trees
• Data types
• Treap
• Search algorithms
• Binary search tree
• Lowest common ancestor
• B-tree
• Finger search
• Tree
• Geometry of binary search trees

Algorithms and Data Structures Winter TermExercises for Unit 16 & 17 1. Show the following simple facts about a binomial tree of rank k. a) The tree has 2k nodes.

Source URL: www-tcs.cs.uni-sb.de

• Abstract data types
• Binomial heap
• Fibonacci heap
• Heap
• Amortized analysis
• Queue
• Data structures
• Priority queues
• Weak heap
• Shadow heap