Algorithm concept. Analysis and complexity. Design methods: Divide and conquer: The general method, binary search, merge sort, quick sort, selection, matrix multiplication. Greedy method: The general method, minimum spanning Trees. Dynamic programming: The general method, shortest paths, optimal search trees, and the traveling salesman problem. Backtracking: The general method, The 8-queens Problem. NP-hard and NP-complete problems: Cooks theorem, NP-hard graph problems.
Alphabets and languages. Finite representation of language. Deterministic and non-deterministic finite automata and their applications. Equivalence considerations. Regular expressions. Context-free languages. Context-free grammars. Regular languages, pushdown automata. Properties of context-free languages. Determinism and parsing top-down parsing, and bottom-up parsing. Turing machines: Computing with Turing machines, combining Turing machines, and nondeterministic Turing machines.
Introduction to computer graphics: History, applications, and graphics system software. Output primitives: Points, lines, circles, ellipses, character generation. Attributes of output primitives: Color and intensity, area filling, character attributes. Two-dimensional transformations: Basic transformations; translation, scaling and rotation. Matrix representations and homogeneous coordinates, Composite transformations. Windowing and clipping. Segments. Interactive input devices.
Artificial and Human intelligence: Domains of AI-symbolic processing: Semantic nets, modeling, model based reasoning, frames. Inference techniques: Implication, forward and backward chaining, inference nets, predicate logic, quantifiers, tautology, resolution, and unification. Rule based systems: Inference engine, production systems, problem solving, planning, decomposition, and basic search techniques. AI languages: Symbolic and coupled processing prolog: Objects and relations, compound goals, backtracking, search mechanism, dynamic databases, Lisp: program structure and operations, functions, unification, memory models. Fields of AI: heuristics and game playing, automated reasoning, problem solving, computational linguistics and natural language processing, computer vision, robotics. AI based computer systems: Sequential and parallel inference machines, relation between AI and artificial neural nets, fuzzy systems.
An overview of database management; what is a database system, operational data, data independence, relational systems and others. An architecture of a database system: The three levels of architecture, the external level, the conceptual level, the internal level, mappings, the database administrator, the database management system. The internal level: Database accesses, page sets and files, indexing. Hashing, pointer chains, comparison techniques. An overview of DB2: Relational databases, the SQL language, major system components. Relational algebra: A syntax for the relational algebra, traditional set operations, special relational operations. Relational calculus: Tuple-oriented relational calculus, relational calculus vs. relational algebra, domain-oriented relational calculus, query-by-examples. Data definition: Base tables, indexing. Data Manipulation: Simple queries, join queries, built-in functions, advanced features, update operations. The system catalog: Querying the catalog, updating the catalog. View: View definition, DML operations and view, logical data independence, advantages of views. Embedded SQL: Operations not involving cursors, operations involving cursors, a comprehensive example, dynamic SQL. Database environment: Recovery and concurrence security and integrity, database product family.
