### Create a StudySoup account

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

Already have a StudySoup account? Login here

# SPTPOPTCS FOR HRNSSNG SLR ENR ECEN 689

Texas A&M

GPA 3.74

### View Full Document

## 39

## 0

## Popular in Course

## Popular in ELECTRICAL AND COMPUTER ENGINEERING

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.

## Similar to ECEN 689 at Texas A&M

## Popular in ELECTRICAL AND COMPUTER ENGINEERING

## Reviews for SPTPOPTCS FOR HRNSSNG SLR ENR

### 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

### 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

#### "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."

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

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

#### "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."

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.