New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Jimmy Hane


Jimmy Hane
Texas A&M
GPA 3.74

Alexander Sprintson

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Alexander Sprintson
Class Notes
25 ?




Popular in Course


This 17 page Class Notes was uploaded by Jimmy Hane on Wednesday October 21, 2015. The Class Notes belongs to ECEN 689 at Texas A&M University taught by Alexander Sprintson in Fall. Since its upload, it has received 39 views. For similar materials see /class/226244/ecen-689-texas-a-m-university in ELECTRICAL AND COMPUTER ENGINEERING at Texas A&M University.




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/21/15
Algorithmic Foundations of Networkin Alex Sprintson Department of Electrical and Computer Engineering Texas AampM Lecture 1 Information 0 Course webpage gt httpcegroupecetamueduspaleXalgfound 0 Office hours gt Tuesday and Thursday 1pm 2pm WERC 332D gt or by appointment spalex tamue u gt Will use official TAMU roster email list Algorithmic Foundations Nelworki Review 0 The course will provide fundamental and in depth knowledge of the rapidly evolving area of network algorithms gt 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 V o The course will provide the students with powerful algorithmic tools and enable them to pursue research in the related areas 9 Prerequisite Graduate standing or instructor consent Alex Srlimson lhmic Foundation Syllabus co 0 At the end of this course the students will V VV V VV Be able to apply the techniques of linear and integer programming for solving network optimization problems Be able to design approximation algorithms for NPhard problems Understand the technique of network flows and its applications in various areas of networking Be familiar with stateof theart routing algorithms including Quality of Service routing Be able to solve network reliability problems Be familiar with the randomization technique and its applications in algorithm design Be able to solve basic facility location and scheduling problems Alex Srlimson lhmic Foundation Syllabus cont a Textbook andor resource materials No textbook will be required The instructor will provide course notes and research papers 0 Grading policies gt Method of evaluation In this course homework assignments quizzes projects and student presentations will be used for evaluation of your performance V Method of evaluation In this course homework assignments quizzes projects and student presentations will be used for evaluation of your performance Presentations 10 at Assignments 40 at Project 30 at Quizzes 20 at Total 100 o 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 39 hmic Founda 39 0 Introduction to network algorithms Data structures Performance metrics and evaluation Complexity and approximations Heuristics Shortest path algorithms Introduction to network algorithms Data structures Performance metrics and evaluation Complexity and approximations Heuristics Shortest path algorithms Network optimization and Linear Programming LP Basics of LP LP duality primal dual algorithms applications for network optimization Network Flows Theory of network flows disjoint path algorithms Maximum flow algorithms Min cost flow algorithms Facility location algorithms Location problems Center problems Median problems Multicommodity flow algorithms Steiner tree algorithms Nelworki Algorithmic Foundations Course topics con 0 Traveling Salesman Problem 0 Routing algorithms Quality of Service routing Restricted shortest path algorithms 0 Network design problems Steiner networks LP relaxation and half integrality 0 Network Reliability problems Cut Enumeration Counting problems 0 Connectivity augmentation 0 On line algorithms Competitive analysis 0 Scheduling algorithms Algorithmic Foundations Nelworki Homework 6 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 0 Format gt V V V VV 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 righthand 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 All homework must be submitted by email to spalex tamuedu 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 lhmic Foundation Alex Srlimson Quizzes 0 Random quizzes will be given in class n cass quizzes on a given subject may be given before the due date of homework covering that subject rilhmic Foundauol oi Nelworkil Algorithm Design 0 Algorithm design is a classical topic gt Covers exact approximation onIine algorithms gt Poses major challenges when tasks have to be performed under stringent conditions 0 Networking provides a rich new context for algorithm design gt Algorithms are used everywhere in networks at at the endhosts for packet transmission in the network switching routing caching etc gt Many new scenarios and very stringent constants gt High speed of operation and largesized systems gt Require new approaches and techniques 39 lunic Founda 39 NP hardness a Most of the problems encountered in communication networks are NP hard 0 An NP optimization problem H is either a minimization or maximization problem such that gt Each valid instance I of H comes with a nonempty set of solutions at Each solution is assigned a nonnegative rational number referred to as its objective value gt There exists a polynomialtime algorithm for determining validity feasibility and objective value 0 A feasible solution is that achieves the optical objective value is referred to as an optimal solution a OPTIIU denotes the value of the optimal solution Alex Srlimson lhmic Foundation 0 Consider the following problem Problem Given an undirected graph CV7 E and a cost function on vertices c V a Q find a minimum cost vertex cover ie a set V Q V such that each edge e E E has at least one endpoint incident at V o The special case in which all vertices are of unit cost will be called the cardinality vertex cover problem Alex Srlimson lhmic Foundation 0 Valid instances consist of an undirected graph CV7 E and a cost function on vertices o A feasible solution is a set 5 Q V that is a cover in G 0 Objective function sum of costs of all vertices in 5 9 Clearly a solution to the Vertex Cover Problem can be verified in polynomial time 0 Finding an optimal solution for Vertex Cover is NP hard Algorithmic Foundations Nelworki Approximation Algorithms a An approximation algorithm A for H produces in polynomial time a feasible solution whose objective value is close to the optimal o By close we mean within a guaranteed factor of the optimal e We show a factor two approximation algorithm for the cardinality vertex cover gt An algorithm that finds a cover of costs g 2 OPT in time polynomial in V Algorithmic Foundations Nelworki Matching Problem 0 Given a graph CV7 E a subset of nodes E Q E is said to be a matching if no two edges in E share an end point a A matching of maximum cardinality in G is called maximum matching 0 A matching that is maximal under inclusion is called a maximal matchin gt A maximal matching can be computed in polynomial times by a greedy algorithm gt Maximum matching can also be solved in polynomial time Alex Srlimson lhmic Foundation Vertex Cover con 0 Observation A maximum matching in G provides a lower bound on the size of vertex cover gt Including maximal matching Algorithm 0 Find a maximal matching in G and output the set of matched vertices Algorithmic Foundations Nelworki Vertex Cover con Theorem The above algorithm is a factor 2 approximation algorithm for the cardinality vertex cover problem Proof 0 No edge can be left uncovered by the set of picked vertices Otherwise an edge would be added to the matching in contradiction to its minimality Let M be the maximum matching picked then lMl g OPT The algorithm has cardinality 2lMl which is at most 2 OPT Alex Srlimson Algorithmic Foundations of Networking


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.