Algorithms and Data Structures - Spring 2018

Instructor: Antonio Carzaniga
Assistants: Marcel Bezdrighin, Ali Fattaholmanan Najafabadi, Ioannis Mantas
Type of course: lecture
Lecture Hours: Tuesday 8:30–10:30 in SI-003, Thursday 8:30–10:30 in SI-003
Instructors' Office Hours: by appointment
Assistants' Office Hours: by appointment

Objectives

Algorithms and data structures are fundamental to computer science, as they are the essence of computer programs. Also, the performance of any software system depends on the efficiency of its algorithms and data structures. Designing and analyzing algorithms is therefore crucial for the development of software systems. More generally, the study of algorithms provides insight into the nature of problems and their possible solutions, independent of programming language, programming paradigm, computer hardware, or any other implementation aspect. The objective of this course is to provide students with the knowledge and skills necessary to design and reason about algorithms, and to understand some of the most fundamental algorithms and data structures, their strengths and weaknesses, and their suitability in common contexts.

Contents

The course will cover basic notions of complexity, including asymptotic analysis of worst-case and average complexity, big-O, little-o, omega, and theta notation, polynomial reductions, poly-time verification vs. solution, NP and P complexity classes; general algorithm strategies such as brute force, greedy, divide-and-conquer, and dynamic programming; common algorithms, including elementary numeric computations, searching and sorting, elementary graph algorithms, and string matching; basic data structures, including stacks, queues, linked lists, and rooted trees; more advanced data structures, including B-trees, heaps, hash tables, and structures representing disjoint sets and dictionaries.

Textbook

• Introduction to Algorithms (Third Edition), by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, published by MIT Press and McGraw-Hill.

Links

Additional information is available through the following links and pages.

• A collection of exercises.
• A collection of programming problems and examples in Python.
• Policies - including evaluation criteria and communications.
• Program - detailed course program.
• Schedule - including actual class schedule, topics, assignments, and links to additional course material.
• Announcements - all communications will be posted on this page.
• Previous edition - Schedule and class material of the previous edition of the course.