COMP 301: Operating Systems
History and evolution of operating systems. Review of computer organization: CPU, registers, MMU, interrupts, stack-based execution. Processes: definition, process state, threads, resources. Unix process control. Process table, PCBs. POSIX threads. Multiprogramming: definitions. Monitors, concepts and implementation. Semaphores, reader-writer locks, producer/consumer and buffers. Deadlocks. Process scheduling. Memory management: Memory hierarchies, locality, caching and prefetching, fragmentation. Memory allocation. Program loading. Segmentation, paging. The i386 paging model. Memory mapping, copy-on-write. Virtual memory, replacement policies. Input/output and interprocess communication: Streams and stream I/O. Pipes, sockets. Terminals. Network and block devices. Device drivers, driver architecture. I/O programming using polling, threads, event-driven programming. External memory: file systems. File and directory management. Magnetic disks, performance model, formatting, I/O scheduling.
COMP 401: Algorithms and Complexity
Models and concepts of complexity. Introduction to discrete mathematics for algorithm analysis. Asymptotic cost. Recursion and recurrences, solution by induction, master theorem. Fundamental recursive algorithms: multiplication, Karatruba's algorithm, FFT. Order statistics. Dynamic programming, memoization. Knapsack problem. Non-determinism, Cook's theorem, the classes P and NP, NP-completeness. Amortized complexity analysis, amortized costs in basic dynamic data structures. Range search over ordered keys, data structures for multidimensional range search. Introduction to graph theory. Data structures for graph representation. Graph traversals, depth and breadth first search, traversing DAGs, topological sorting. Connected components. Weighted graphs. Minimum spanning trees, Prim's algorithm, Kruskal's algorithm. The Union-Find problem. Ackerman's function. Shortest paths and distance metrics. Triangle inequality. Representing single-source and all-pairs shortest paths. The algorithm of Bellman-Ford.
COMP 406: Advanced Topics in Databases
Coordination and recovery in the operation of database management systems. Distributed databases and operational problems. New SQL–3 standard. Database engines. Advanced database systems and applications (object–oriented, temporal, active, spatial databases,data warehouses). Correlation between mathematical logic and data warehouses (inductive databases).
COMP 414: Principles of Distributed Software Systems
Models and methods for interprocess communication. Sockets, shared memory, group communication, remote procedure calls, distributed objects. Basic network programming. Sessions. Protocols. Distributed system architectures: client-server, multi-tier architecture, mediators, code migration, agent systems, peer-to-peer networks. Overview of CORBA, using CORBA IDL. Naming and addressing: names, physical and logical addresses, name services, DNS. Directory services, LDAP. Service oriented architecture. Distributed algorithms: Models, algorithms with coordinator. Time in distributed systems. Causality. Lamport's theorem. Lamport clocks, vector clocks. Global state and snapshots. Basic algorithms without coordinator: leader election, mutual exclusion, byzantine agreement. Search algorithms: distributed data structures, search in peer-to-peer networks, distributed hash tables. Reliability: fault-tolerance, backups, replication. Distributed transactions, two and three-phase commit protocols. Security.
COMP 416: Multidimensional Data Management
Multidimensional data: raster and vector representations, abstract data types, standard formats. Management of large datasets, performance issues. Storage and retrieval of data in main memory and hard disks. Main applications: GIS, CAD, graphics. Introduction to spatio–temporal databases, data models, languages for spatial, topological and temporal queries. Basic 2–d and 3–d geometry, coordinate systems, elements of cartography. Computational geometry, convex hull algorithms, triangulation, data structures for point location and segment intersection. Geometric data structures, range search, nearest neighbors, special cases, external data structures, distributed data structures. Query processing algorithms. High–dimensional data processing, metric spaces, similarity metrics, optimization problems, linear programming.
COMP 516: Data Processing and Management in Sensor Networks
Sensor nodes: Characteristics, constraints. Sensor network applications. Distributed data processing in sensor networks. Continuous Queries. Types of continuous queries and their characteristics. Query Languages. Data collection techniques (pull–based and push–based). Data storage, indexing and search techniques. Aggregation tree. Synchronization and data transmission. Different techniques of forming the aggregation tree. Distributed sensor (self)-organization. Approximate queries in sensor networks. Observing moving objects. Information loss and duplicate calculation of information: means of handling such issues. Quality of sensor measurements. Ways of isolating and removing spurious measurements.