Course Syllabus Page 1 Course Syllabus Course Information CS6385 Algorithmic Aspects of Telecommunication Networks, Section 001 Cross listed as TE 6385. Fall Semester, 2014 Professor Contact Information Name: Dr. Andras Farago, Professor Department: Computer Science Office: ECS 4.204 Office hours: Friday 8:00-10:00am Phone: 972-883-6885 E-mail: [email protected] Mail Station: EC31 Teaching Assistant: When TA is assigned, will be posted under “Announcements” at the course website in e-Learning. Catalog Pre-requisites for the course: CS 5343 Algorithm Analysis & Data Structures CS 5348 Operating Systems Concepts TE 3341 Probability Theory and Statistics or equivalents. Course Description Purpose and content of the course: The purpose of the course is to make students familiar with fundamental methods in the design and analysis of telecommunication networks. The main emphasis is on the methodology that remains valid on the long term and does not depend strongly on frequently changing applications. Outline of topics to be addressed: introduction to the network planning problem; mathematical programming for planning; network algorithms for planning; elements of network reliability; optimization for network design; network data analysis; selected topics form link level and network level traffic modeling and analysis for traffic engineering.Course Syllabus Page 2 More detailed topic list Note: The list is tentative, some topics may be skipped, new ones may be added. - Fundamental concepts of network planning; Typical problems and issues in network design; Analysis vs. synthesis; Reasons for hardness in network planning; Decomposition approach to mitigate hardness; Pathways to optimum design: exact, approximate, heuristic. - Optimization in network design; Linear Programming: formulation, solution principles, duality, network planning related applications; Integer Linear Programming: formulation, methods for linearizing non-linear integer programs, solution principles, exact and heuristic algorithms for integer programs, network design related applications. - Graph algorithms for network design; maximum flow; minimum cost flow; multicommodity flow; flow based network design; network vulnerability analysis via graph connectivity; structure of optimally connected graphs under uniform costs, various theorems and algorithms related to graph connectivity; Karger's randomized contraction algorithm for minimum cut, Nagamochi-Ibaraki minimum cut algorithm. Outlook to recent new results. - Algorithms and models for reliability analysis; Reliability concepts; Basic reliability configurations; More complex reliability configurations; Algorithms to compute exact and approximate network realibity; Lifetime measures; Computing network lifetime measures in various settings. - Traffic analysis for network planning; Integrating flow and queuing models in network planning to capture traffic considerations; Link capacity dimensioning for given flow and network topology; Flow routing for given topology and link capacities; Combined capacity and flow assignment when only the network topology and the traffic demand is given; Heuristic methods for optimizing capacities, flow routing, and network topology together, when only the traffic matrix is known; Blocking probability models at the link level, and at the network level; Reduced load approximation and the Erlang fixed point equations (optional). Learning objectives Outcomes (see explanation under the table) Fundamental concepts of network planning b,c Optimization in network design a,b,c,d,e Graph algorithms for network design a,b,c,e Algorithms and models for reliability analysis a,b,c,e Traffic analysis for network planning a,b,c Outcomes a. an ability to understand advanced concepts in theory of computer science; b. an ability to understand advanced concepts in applications of computer science;Course Syllabus Page 3 Student Learning Objectives/Outcomes Required text: Lecture notes written by the instructor. They are available online at the course website in eLearning. The lecture notes may be updated during the semester. ______________________________________________________________________________ Assignments & Academic Calendar 3 or 4 programming projects and one exam. Due dates of projects: will be announced and posted in eLearning. Exam date: Wednesday, December 10, 2014. Grading Policy Item Weight Project average 66% Exam 34 % The weights and the number of projects may be changed at the professor’s discretion. Bonus points may be assigned for outstanding performance. Course & Instructor Policies Course website: Project submissions will be done via the course website in eLearning Announcements, deadlines, and any other course related information will also be posted there. Check the course website regularly. E-mail notifications will also be sent from eLearning. According to UTD e-mail policy, please do not use private e-mail addresses (such as yahoo, gmail, etc.) for course related correspondence. It is your responsibility to check your e-mail regularly and to make sure that your mailbox does not run over quota, so that the messages do not bounce. c. an ability to apply knowledge of advanced computer science to formulate and analyze problems in computing and solve them; d. an ability to learn emerging concepts in theory and applications of computer science; and, e. an ability to design and conduct experiments as well as to analyze and interpret data.Course Syllabus Page 4 Late submission policy: Late submissions will receive reduced points. The reduction amount depends on how late the submission is (it can reach 100 % reduction). The only exception is a late submission due to documented
View Full Document