CS CALENDAR	FACULTY OFFICE HOURS	CONTACT US
UCF--> CECS--> Computer Science

Solution to the Data Structures and Algorithms portion of the Spring 1999 Ph.D. Qualifying Examination Qualifying Exam, Phase I The subjects are: Algorithms/Data Structures Architecture Artificial Intelligence Computational Neuroscience Computer Graphics Systems Computer Networks Computer Vision Database Management Systems Digital Media Formal Languages Graph Theory Operating Systems Quantum Computing Parallel and Distributed Computation Performance Modeling Techniques Programming Languages Software Engineering VLSI OPERATING SYSTEMS The students will be tested on the following topics: Process Management and Coordination CPU Scheduling Algorithms The Critical Section Problem Synchronization Hardware Semaphores and Monitors Deadlock Characterization, Detection, Prevention and Avoidance Inter-process Communication Synchronization Hardware Memory Management and Virtual Memory Paging, Segmentation and Paged Segmentation Virtual Memory and Page Replacement Algorithms Thrashing and the Working Set Model Page-Fault Rate: Selection of Page Size and Impact of Program Structure File Systems Access Methods Directory Structures Disk Space Allocation Methods Free Space Management Protection Mechanisms Recommended Text: Operating Systems Concepts by Silberschatz and Galvin. Fifth Edition, Addison Wesley, 1998 ISBN: 0-201-59113-8 Chapters 4, 5, 6, 7, 8, 9, 10, and 11 ALGORITHMS/DATA STRUCTURES Topics: Summation formulas and techniques, recurrences, induction proof, order analysis (big-O notation), searching and sorting procedures, tree structures. Basic algorithm design techniques and their analysis, e.g., divide-and-conquer, greedy, dynamic programming, and implicit and complete enumeration. References: 1. Lewis and Denenberg, Data Structures and Their Algorithms, Harper Collins Publishers, 1991. 2. Graham, Knuth, and Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994. 3. G. Brassard and P. Bratley, Fundamentals of Algorithmics, Prentice Hall, 1996. 4. E. Horowitz and S. Sahni, Fundamentals of Data Structures, Computer Science Press, 1976. 5. D. Stubbs and N. Webre, Data Structures with Abstract Data Types and Pascal, Brooks/Cole, 1984. 6. E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, 1978. GRAPH THEORY Topics: Graphs, digraphs, weighted graphs, and subgraphs; Walks, paths, cycles, cutsets, trees, spanning trees, and Hamiltonian cycles; Planarity, geometric and combinatorial duals, thickness and crossings, and graph drawing and layout; Connectivity and separability. Coloring, coverings, and independence and domination numbers. Matchings, chromatic number. Tournaments. Isomorphism Network flows. Vector spaces and subspaces of a graphs and associated matrices. Counting and enumeration of labeled and unlabeled graphs of various types. Graph algorithms, complexity, data structures, DFS, BFS, and mixed searches. Application of graph theory (e.g., in circuit analysis, switching theory, OR, global program optimization, and in Markov processes). References: 1. F. Harary, GRAPH THEORY, Addison-Wesley, 1969 2. J. A. Bondy and U.S.R. Murthy, GRAPH THEORY WITH APPLICATIONS, North Holland, 1976. 3. N. Deo, GRAPH THEORY WITH APPLICATIONS TO ENGINEERING & COMPUTER SCIENCE, Prentice-Hall, 1974. 4. E. M. Reingold, J. Nievergelt and N. Deo, COMBINATORIAL ALGORITHMS, Prentice-Hall, 1977, Chapter 8. 5. M. M. Syslo, N. Deo, and J. S. Kowalik, DISCRETE OPTIMIZATION ALGORITHMS, Prentice-Hall, 1983, Chapter 3. FORMAL LANGUAGES/AUTOMATA THEORY Topics: The Chomsky Hierarchy of Languages. Regular languages and grammars, DFAs, NFAs, closure properties of regular languages and the pumping lemma for regular languages. Context free grammars, pushdown automata, and the pumping lemma for context free grammars. Basics and constructions of Turing machines. References: 1. Thomas A. Sudkamp, Languages and Machines, An Introduction to the Theory of Computer Science, Chs. 1-10. (Required Reading) 2. Lewis and Papadimitriou, Elements of the Theory of Computation, Ch. 1-4. (Recommended Reading) 3. Hopcroft and Ullman, Introduction to Automata, Theory and Languages, Ch. 1-7. (Recommended Reading) PROGRAMMING LANGUAGES The questions for this exam will cover material that is considered to be undergraduate material in programming languages and systems. There is not necessarily a particular course to point to here that contains all the material, since it is spread across multiple courses. These courses include COP4020 (Programming Languages), COP3402 (Computer Systems Programming), and, to some extent, COP3530 (Computer Science III) and COT4210. Essentially, the areas covered on this portion of the exam include: 1) Use of regular and context free grammars to express the syntax of programming languages, including the use of tools such as Lex and Yacc. 2) Simple parsing strategies, such as recursive descent parsers. 3) The basic structure of a language processing system. 4) The basic language classes (declarative, imperative, functional and object-oriented) and their characteristics. 5) The basic semantic representations (denotational, operational and axiomatic) and their characteristics. 6) Abstract data types. Required Reading List: Concepts of Programming Languages by Robert Sebesta (6th Edition). (There are few differences between the 3rd and 4th edition). Recommended References: Part of the above material is covered in more depth in the following references: 1) lex & yacc by Levine, Mason and Brown. This is an excellent book showing progressively more complex examples of the tools. 2) Compilers -- Principles, Techniques and Tools by Aho, Sethi and Ullman. (also known as the dragon book). This book is the definitive reference on compilers and has very good explanations. For this exam, pay particular attention to all of Chapters 1&2, Sections 3.1-3.5, Sections 4.1-4.4, Sections 5.1-5.2, Sections 6.1-6.3, Section 7.1, Sections 7.5-7.6, Section 8.1 and Sections 9.1-9.3. 3) Languages and Machines, An Introduction to the Theory of Computer Science, by Thomas A. Sudkamp, Chapters 1-8. ARCHITECTURE The students will be tested on the following topics: Performance Analysis Instruction Set Architecture Design Pipelining Memory Hierarchy Instruction-Level Parallelism Exploration Basic Storage Systems Computer Arithmetic Good sources for the above information are: 1. D. A. Patterson and J. L. Hennessy, "Computer Organization & Design: the Hardware / Software Interface", Morgan Kaufmann, 2nd ed. 1998, 3rd ed. 2004. 2. J. L. Henessy and D. A. Patterson, "Computer Architectures: A Quantitative Approach" Morgan Kaufman, 3rd ed. 2003. 3. J. P. Shen and M. H. Lipasti, "Modern Processor Design: Fundamentals of Superscalar processors" McGraw Hill, 2004. Software Engineering Topics: Software Process Models Unified Software Process Spiral Model Use Case Model Analysis Model Design Model Process Improvement Methodologies Capability Maturity Model Key Process Areas Statistical Software Process Improvement Object-Oriented Software Models in UML Use Case Diagrams Communication (Collaboration) Diagrams Activity Diagrams System State Diagrams Sequence Diagrams Class Diagrams Deployment Diagrams Data Flow Diagrams Software Design Styles Functional (-) Functional (+) Object-Oriented (-) Object-Oriented (+) Software Metrics and Estimation Function Point Methodology for OO Designs COCOMO Models McCabe's Cyclomatic Complexity Metric Halstead's Metric Software Testing & Reliability References: 1. Software Engineering: A Practioner's Approach, 5th Ed., by Roger Pressman, McGraw-Hill, 2001. ISBN = 0-07-365578-3. 2. UML Distilled, Third Edition, by Martin Fowler, Addison-Wesley, 2004, ISBN = 0-321-19368-7. 3. Course Notes http://www.cs.ucf.edu/~workman/cen5016 4. Course Notes http://www.cs.ucf.edu/~workman/cop4232 VLSI The students will be tested on the following topics: Multilevel Design Abstraction for VLSI Design Logic Design using CMOS technology Logic Optimization Functional and Systems Design Fundamentals of VLSI Technology af Trends VLSI Hardware Algorithms and Systolic Architectures Application Specific VLSI Chips VLSI CAD Tools FPGA Good sources for the above information are given below. 1. A. Mukherjee, "Introduction to nMOS and CMOS VLSI Systems Design",Prentice 2. N. Weste and K. Eshraghian, " VLSI Systems Design", Addison Wesley,1992. 3. Wayne Wolf, "Modern VLSI Design",Prentice Hall,1994. 4. D. A. Pucknell and K. Eshraghian," Basic VLSI Design", Prentice Hall,1988. 5. John S. Smith, "Field Programmable Gate Arrays", Addison-Wesley, 1997. 6. F. T. Leighton, "Parallel Algorithms and Architectures", Ch.1, Morgan -Kaufman, 1992. DATABASE MANAGEMENT SYSTEMS The students will be tested on the following topics: File Organizations Indexing Techniques External Sorting Algorithms Relational Algebra and Calculus The Relational Data Model SQL (Structured Query Language) Query-by-Example (QBE) Evaluation of Relational Operators Relational Query Optimization Conceptual Design and the ER Model Normal Forms Physical Database Design and Tuning Concurrency Control Crash Recovery A good source for the above information is the first 18 chapters of the following text: Database Management Systems by Raghu Ramakrishnan McGraw-Hill, ISBN: 0-07-050775-9 ARTIFICIAL INTELLIGENCE I. Problem-Solving A. General Problem-Solving Methods Search Algorithms State Space Search Breath-First Search Depth-First Search Heuristic Search Best-First Search Hill-Climbing A* IDA* Genetic Algorithms Simulated Annealing Means-Ends Analysis Logic Task B. Knowledge-Based Problem-Solving Production Rules (Expert Systems) Forward and Backward Chaining Classification Problem-Solving II. Knowledge Representation A. Semantic Networks B. Frames C. FOPC Resolution Prolog E. Ontologies for KR III. Natural Language Processing A. Syntax Context Free Grammars Phrase Structure Grammars RTNS and ATNs. B. Semantics Thematic Roles Ontologies for Semantics IV. Learning A. Learning by Examples (Winston's program) B. Similarity-Based Learning C. Explanation-Based Learning V. Programming Basic Knowledge of Lisp and Prolog TextBooks: Luger and Stubblefield: Artificial Intelligence: E. Rich and K. Knight (McGraw-Hill): Artificial Intelligence. COMPUTER VISION Edge Detection Sobel, Roberts operators Canny Edge Detector Laplacian of Gaussian Edge Detector Region Segmentation Histogram Thresholding Connected Component Algorithm Region merging Binary Images Region properties area, centroid, moments, orientation 2-D Shape Hough transform Pyramids Shape Number Medial Axis transform Motion Optical Flow Horn and Schunck Point correspondence Structure from Motion Heeger and Jepson Stereo stereo geometry Marr-Poggio Correlation-based stereo Book: Machine Vision, Jain et al, McGraw Hill. COMPUTER NETWORKS The students will be tested on the following topics: Network Requirements Connectivity Traffic Characteristics Services Performance Characteristics (Bandwidth, Throughput, Delay, Utilization) Network Architecture Layering and Protocols (OSI Model, TCP/IP Model) Taxonomies/Classifications (based on distances, topology, connectivity, user requirements) Principal Network Nodes and Their Roles Direct Link (Broadcast Domain) Networks and Layer 2 Hardware Building Blocks (nodes and links) Framing (bit-oriented vs clock-based) Error detection Reliable transmission (stop & wait, sliding window such as GoBack-N and Selective Repeat) Ethernet Token Ring FDDI Wireless Networks (802.11 Wireless LANs) Packet Switching Networks and Layer 3 Datagrams Route Computation (including RIP and OSPF) Virtual Circuit Switching Source routing Bridges and LAN Switches Cell Switching (ATM) Principals of Switching Hardware Internetworking with TCP/IP Addressing and subnet design Datagram forwarding IP Protocol ARP adn RARP Redundant design End-to-end Protocols and Layer 4 Transport Control Protocol (TCP) User Datagram Protocol (UDP) Congestion Control and Resource Allocation Weighted Fair Queuing and Random Early Detection TCP Congestion Control Traffic Policing/Shaping (Leaky Bucket, Token Bucket) Reservation and QoS Issues (RSVP, ATM QoS) Coverage of the required materials can be found in many network references. Two example references are listed below. Students should review the appropriate chapters/sections that cover the above topics. Computer Networks, 3rd Ed. Andrew Tanenbaum Prentice Hall 1996 ISBN: 0-13-349945-b Communication Networks- Fundamental Concepts and Key Architectures. A. Leon-Garcia and I. Widjaja McGraw-Hill, 2000 PERFORMANCE MODELING TECHNIQUES The students will be tested on the following topics: Basic Performance Measures Little's Formula The Poisson Process; Continuous Time Markov Chains. Single Server Queues with Poisson Arrivals Throughput, Average Queue Length and Waiting Times in Simple Queues Probability of Packet Loss or Cell Loss in Finite Capacity M/M/1/K systems Product Form Networks. Jackons's Theorem. Open and Closed Systems. Computational Algorithms for Queueing Networks. The required materials are adequately covered in the following reference. Students should review the appropriate chapters/sections that cover the above topics. Introduction to Queueing Networks, 2nd Ed., 2nd Printing Erol Gelenbe and Guy Pujolle. John Wiley & Sons, 1999 ISBN: 0-471-96294-5 DIGITAL MEDIA Digital media is an academic discipline that concerns the use of computers to store and communicate multisensory information. The discipline brings together artists and technologists in a unique partnership of tool-user and toolmaker. At UCF, the course CAP4020 teaches the central principles of Digital Media. It focuses on the Internet as the prime domain of innovation. The syllabi for the 1998 and 1999 offerings of CAP4020 can be seen via the following two hyperlinks: www.cs.ucf.edu/~moshell/CAP4020/1998/index.html www.cs.ucf.edu/~moshell/CAP4020/index.html The midterm exam for the 1998 course is on-line at www.cs.ucf.edu/~moshell/CAP4020/1998/mtx.html The texts for the 1999 course were: Digital Illusion - Dodsworth, Clark. Addison-Wesley, 1998. PERL and CGI for the World Wide Web - Castro, Elizabeth. Peachpit Press, 1999. Emerging Multimedia Computer Communication Technologies - Wu, C. H. and Irwin, J. D. Prentice Hall, 1998 The key concepts, which are studied in Digital Media, include the following: Analog imagery (e. g. photography) as mappings from (x,y) space to color space Digital computer Imagery as arrays of pixels Color palette systems Object space (2d and 3d geometry) and image space (pixel images) Video representation of images and motion Animation Audio as an analog medium Audio as a digital medium: MIDI Multimedia databases Multimedia sequencing and presentation systems Post-production tools and activities Image compression: basic concepts: redundancy, run length, Huffman encoding Spatial domain image compression; Discrete Cosine Transform GIF, JPEG, MPEG Wavelets, fractals ATM technology Broadband to the home: DSL, CATV technologies Basics of LANs; Ethernet Basic Internet technology; TCP/IP; UDP CGI scripting and client/server interaction on the World Wide Web Basics of virtual world and videogame technology Basics of CD-ROM and DVD technology To prepare for the Qualifying Exam, I recommend studying the Midterm Exam, which is accessible by the link provided above, and then making up similar questions and their answers. Work with other students. Provide your questions to them, and answer their questions. COMPUTER GRAPHICS SYSTEMS Texts for the Course 1. (Shirley) Fundamentals of Computer Graphics, Peter Shirley, A.K. Peters (2002) 2. (Angel) Interactive Computer Graphics: A top-down approach, Edward Angel, Addison Wesley, 3rd Edition (2003) Course Outline 1. Math for Computer Graphics References: Shirley: Chapter 2, Chapter 4 Angel: Chapter 4, Appendix B and C, pp. 571-588 "Mathematics for Computer Graphics Applications" by M.E. Mortenson, Industrial Press, 1999. 2. Raster algorithms/Scan-conversion algorithms References: Shirley: Chapter 3 Angel: Chapter 7 3. Geometric Transformation References: Shirley: Chapter 5 Angel: Chapter 4 4. Viewing References: Shirley: Chapter 6 Angel: Chapter 5 5. Visible Surface Finding Algorithms. References: Shirley: Chapter 7 Angel: Chapter 7 6. Reflection models and Surface Shading. References: Shirley: Chapter 2 8, 21 Angel: Chapter 6 7. Ray tracing 8. Texture Mapping References Shirley: Chapter 10 Angel: Chapter 9 9. Sampling and Anti-aliasing 10. Graphics Pipeline Shirley: Chapter 11 11. Data Structure for Computer Graphics Shirley: Chapter 12 Angel: Chapter 8 12. Curves and Surface Shirley: Chapter 13 Angel: Chapter 10 13. Color Shirley: Chapters 17, 18 Angel: Chapter 13 PARALLEL AND DISTRIBUTED COMPUTATION Text for the Course 1. Quinn, M. J. (1994) Parallel Computing:Theory and Practice, McGraw Hill, NY 2. Kumar, V., Grama, A., Grupta, A., and Karypis, G. (1994) Introduction to Parallel Computing: Design and Analysis of Algorithms, Addison Wesley. 3. Ja'Ja, J. (1992) An Introduction to Parallel Algorithms, Addison Wesley. 4. Leighton, F. T. (1992) Introduction to Parallel Algorithms and Architectures: Arrays, Trees, and Hypercubes, Morgan Kaufmann Publishers, San Mateo, CA 5. Akl, S. G. (1997) Parallel Computation: Models and Methods, Prentice-Hall Suggested Areas of Study 1. Parallel computation models -- PRAMs, Circuits 2. Taxonomy of parallel architectures 3. Performance metrics and scalability. Kumar, et. al, Chapter 4 4. Interconnection networks -- static and dynamic. Kumar, et. al, Chapter 2; Quinn, Chapter 3 5. Basic tools, techniques, and paradigms of parallel algorithm design. Quinn, Chapter 6; Ja'Ja', Chapter 2 6. Comparison-based parallel algorithms -- selection, sorting, merging, searching. Quinn, Chapter 10; Kumar, et. al, Chapter 6; Leighton, Sections 1.1 & 1.6; Ja'Ja', Chapter 4 7. Parallel matrix computation -- dense and sparse. Quinn, Chapters 7 & 9; Kumar, et. al, Chapters 5 & 11; Leighton, Sections 1.3 & 2.4 8. Parallel graph algorithms. Quinn, Chapter 12; Kumar et. al, Chapter 7; Leighton, Sections 2.5 9. FFT. Quinn, Chapter 8; Kumar et. al, Chapter 10; Leighton, Section 3.7 10. Parallel dictionaries. Quinn, Chapter 11 11. Basic complexity issues and lower bounds: P-completeness, NC, SC, RNC. Ja'Ja', Chapter 10 COMPUTATIONAL NEUROSCIENCE Topics: Single Neuron Structural subdivisions (soma, dendrites, etc.) and their functions Membrane electrophysiology Pumps, channels Membrane potential, action potential Synaptic transmission Synaptic integration Neuron as an electrical circuit Point neuron model Compartmental model Functional subdivision of the nervous system Peripheral, central, spinal cord, brain, etc. Partitioning of the cerebral cortex (lobes, areas) General organization of the sensory pathways Organization of the motor system Synaptic plasticity Hebbian rule Afferent group selection Effect of lateral interactions on afferent groups Cortical functional architecture Cortical layers Input, interlayer, output connections Cortical columnar organization Cortical cell types Connectivity of the output layers Cortical topography Receptive fields Topographic maps Mexican Hat pattern of lateral connections and its effects Inverted Mexican Hat pattern of lateral connections and its effects Development and maintenance of cortical topographic maps Cortical network as a nonlinear dynamical system Phase-space, bifurcation plots Types of dynamical attractors Chaotic dynamics Transients Visual system RF properties of cells in retina and thalamus (ON- OFF-center) "Simple" RFs in the primary visual cortex, V1 "Complex" RFs in the V1 Higher cortical areas Recommended text: a detailed summary of these topics can be found at www.cs.ucf.edu/courses/cap4932. Use the 2 tests included there to evaluate your preparedness. Additionally, you can use the following textbooks - Essentials of Neural Science and Behavior. E. R. Kandel, J. H. Schwartz, T. M. Jessell; Simon and Schuster Co., 1995. ISBN 0-8385-2245-9; or The Handbook of Brain Theory and Neural Networks. M. A. Arbib (ed.), MIT Press, 1998. ISBN 0-262-51102-9

	CS	CECS	UCF

 

Maintained by CS Support		School of Computer Science University of Central Florida Orlando, Florida  32816-2362 Voice (407) 823-2341 FAX (407) 823-5419