MM851: Algorithms and Probability
Comment
Entry requirements
Academic preconditions
Students taking the course are expected to:
- Have knowledge of basic datastructures
- Have knowledge of basic algorithms for manipulating (representations of) sets of numbers and graphs as well as implementations of such in an imperative programming language.
- Be able to use basic mathematical argumentation, including proof by induction, proof by contradiction and logic expressions
- Know about convergence of power series
Course introduction
- Give the competence to develop and analyse algorithms based on methods from combinatorics and discrete probability
- Give the competence to apply combinatorial arguments as well as discrete probability in connection with development and analysis of algorithms and data structures
- Give knowledge and understanding of the probabilistic method
- Give an understanding of how to apply methods from combinatorics and randomisation in the design and analysis of algorithms with good expected running time/performanc
- Give knowledge of randomised design of algorithms and the use of elementary probability theory to analyse the running time of algorithms
- Give competencies in developing new variants of key algorithms and data structures in the field of computer science
Expected learning outcome
- Apply the counting techniques from the course to determine the cardinality of a set
- Apply the topics on discrete probability from the course to, among other things, central probability distributions as well as to estimate the expected running time of algorithms
- Solve linear recurrence relations
- Develop and analyse basic randomized algorithms based on topics from the course
- Apply techniques from universal hashing to choose hash functions with good expected performance
- Apply algorithms from the course to find occurrences of a given text string in a text
- Construct a finite automaton corresponding to the string matching problem for a given text pattern.
- Formulate a flowmodel for problems that resemble those covered in the course
Content
- Combinatorics
- Counting techniques including, permutations, combinations, binomial coefficients, distributing objects in boxes and the inclusion-exclusion principle
- Linear recurrence equations
- Discrete probability and discrete probability distributions
- Randomized algorithms
- Probabilistic analysis of algorithms
- The probabilistic method
- Universal hashing
- String matching
- Flows in networks
Literature
Examination regulations
Exam element a)
Timing
Tests
Oral examination
EKA
Assessment
Grading
Identification
Language
Examination aids
ECTS value
Additional information
Oral exam as well as a number of assignments handed in during the course. The grade is based on an overall impression of the elements included in the evaluation. Assignments, along with selected topics from the course, form the basis for the oral exam. The external examiner will have the opportunity to see the answers to the assignments.
The re-examination is an oral examination assessed by the grade according to the 7-point grading scale and external co-examination.
Indicative number of lessons
Teaching Method
At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.
- Intro phase: 40 hours
- training phase: 30 hours
Note that part of the lectures will be given as video lectures. The participants will watch these and prepare themselves for dicussion about the topics in class.
Activities during the study phase:
- Self study of the teaching materials
- Solving weekly assignments in order to discuss these at the tutorials
- Written assignments as part of the exam
- Selfguided follow up on the intro and tutorial classes
- Repetition for the exam