263-4500-00L  Advanced Algorithms

SemesterAutumn Semester 2017
LecturersM. Ghaffari
Periodicityyearly recurring course
Language of instructionEnglish



Courses

NumberTitleHoursLecturers
263-4500-00 VAdvanced Algorithms2 hrs
Tue10:15-12:00CAB G 52 »
M. Ghaffari
263-4500-00 UAdvanced Algorithms2 hrs
Fri10:15-12:00CAB G 59 »
M. Ghaffari
263-4500-00 AAdvanced Algorithms1 hrsM. Ghaffari

Catalogue data

AbstractThis is an advanced course on the design and analysis of algorithms, covering a range of topics and techniques not studied in typical introductory courses on algorithms.
ObjectiveThis course is intended to familiarize students with (some of) the main tools and techniques developed over the last 15-20 years in algorithm design, which are by now among the key ingredients used in developing efficient algorithms.
Contentthe lectures will cover a range of topics, including the following: graph sparsifications while preserving cuts or distances, various approximation algorithms techniques and concepts, metric embeddings and probabilistic tree embeddings, online algorithms, multiplicative weight updates, streaming algorithms, sketching algorithms, and a bried glance at MapReduce algorithms.
Prerequisites / NoticeThis course is designed for masters and doctoral students and it especially targets those interested in theoretical computer science, but it should also be accessible to last-year bachelor students.

Sufficient comfort with both (A) Algorithm Design & Analysis and (B) Probability & Concentrations. E.g., having passed the course Algorithms, Probability, and Computing (APC) is highly recommended, though not required formally. If you are not sure whether you're ready for this class or not, please consulte the instructor.

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits6 credits
ExaminersM. Ghaffari
Typeend-of-semester examination
Language of examinationEnglish
RepetitionThe performance assessment is only offered at the end after the course unit. Repetition only possible after re-enrolling.
Additional information on mode of examinationExercises 30% to the final grade: We will hand out a specially marked exercise, whose solution (typeset in LaTeX or similar) is due two weeks later. These solutions will be graded; the grades will each account for 10% of the final grade.

End of term: a written exam (180 min) accounting for 70% of the grade; open book exam: you are permitted to consult any books, handouts, and personal notes. The use of electronic devices is not allowed.

Learning materials

 
Main linkInformation
Only public learning materials are listed.

Groups

No information on groups available.

Restrictions

There are no additional restrictions for the registration.

Offered in

ProgrammeSectionType
CAS in Computer ScienceFocus Courses and ElectivesWInformation
Doctoral Dep. of Information Technology and Electrical EngineeringDoctoral and Post-Doctoral CoursesWInformation
Computer Science MasterFocus Elective Courses General StudiesWInformation
Computer Science MasterFocus Elective Courses Theoretical Computer ScienceWInformation
Mathematics BachelorAuswahl: Theoretical Computer ScienceWInformation
Mathematics MasterAuswahl: Theoretical Computer Science, Discrete MathematicsWInformation