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 online 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.
Quick links:
All the documents except for some pictures are Copyright ©
20052015 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 FrontCover Texts and no
BackCover Texts. A copy of the license is
available here. Please, send comments,
suggestions, or complaints about this document to the author by email
at
[email protected].
Requirements
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
find here.
Lectures from Algorithms and Data Structures
The following lectures are based on the
book
Introduction to
Algorithms, by Thomas H. Cormen, Charles
E. Leiserson, Ronald L. Rivest, and Clifford Stein.

intro
Course introduction: course organization and
policies; Example of the Fibonacci sequence: a bad algorithm and a
good algorithm; implementationindependent behaviors and
algorithmic complexity.
 growth
Complexity under the RAM model.
Asymptotic growth of functions: bigO, Omega, and Theta notations.
 arithmetic
Representing numbers: space
complexity. Adding and multiplying numbers. The simple algorithms
and their analysis. Initial idea for a better multiplication
algorithm.
 insertionsort
Basic elements for the
analysis of algorithms: complexity and correctness of
insertionsort; worst, best, and averagecase complexity; loop
invariants.
 divide
Divide and conquer strategy:
binary search, merge, merge sort, recursive multiplication, median
and ksmallest selection.
 recurrence
General divide and conquer
strategy and complexity: recurrences.
 sort
Quicksort. Heaps and heapsort.
 elementary
Elementary data structures
and hash tables.
 binarytree
Binary search trees.
Randomized binary search trees.
 tst
Radixsearch. Tries, and ternary
search tries.
 redblack RedBlack trees. Introduction.
 redblack2
Redblack trees: deletion.
 btrees
BTrees. Data structures in
secondary storage: modeling disk access. Structure, search, and
insertion in Btrees.
 strings
String matching:
KnuthMorrisPratt algorithm, BoyerMoore algorithm.
 graphs
Graphs: representation and
elementary algorithms.
 graphs2
Minimal spanning trees.
 greedy
Greedy algorithms: general
strategy, Huffman codes.
 dynamic
Dynamic programming: examples,
and general strategy.
 dijkstra
Dijkstra's algorithm.
 random
Randomized Algorithms: randomized
variants of alreadyseen deterministic algorithms, Monte Carlo and
Las Vegas algorithms, examples.
 primality
Primality testing with basic
elements of modular arithmetic.
 complexity
Basic elements of complexity
theory: polynomialtime algorithms and problems; the P complexity
class; the NP class; polynomialtime reduction and
NPcompleteness; satisfiability.
Lectures from Computer Networking
The following lectures are based on the
book
Computer
Networking: A TopDown Approach, by James F. Kurose and Keith
W. Ross (AddisonWesley).
 Intro: Course introduction: course
organization and policies; a quick onehour tour of the course
program through an example using the Web.
 ethics
Just do the right thing!
 basic_concepts
Basics of computer
networking: what is a protocol; circuitswitched
vs. packetswitched networks; datagram service; highlevel
architecture of the Internet; layered protocol architecture;
historical perspective.
 quantitative
Basic quantitative analysis of
network communication: Delay and Throughput.
 web
Basics concepts for network
applications: client/server roles. The worldwide web. Basics of
the HTTP protocol: message formats for requests and replies.
Error replies.
 web2
The HTTP Protocol: message
formats, methods, status codes, web caching, sessions and cookies.
 dns
Domain Name System: IP addresses
vs. names; architecture and features of DNS; caching; DNS records,
queries, and message formats; examples.
 email
Electronic Mail: basic concepts;
message formats; transport protocol (SMTP); MIME format.
 p2p
Peertopeer systems: benefits of
peertopeer file transfer; basic notions on BitTorrent and search
in peertopeer systems.
 transport
Transport Layer: basic concepts;
multiplexing/demultiplexing; UDP message format; UDP features.
 reliability
Finitestate machines; Reliable
transfer: basic concepts; a simple reliable data transfer
protocol; checksums, ACKs/NACKs, and sequence numbers.
 reliability2
Quantitative characterization of
network connections: latency, bandwidth, and link capacity;
Reliable transfer: performance of the stopandwait protocol,
pipelining, sliding window, gobackn, selective repeat.
 tcp
TCP: basic concepts, segment format,
sequence numbers and acknowledgment numbers, RTT estimation,
reliable transfer in TCP, connection setup and .
 tcp2
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.
 network
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.
 network3
IPv4 addressing: (sub)network
addresses, prefixes and masks, classless interdomain routing,
addressblock allocation, and longestprefix matching. IPv6:
motivation, datagram format, primary design goals and features,
extensions and options
 routing
Routing: graph model and highlevel
routing strategies. Linkstate routing: principles, broadcast
routing, Dijkstra's algorithm.
 routing2
Distancevector routing: principles,
routing algorithm, comparison with linkstate routing, examples.
 bgp
Interdomain routing and BGP:
autonomous systems, hierarchical routing, basic concepts in BGP,
pathvector routing, highlevel route selection algorithm and
policies.
 security
Basic elements of communication
security: models and goals, privacy and integrity; cryptographic
primitives and modes of operation.