Corelab

Introduction to Computer Science. Algorithms and Data Structures, programs, programming languages. Pascal. Specification, design, coding, verification, documentation and maintenance of programs. Basic data structures, control structures, procedures, recursion, parameter passing.

The goal of this course is to introduce students to fundamental computer principles and various areas of Computer Science. The course covers subjects of Theoretical Computer Science (logic for Computer Science, automata, formal grammars, computability and complexity), number representation and operations (binary arithmetic, number systems, binary representation, fixed point and floating point operations, encoding), computer architecture (processor architecture, instruction format-machine language, assembly language, memory organization-peripheral devices-storage devices), as well as an introduction to system software (operating system, compiler-interpreter), applications (databases, file management, etc), and various programming paradigms (functional, logical, object-oriented programming).

Introduction to fundamental computing principles and notions: computational problems as formal languages, models of computation, computability, algorithms, complexity classes, completeness, automata, formal grammars, hardness results, logic in computer science. The course also offers an introduction to the functional programming paradigm with the Haskell programming language and a set of lab assignments that help in demonstating and clarifying some of the theoretical concepts taught.

Techniques for asymptotic program analysis and algorithm selection criteria. Algorithm design techniques: divide and conquer, dynamic programming, greedy algorithms. Applications to graph theory (depth-first search, breadth-first search, minimum spanning tree, shortest path). Sorting and searching. Algebraic problems (evaluation of polynomials, matrix multiplication). Polynomial-time algorithms and NP-complete problems.

Approximation algorithms. Linear programming and LP-based approximation algorithms. Randomized, online, and distributed algorithms. Fixed parameter tractability and parameterized complexity. Special topics: algorithmic game theory; mechanism design; cryptography; PCP and non-approximability; non-conventional computing; machine learning.

Computability: Logical foundation of computer science. Historical review on the problem of decidability of mathematical statements, and solvability or computability of problems. Simple equivalent models of computation: Turing machines, WHILE programs. Induction and recursion, encoding and semantics. Fixed-point theory. Arithmetic hierarchy. Relations between complexity classes. Reductions and completeness. Oracles. Polynomial hierarchy. Probabilistic, interactive and counting classes. Advanced topics from the theory of formal grammars. Applications to programming language syntax.

Classical cryptography: Caesar, Vigenere, coincidence index, Kasiski test. Shannon's perfect secrecy, one-time pad. Symmetric cryptography. Block cryptosystems: Feistel networks, DES, AES. Operation modes. Message authentication codes (MACs). Stream ciphers. Νumber theory: modular arithmetic, quadratic residues, Chinese Remainder Theorem, Legendre's theorem, Euler's "phi" function, Legendre and Jacobi symbols. Primality tests: Fermat, Solovay-Strassen, Miller-Rabin, AKS algorithm. Factorisation: rho method, Dixon, B-smoothness. Public-key cryptography. RSA and Rabin cryptosystem. Disrete logarithm and ElGamal cryptosystem. Diffie – Hellman key exchange. Cryptographic assumptions and reductions. Digital signatures: RSA, ElGamal, DSS, one-time, blind, undeniable signatures. Hash functions. Zero knowledge identification schemes: Fiat-Shamir and Feige-Fiat-Shamir. Computational Complexity theory. Arthur-Merlin games, interactive proof systems. Zero knowledge proofs.

Languages and their representations. Grammars, context-sensitive and context-free grammars. Finite automata and regular grammars. Pushdown automata. Turing Machines. Automata and language recognition. Applications in programming languages syntax. (Un)decidability and complexity problems.

Computational Models - Turing Machines: Problems, Algorithms and Languages. Equivalence of Computational Models, Turing Machines, Time and Space bounds, multiple strings, linear speedup, nondeterminism. Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization, The Halting Problem, Recursive and Recursive Enumerable Sets. Rice's Theorem, Recursive Unseparability, Second-Order Logic, Undecidability-Incompleteness, Fagin's Theorem. Complexity Classes: Complexity measures, time and space classes, Hierarchy Theorems, Gap Theorem. Space Computation: The classes L and NL, Savitch's Theorem, Immerman-Szelepscényi Theorem, Undirected Reachability and Reingold's Theorem. Reductions & NP-Completeness: Different types of reductions (Karp, Cook, Cook[1], tt) and relations among them, NP-completeness, Cook's Theorem, NP-complete problems, pseudopolynomial algorithms, Ladner's Theorem, density, sparse sets, The "Berman-Hartmanis" conjecture, NP-isomorphism, padding. Function Problems: The classes coNP and ΔNP, Function classes and reductions, the classes PLS and PPAD. Randomized Computation: Randomized algorithms and complexity classes, quantifier notation and related results, Error reduction, semantic and syntactic classes, the "P vs BPP" question. Non-Uniform Complexity: Boolean circuits, the class P_/poly, Turing Machines with advice, parallel computation, circuit lower bounds, natural proofs. Oracles & The Polynomial Hierarchy: Oracles and oracle classes, the polynomial-time hierarchy and related theorems, The BPP Theorem, Operator-defined classes. Interactive Proofs: The class IP, Arthur-Merlin games, Shamir's Theorem, Probabilistically Checkable Proofs and the PCP Theorem. -Counting Complexity: The class #P and #P-completeness, Toda's Theorem, Gaps, the class TotP. Parameterized Complexity: Fixed-Parameter Tractability, FPT Reductions, The Classes paraNP, XP and W[P], The W-Hierarchy and the A-Hierarchy.

Introduction to Fortran programming language: simple data types, variables, constants, expressions, statements. Control structures: if-then-else, do loop, do while. Programming methodology: iteration, recursion, data structures, algorithms. Arrays, records, linked lists. Dynamic memory allocations. Subroutines and functions, parameter passing. Input, output, files. Foundations of object-oriented programming: abstract data types, classes, objects, methods, encapsulation, inheritance, polymorphism. Interconnection to other programming languages. Software engineering principles: specifications, design, implementation, verification, documentation and maintenance.