CS-250 / 8 credits

Teacher(s): Chiesa Alessandro, Svensson Ola Nils Anders

Language: English

## Summary

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.

## Content

Mathematical Induction

• Mathematical background, Euler's formula for trees.

Analysis of Algorithms

• O-notation, time and space complexity, recurrence relations, probabilistic analysis.

Data structures

• Arrays, linkes lists, trees, heaps, hashing, graphs.

Design of algorithms by induction

• Divide-and-conquer algorithms, dynamic programming.

Greedy Algorithms

• Spanning tree and shortest path algorithms.

Sorting and searching

• merge sort, bucket sort, quicksort, heapsort, binary search.

Graphs algorithms and data structures

• Graphs traversals, shortes path, spanning trees, transitive closures, decompositions, matching, network flows.

## Keywords

Algoriths, data structures, efficiency, problem solving

## Learning Outcomes

By the end of the course, the student must be able to:

• Illustrate the execution of algorithms on example inputs
• Describe basic data structures such as arrays, lists, stacks, queues, binary, search trees, heapas, and hash tables
• Analyze algorithm efficiency
• Compare alternative algorithms and data structures with respect to efficiency
• Choose which algorithm or data structure to use in different scenarios
• Use algorithms and data structures taught in the course on concrete problem instances
• Design new algorithms and data structures bases on known methods
• Prove the corrrectness of an algorithm

## Teaching methods

Ex cathedra lecture, exercises in classroom

## Assessment methods

Continous assessment with final exam.

## In the programs

• Semester: Spring
• Exam form: Written (summer session)
• Subject examined: Algorithms I
• Lecture: 4 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: mandatory
• Semester: Spring
• Exam form: Written (summer session)
• Subject examined: Algorithms I
• Lecture: 4 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Spring
• Exam form: Written (summer session)
• Subject examined: Algorithms I
• Lecture: 4 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Spring
• Exam form: Written (summer session)
• Subject examined: Algorithms I
• Lecture: 4 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: mandatory
• Semester: Spring
• Exam form: Written (summer session)
• Subject examined: Algorithms I
• Lecture: 4 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Spring
• Exam form: Written (summer session)
• Subject examined: Algorithms I
• Lecture: 4 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: mandatory
• Semester: Spring
• Exam form: Written (summer session)
• Subject examined: Algorithms I
• Lecture: 4 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Spring
• Exam form: Written (summer session)
• Subject examined: Algorithms I
• Lecture: 4 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Spring
• Exam form: Written (summer session)
• Subject examined: Algorithms I
• Lecture: 4 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Spring
• Exam form: Written (summer session)
• Subject examined: Algorithms I
• Lecture: 4 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional
• Semester: Spring
• Exam form: Written (summer session)
• Subject examined: Algorithms I
• Lecture: 4 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional

## Related courses

Results from graphsearch.epfl.ch.