Department of Computer ScienceSchool of Science and Computer EngineeringDepartmental Course Syllabus- Week 1- Weeks 2 -- 5- Weeks 6-7- Weeks 8: Midterm Exam March 7, 2012- Weeks 9 Spring Break, March 10-17, 2012- Week 10- Week 11- Weeks 12-13Department of Computer Science School of Science and Computer Engineering University of Houston Clear Lake Departmental Course Syllabus CSCI 5931 CSCI 5931: Graph Theory and Algorithms (3 credits). Catalog Description: This course covers the fundamental concepts of graph theory that are relevant to computer science in general and to parallel computing in particular. Parallel computations using popular interconnection networks such as arrays, trees, hypercubes, and permutation networks such as the star and the pancake networks are covered. Knowledge of sequential algorithms and the various paradigms in the design of such algorithms is required. Pre-requisites: Advanced Data Structures and Algorithms Course. Audience: This course is designed for students in the graduate program in computer science, computer information systems, computer engineering, computer system engineering. Instructor: Said Bettayeb, Ph.D. Associate Professor (281) 283-3857 Office Hours: Mond. 5:00 - 7:00 p.m. and Tues. 5:00 - 700 p.m. Or by Appointment Course Requirement: • Academic Requirements: 1. Assigned reading (journal articles, selection from books). . 2. Four Homework Assignments: 3. Project: One.4. Midterm examination March 7, 2012 • Administrative Requirements: University regulations governing class attendance will be strictly observed. Evaluation of Student Performance: • Project Presentation: April 24-May 2, 2012 • Homework: late homework or project will be accepted with a 10% penalty for every missed day • Midterm Exam: 30% • Homework: 20% • Project 50% Grading Scale: 92------100 A 87 ---- 91 A- 84 ------86 B+ 80----83 B 76-----79 B- 72------25 C+ 68-----71 C 64-----67 C- 59------63 D+ 54----58 D 49-----53 D- 58 and Below F Readings: Required Textbook: Author: Leighton, Thomson, Title: Introduction to Parallel Algorithms and Architectures Publisher: Morgan Kaufman Recommended Readings: Recommended Textbook: Author: Chartrand & Lesniak Title: Graphs & Digraphs Edition: 4th Publisher: Chapman & Hall/CRC Dr. Bettayeb’s research papers. Research papers: Prominent Researchers in the Field such as A. Rosenberg, T. Leighton, S. Bhatt, H. Sudborough, A. Zomoya, B. Monien Instructor Emphasis Study of the structures and properties of graphs such as vertex transitivity, genus, diameter and bisection. The class will cover graph algorithms, and computationalgeometry, and study how the algorithms can be used in practice for various applications in graphics, computer vision, and scientific simulation. Course Goals and Objectives/Learning Outcomes: This course prepares students to • Learn the fundamental concepts of graph theory such as degree sequences, cut vertices, automorphism, diameter, bisection, planarity, genus, Hamiltonian graphs, Eulerian graphs, • Design efficient embeddings of interconnection networks, • Determine the efficiency of parallel machines by studying their underlying interconnection networks properties such as the bisection which measure the communication congestion, the diameter which measure communication delay, the genus which indicates the feasibility of such a machine. Objectives: In this course, the student will learn the following material: 1. The fundamental concepts of Graph Theory such as degree sequences, paths and cycles, cut vertices, bridges, and blocks. 2. How to design efficient solutions to problems that can be modeled by graphs. 3. Graph embeddings: Eurler’s formula, planar graphs, the genus of a graph. 4. More about NP completeness: Hamiltonian Graphs, Travelsalesman. 5. Graphs and groups: The group and Edge Group of a graph, Cayley Color Graphs 6. Graph Coloring. Course Content and Schedule: • Week 1 Introduction to Graphs and Digraphs: Graphs, degree sequences, distances, digraphs, multigraphs • Weeks 2 -- 5 Structure of Graphs: Cut vertices, bridges, and blocks Automorphism group of a graph Cayley color graphs Eulerian and Hamiltonian Graphs Planar Graphs• Weeks 6-7 Graph Embeddings: The genus of a graph 2-cell embedding Arrays and Trees: • Elementary sorting and counting on a linear array • Integer Arithmetic • Matrix Algorithms • Graph Algorithms: Transitive Closure, Connected Components, Shortest Paths, Breadth First Spanning Trees, • Weeks 8: Midterm Exam March 7, 2012 • Weeks 9 Spring Break, March 10-17, 2012 • Week 10 Meshes of Trees: (a) Graph Algorithms Revisited (b) Matrix Algorithms Revisited (c) Integer Arithmetic Revisited. • Week 11 Hypercubes and Related Networks (a) The Hypercube (b) The butterfly, cube connected cycles (c) The Shuffle Exchange and the De Bruijn graphs (d) Packet Routing Algorithms • Weeks 12-13 (a) Sorting: Odd-Even Merge Sort (b) The Fast Fourier Transform • Weeks 14-15 Final Project
View Full Document
Unlocking...