Algorithms and Data Structures - Spring 2022
announcements
Apr 26: How many countries can you walk to starting from Switzerland?
What is the least number of land borders you have to cross to go from South Africa to Switzerland?
Answer these questions by writing two python programs that read the
list of land border between countries from
this
text file> (encoded in an intuitive way).
Apr 26: The following are good exercises about
binary search trees, taken as usual from
the
collection
of exam exercises (Edition 2.11): 200, 95, 96, 81, 195. You might
want to work these out and discuss your solutions in Thursday's
exercise session (April 28).
Mar 23: The midterm exam is scheduled for Thursday
7 April from 14:30 to 16:30.
Mar 23: The following are good exercises for
the midterm exam, taken as usual from
the
collection
of exam exercises (Edition 2.11): 100, 101, 102, 103, 105, 114,
115, 116, 117, 118, 122, 125, 126, 129, 130, 135, 142, 144, 145, 149,
150, 152, 154, 156, 161, 162, 164, 165, 177, 178, 179, 180, 181, 182,
183, 184, 187, 190, 192, 194, 196, 197, 199, 204, 207, 210, 211, 212,
213, 214.
Have at it!
Mar 23: Room C1.04 (the usual classroom) is reserved for
exercise sessions for the Thursday 14:30-16:30 slot for the rest of
the semester. We will use this time and space to work, individually,
in groups, and all together, on algorithmic programming and exercises.
The first exercise session will be held next week, on Thursday 31
March. We will work on exercises 100, 101, 102, 103, 105 from
the
collection
of exam exercises.
Attendance is not at all required, although I encourage everyone to
participate.
Mar 10: There will be an exercise session during next
week's Tuesday class (15 March). You should prepare by solving the
following exercises on your own before Tuesday:
- Horizontal Histogram
from this
list of Python programming exercises.
- Vertical Histogram from this list of Python programming exercises.
- Compression of a Sequence from this list of Python programming exercises.
- Exercise n. 172 from this collection of exam exercises.
Mar 2: Unfortunately, I have to cancel tomorrow's class
(Thursday, 3 March). I prepared three
simple
programmig exercises in
Python. You should use the two hours of class time to practice with
those. We will discuss the solutions in class next week.
Feb 22: Welcome to Algorithms and Data Structures!
Instructor:
Antonio Carzaniga
Assistants:
Dylan Robert Ashley,
Aditya Ramesh,
Morteza Rezaalipour.
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.
Textbook
Useful Links
Additional information is available through the following links and
pages.
Lectures and Material
-
Course introduction: course organization and policies; Example of
the Fibonacci sequence: a bad algorithm and a good algorithm;
implementation-independent behaviors and algorithmic complexity.
-
Complexity under the RAM model. Asymptotic growth
of functions: big-O, Omega, and Theta notations.
-
Basic elements for the analysis of algorithms:
complexity and correctness of insertion-sort; worst-, best-, and
average-case complexity; loop invariants.
-
Divide and conquer strategy: binary search, merge,
merge sort, recursive multiplication, median and k-smallest
selection.
-
Quick-sort. Heaps and heap-sort.
-
Elementary data structures and hash tables.
-
Binary search trees. Randomized binary search trees.
-
Review or binary trees. Height of a BST in the
average case: simulation and visualization.
-
Red-Black trees: introduction.
-
B-Trees. Data structures in secondary storage:
modeling disk access. Structure, search, and insertion in
B-trees. Relation with red-black trees.
-
Graphs: representation and elementary algorithms.
-
Minimal spanning trees; Disjoint sets.
-
Dijkstra's Algorithm.
-
Greedy algorithms: general strategy, activity
selection, Huffman codes.
-
Dynamic programming: examples, and general strategy.
The material for the following lectures is from the previous edition
of the course. Lecture material is updated as we progress through the
lectures.
-
Basic elements of complexity theory: polynomial-time
algorithms and problems; the P complexity class; the NP class;
polynomial-time reduction and NP-completeness; satisfiability.
-
Exercises.