Algorithms and Data Structures - Spring 2023

Instructor: Antonio Carzaniga
Assistants: Thomas Bertini,
Fabio Di Lauro, Bojan Lazarevski,
Shamiek Mangipudi, Claudio Milanesi
Lecture schedule: Tuesday 10:30–12:30, Thursday 10:30–12:30. See the course weekly schedule or the second-semester Bachelor schedule for details and updates
Instructors' Office Hours: by appointment
Assistants' Office Hours: by appointment

Objectives

Algorithms and data structures are fundamental to computer science. 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.

Policies

See this page for assessment criteria and general course policies.

Learning Material and Other Useful Links

• 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. We refer to this textbook as "CLRS" in the reading references below.
• Notes on Elementary Algorithmic Programming in Python (PDF).
• Exercises for Elementary Algorithmic Programming in Python.
• Other programming problems and examples in Python.
• A collection of exam exercises.
• Previous edition - Schedule and class material of the previous edition of the course.

Lectures and Related Material

• An introduction to elementary, algorithmic programming in Python. This topic will be covered over a series of lectures.
  Material: notes, basic exercises, other programming exercises
• Course introduction: course organization and policies; Example of the Fibonacci sequence: a bad algorithm and a good algorithm; implementation-independent behaviors and algorithmic complexity.
  Material: slides used in class
• Complexity under the RAM model. Asymptotic growth of functions: big-O, Omega, and Theta notations.
  Book ref.: CLRS 2.2, 3. Material: slides used in class
• Basic elements for the analysis of algorithms: complexity and correctness of insertion-sort; worst-, best-, and average-case complexity; loop invariants.
  Book ref.: CLRS 2. Material: slides used in class
• Divide and conquer strategy: binary search, merge, merge sort, recursive multiplication, median and k-smallest selection.
  Book ref.: CLRS 9.1, 9.2. Material: slides used in class
• Quick-sort. Heaps and heap-sort.
  Book ref.: CLRS 6.1-4, 7.1-3. Material: slides used in class, quick_sort.py
• Elementary data structures and hash tables.
  Book ref.: CLRS 10, 11-11.2,11.4. Material: slides used in class; examples: stack.py, queue.py, list.py
• Binary search trees. Randomized binary search trees.
  Book ref.: CLRS 12. Material: print_binary_tree.py, bst.py, slides used in class
• Review or binary trees. Height of a BST in the average case: simulation and visualization.
• Red-Black trees: introduction.
  Book ref.: CLRS 13-13.3. Material: slides used in class
• B-Trees. Data structures in secondary storage: modeling disk access. Structure, search, and insertion in B-trees. Relation with red-black trees.
  Book ref.: CLRS 18-18.2. Material: slides used in class
• Graphs: representation and elementary algorithms.
  Book ref.: CLRS 22-22.4. Material: slides used in class; bfs.py; topological_sort.py
• Minimal spanning trees; Disjoint sets.
  Book ref.: CLRS 23. Material: slides used in class; prim.py, graph1.txt, graph2.txt
• Dijkstra's Algorithm.
  Book ref.: CLRS 24.3. Material: slides used in class; dijkstra.py
• Greedy algorithms: general strategy, activity selection, Huffman codes.
  Book ref.: CLRS 16.2-16.3. Material: slides used in class
• Dynamic programming: examples, and general strategy.
  Book ref.: CLRS 15.3. Material: slides used in class; bellman_ford.py, longest_increasing_subsequence.py, edit_distance.py
• Basic elements of complexity theory: polynomial-time algorithms and problems; the P complexity class; the NP class; polynomial-time reduction and NP-completeness; satisfiability.
  Book ref.: CLRS 34. Material: slides used in cleass