This page contains the source files of most of the beamer
presentations used in my lectures for the
Algorithms and Data Structures
and Computer Networking classes I
teach at the Univesity of Lugano. These source files have been
authored by me, and are
available on-line in the hope that they will be useful to others. In
particular, I have been asked to share these source files to exemplify
the use of PsTricks macros
to create graphs and schematic diagrams. I also hope that readers
would point out errors and offer constructive suggestions for both
content and form.
All the documents except for some pictures are Copyright ©
2005-2015 Antonio Carzaniga.
Permission is granted to copy, distribute and/or modify these
documents under the terms of the GNU Free Documentation License,
Version 1.3 or any later version published by the Free Software
Foundation; with no Invariant Sections, no Front-Cover Texts and no
Back-Cover Texts. A copy of the license is
available here. Please, send comments,
suggestions, or complaints about this document to the author by e-mail
All the presentations are typeset with the LaTeX system. So, you
obviously need a relatively recent verions of the TeX/LaTeX system.
In particular, you also need the following packages and style files:
Some of these presentations also need additional files (e.g., images).
I apologize but I have not had the time to make them available on this
page. Also, notice that some of the fonts used to generate some of
the presentations may not be available on your system. Therefore the
presentations you typeset may look a bit different from the ones you
Lectures from Algorithms and Data Structures
The following lectures are based on the
book Introduction to
, by Thomas H. Cormen, Charles
E. Leiserson, Ronald L. Rivest, and Clifford Stein.
Course introduction: course organization and
policies; Example of the Fibonacci sequence: a bad algorithm and a
good algorithm; implementation-independent behaviors and
Complexity under the RAM model.
Asymptotic growth of functions: big-O, Omega, and Theta notations.
Representing numbers: space
complexity. Adding and multiplying numbers. The simple algorithms
and their analysis. Initial idea for a better multiplication
Basic elements for the
analysis of algorithms: complexity and correctness of
insertion-sort; worst-, best-, and average-case complexity; loop
Divide and conquer strategy:
binary search, merge, merge sort, recursive multiplication, median
and k-smallest selection.
General divide and conquer
strategy and complexity: recurrences.
Quick-sort. Heaps and heap-sort.
Elementary data structures
and hash tables.
Binary search trees.
Randomized binary search trees.
Radix-search. Tries, and ternary
- redblack Red-Black trees. Introduction.
Red-black trees: deletion.
B-Trees. Data structures in
secondary storage: modeling disk access. Structure, search, and
insertion in B-trees.
Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm.
Graphs: representation and
Minimal spanning trees.
Greedy algorithms: general
strategy, Huffman codes.
Dynamic programming: examples,
and general strategy.
Randomized Algorithms: randomized
variants of already-seen deterministic algorithms, Monte Carlo and
Las Vegas algorithms, examples.
Primality testing with basic
elements of modular arithmetic.
Basic elements of complexity
theory: polynomial-time algorithms and problems; the P complexity
class; the NP class; polynomial-time reduction and
Lectures from Computer Networking
The following lectures are based on the
Networking: A Top-Down Approach
, by James F. Kurose and Keith
W. Ross (Addison-Wesley).
- Intro: Course introduction: course
organization and policies; a quick one-hour tour of the course
program through an example using the Web.
Just do the right thing!
Basics of computer
networking: what is a protocol; circuit-switched
vs. packet-switched networks; datagram service; high-level
architecture of the Internet; layered protocol architecture;
Basic quantitative analysis of
network communication: Delay and Throughput.
Basics concepts for network
applications: client/server roles. The world-wide web. Basics of
the HTTP protocol: message formats for requests and replies.
The HTTP Protocol: message
formats, methods, status codes, web caching, sessions and cookies.
Domain Name System: IP addresses
vs. names; architecture and features of DNS; caching; DNS records,
queries, and message formats; examples.
Electronic Mail: basic concepts;
message formats; transport protocol (SMTP); MIME format.
Peer-to-peer systems: benefits of
peer-to-peer file transfer; basic notions on BitTorrent and search
in peer-to-peer systems.
Transport Layer: basic concepts;
multiplexing/demultiplexing; UDP message format; UDP features.
Finite-state machines; Reliable
transfer: basic concepts; a simple reliable data transfer
protocol; checksums, ACKs/NACKs, and sequence numbers.
Quantitative characterization of
network connections: latency, bandwidth, and link capacity;
Reliable transfer: performance of the stop-and-wait protocol,
pipelining, sliding window, go-back-n, selective repeat.
TCP: basic concepts, segment format,
sequence numbers and acknowledgment numbers, RTT estimation,
reliable transfer in TCP, connection setup and .
Congestion control: basic
characterization of congestion in networks; congestion control in
TCP: congestion window, congestion avoidance, slow start, reaction
to timeout events, and fast recovery.
Introduction to the network layer:
Forwarding and routing. Router architecture: functional view,
implementation view, switch fabric, queuing. Internet network
layer: IPv4 datagram format, and fragmentation.
IPv4 addressing: (sub)network
addresses, prefixes and masks, classless interdomain routing,
address-block allocation, and longest-prefix matching. IPv6:
motivation, datagram format, primary design goals and features,
extensions and options
Routing: graph model and high-level
routing strategies. Link-state routing: principles, broadcast
routing, Dijkstra's algorithm.
Distance-vector routing: principles,
routing algorithm, comparison with link-state routing, examples.
Inter-domain routing and BGP:
autonomous systems, hierarchical routing, basic concepts in BGP,
path-vector routing, high-level route selection algorithm and
Basic elements of communication
security: models and goals, privacy and integrity; cryptographic
primitives and modes of operation.