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.
Quick links:
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
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; implementation-independent behaviors and
algorithmic complexity.
- growth
Complexity under the RAM model.
Asymptotic growth of functions: big-O, 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
insertion-sort; worst-, best-, and average-case complexity; loop
invariants.
- divide
Divide and conquer strategy:
binary search, merge, merge sort, recursive multiplication, median
and k-smallest selection.
- recurrence
General divide and conquer
strategy and complexity: recurrences.
- sort
Quick-sort. Heaps and heap-sort.
- elementary
Elementary data structures
and hash tables.
- binarytree
Binary search trees.
Randomized binary search trees.
- tst
Radix-search. Tries, and ternary
search tries.
- redblack Red-Black trees. Introduction.
- redblack2
Red-black trees: deletion.
- btrees
B-Trees. Data structures in
secondary storage: modeling disk access. Structure, search, and
insertion in B-trees.
- strings
String matching:
Knuth-Morris-Pratt algorithm, Boyer-Moore 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 already-seen deterministic algorithms, Monte Carlo and
Las Vegas algorithms, examples.
- primality
Primality testing with basic
elements of modular arithmetic.
- complexity
Basic elements of complexity
theory: polynomial-time algorithms and problems; the P complexity
class; the NP class; polynomial-time reduction and
NP-completeness; satisfiability.
Lectures from Computer Networking
The following lectures are based on the
book
Computer
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.
- ethics
Just do the right thing!
- basic_concepts
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;
historical perspective.
- quantitative
Basic quantitative analysis of
network communication: Delay and Throughput.
- web
Basics concepts for network
applications: client/server roles. The world-wide 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
Peer-to-peer systems: benefits of
peer-to-peer file transfer; basic notions on BitTorrent and search
in peer-to-peer systems.
- transport
Transport Layer: basic concepts;
multiplexing/demultiplexing; UDP message format; UDP features.
- reliability
Finite-state 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 stop-and-wait protocol,
pipelining, sliding window, go-back-n, 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,
address-block allocation, and longest-prefix matching. IPv6:
motivation, datagram format, primary design goals and features,
extensions and options
- routing
Routing: graph model and high-level
routing strategies. Link-state routing: principles, broadcast
routing, Dijkstra's algorithm.
- routing2
Distance-vector routing: principles,
routing algorithm, comparison with link-state routing, examples.
- bgp
Inter-domain routing and BGP:
autonomous systems, hierarchical routing, basic concepts in BGP,
path-vector routing, high-level route selection algorithm and
policies.
- security
Basic elements of communication
security: models and goals, privacy and integrity; cryptographic
primitives and modes of operation.