Syllabus
ECEN 689 – Algorithmic Foundations of Networking
Instructor: Alex Sprintson
Website: http://cegroup.ece.tamu.edu/spalex/algfound
Credit: 3
Term: Fall 2008
Meeting times and location: To be determined.
Course description and prerequisites:
The course will provide fundamental and in-depth knowledge of the rapidly evolving area of network algorithms. We will study the theoretical foundations as well as efficient methods for algorithm design that apply to various areas of networking. We will discuss unique properties of networking algorithms and show specific examples of algorithm design. The course will provide the students with powerful algorithmic tools and enable them to pursue research in the related areas.
Prerequisite: Graduate standing or instructor consent.
Learning outcomes:
At the end of this course, the students will:
1. Be able to apply the techniques of linear and integer programming for solving network optimization problems;
2. Be able to design approximation algorithms for NP-hard problems;
3. Understand the technique of network flows and its applications in various areas of networking;
4. Be familiar with state-of-the-art routing algorithms (including Quality of Service routing)
5. Be able to solve network reliability problems
6. Be familiar with the randomization technique and its applications in algorithm design.
7. Be able to solve basic facility location and scheduling problems.
Instructor information
• Name: Dr. Alex Sprintson, Assistant Professor, Department of Electrical and Computer Engineering, Texas A&M University.
• Phone number (979) 458 0092
• Email address: spalex@tamu.edu
• Office hours: To be determined
• Office location: 332D WERC
Textbook and/or resource materials:
No textbook will be required. The instructor will provide course notes and research papers.
Recommended books:
George Varhese: Network Algorithmic
Grading policies:
Method of evaluation: In this course, homework assignments, quizzes, projects, and student presentations, will be used for evaluation of your performance.
Presentations 10 %
Assignments 40 %
Project 30%
Quizzes 20 %
Total 100 %
Mandatory homework problems and lists of suggested problems will be assigned in class every two weeks. Homework turned in late will be assigned a late penalty.
Course Topics
1. Introduction to network algorithms. Data structures, Performance metrics and evaluation, Complexity and approximations, Heuristics, Shortest path algorithms
2. Network optimization and Linear Programming (LP). Basics of LP, LP duality, primal –dual algorithms, applications for network optimization.
3. Network Flows. Theory of network flows, disjoint path algorithms, Maximum flow algorithms, Min-cost flow algorithms.
4. Facility location algorithms. Location problems, Center problems, Median problems.
5. Multicommodity flow algorithms
6. Steiner tree algorithms
7. Traveling Salesman Problem
8. Routing algorithms. Quality of Service routing, Restricted shortest path algorithms.
9. Network design problems. Steiner networks, LP-relaxation and half-integrality
10. Network Reliability problems. Cut Enumeration, Counting problems
11. Connectivity augmentation
12. On-line algorithms. Competitive analysis
13. Scheduling algorithms
Other pertinent course information.
Contribution to Professional Component:
1. Prepares students to design algorithms for fundamental network design and routing problems.
2. Prepares students to read and understand current literature on network algorithms.
3. Develops problem solving skills
4. Prepares students for research in various areas of networking
Homework:
Developing good algorithmic skills and algorithm analysis techniques requires substantial practice. Therefore, mandatory homework problems and lists of suggested problems will be assigned in class every two weeks.
Format
− Solutions must be typed using Microsoft word or Latex software. A Latex template will be provided on the course website.
− Each page should have the page number, as well as the total number of pages, in the upper right-hand corner.
− The first page should have the assignment number in the center at the top of the page.
− All solutions should include all of the steps for full credit.
− Staple together all pages.
− All homework must be submitted by email to spalex@tamu.edu
− All homework assignments are due at the beginning of class on the date assigned. A valid university approved excuse or prior consent from the instructor are required for late assignments.
Quizzes:
Random quizzes will be given in class. In-class quizzes on a given subject may be given before the due date of homework covering that subject.
Americans with Disabilities Act (ADA) policy statement
The Americans with Disabilities Act (ADA) is a federal anti-discrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact the Department of Student Life, Services for Students with Disabilities, in Cain Hall or call 845-1637. For additional information visit http://disability.tamu.edu
Academic Integrity Statement and Policy
“An Aggie does not lie, cheat or steal nor tolerate those who do.” Every student is expected to adhere to this code, violation can result in disciplinary action (e.g., a zero in the assignment, a failing grade for the class, and/or noted on student disciplinary records). All work submitted in this course must be your own work, produced exclusively for this course. More information about Honor Council Rules and Procedures can be found at http://www.tamu.edu/aggiehonor.