forked from esstorm/Final-Exam
ELTE Final Exam
This branch is even with esstorm:master.

## Latest commit Fetching latest commit…
Cannot retrieve the latest commit at this time.

## Files

Type Name Latest commit message Commit time
Failed to load latest commit information. flashcards material .gitignore README.md collection-2020-01-26@14-39-19.colpkg finalexam.pdf

# ELTE Final Exam preparation

This repository contains the flashcards and other material used to prepare for the BSc. Computer Science final exam.

Anki flashcards

## Exam Topics

1. Sequences, series, funcions, limits and continuity
• Convergence of sequences of real and complex numbers and vectors
• Monotonic sequences
• Notion and convergence of infinite numerical series
• Positive series
• The root and the ratio test
• Alternating (Leibniz type) series
• Power series
• Limits and continuity of vector–vector functions
• Properties of functions on a compact set: Theorems of Heine
• Properties of functions on a compact set: Weierstrass
• Continuity of the inverse function
• The Bolzano theorem
1. Differential and integral calculus and applications
• Differentiation and integration of functions of one real variable
• Rules of differentiation
• Theorems of Rolle, Cauchyand Lagrange
• Extrema, concavity, discussion of functions
• The Riemannian integral
• Integration by parts, integration with substitution
• The fundamental theorem of calculus (The Newton–Leibniz formula)
• Area, arc length, volume, surface
• Differentiation of vector–vector functions
• Jacobi matrix, gradient, partial derivative
1. Systems of differential equations
• The initial value problem
• Linear systems of differential equations
• Linear equations of higher-order
1. Methods of interpolation
• Lagrange interpolation
• Hermite interpolation
• Spline in-terpolation Extra: [ ] 3rd degree spline interpolation (cubic)
1. Numerical solution of linear systems of equations
• Gaussian elimination
• Methods based on product decomposition
• Iterative methods
• Least-squares methods
1. Sets, relations and enumeration problems
• Basic operations on sets and their properties
• Binary relations and their properties (transitivity, etc.)
• Partial orderings and equivalence relations
• Permutations, variations, combinations
• Inclusion-exclusion principle
• Pigeonhole principle
• Binomial theorem
1. Undirected and directed graphs
• Basic concepts in graph theory: vertex, edge, degree, walk, trail, path, cycle, connectivity, component
• Trees and their characterizations
• Eulerian and Hamiltonian graphs
• Labeling and coloring, Kruskal’s algorithms on minimal spanning trees
1. Basics of linear algebra
• Matrices
• Determinants
• Basis and dimension in vector spaces
• Eigenvalues and eigenvectors of matrices, diagonalization
• Orthogonal and orthonormal systems in Euclidean spaces
1. Basics of probability and statistics
• Discrete and continuous random variables
• Law of large numbers
• Central limit theorem
• Statistical estimates
• Classical statistical tests
1. Artificial intelligence
• Path-finding problems and their modelling with directed graph(state-space model, problem decomposition model)
• Heuristic path-finding algorithms (their outcomes and computational cost): local searches, backtracking algorithms, graph searches (A, A∗, AC, Balgorithm)
• Two-player games (game tree, existence of winning strategy, minimax algorithm, alpha-beta pruning)
1. Programming theorems
• Usage of programming theorems in programming
• Summation, counting, maximum search, conditional maximum search (conditional maximum search is missing)
• Sequential search
• Binary search
1. Software development models
• Development stages of large scale systems (ambiguous)
• The concept of object-oriented programming, type inheritance
• Views of object-oriented modeling, UML tools (wtf is views?)
• The notion of software design patterns
1. Static and dynamic models
• Static model (class diagram, object diagram)
• Usecase diagrams
1. Compilation and execution of programs
• Compilers and interpreters, bytecode
• Make
• Compilation units, libraries
• Syntactic and semantic rules
• Static and dynamic type checking
• Parallel programming
1. Data, operators and control structures
• Representation of numbers, basic data types
• User defined types
• Operators, expression evaluation
• Statements, control structures,recursion, exception handling
• Data abstraction
• Class, inheritance, static and dy-namic binding, subtype polymorphism
• Generics
1. Program structure
• Block, visibility, scope
• Automatic, static and dynamic variables,garbage collection
• Constructor, destructor
• Cloning and comparing objects
• Programmodules, namespaces
• Subroutines, parameter passing
1. Compilers
• Structure of compilers, the tasks of the components
• Lexical analyzer and its functions, implementation
• Classification and comparison of syntactic analyzers, overview of their creation and functioning
• The notion and use of ATGs
• Code generation in assembly for basic imperative constructs
1. Logic
• The syntax and semantics of propositional and predicate calculus
• The notion of logical consequence
• Basic methods for proving logical consequences in propositional calculus: truth tables, the method of semantic tableaux, and the resolution
1. Theory of computation
• The Church–Turing thesis
• Variants of Turing machines (one tape – multi tape, deterministic – non-deterministic)
• Recursive and recursively enumerable languages
• Undecidable problems
• Reducibility
• The time complexity classes P and NP
• Polinomial time reducibility
• NP-complete problems
• The space complexityclasses PSPACE and NPSPACE
• Savitch’s theorem
• PSPACE-complete problems
1. Data structures
• Representations and operations of basic data structures—array, stack, queue, priority queue, list, binary tree, graph
1. Basic algorithms
• Representations of search data structures (binary search tree, AVLtree, 2-3 tree, B tree, hashing with chaining and open addressing)
• Sorting algorithms and their efficiency (bubble, insert, maximum selection, tournament, heap, quick and merge sort algorithms)
• Sorting in linear time: bucket sorts, radix sorts
1. Formal languages
• Generative grammars, the Chomsky hierarchy
• Basic properties and application of regular and context-free grammars and languages
• Finite automata and pushdown automata
1. Operating systems—parallel processes
• The notion and implementation of process and thread
• Interactive, batch and real-time processes, scheduling algorithms
• Types of parallelism, race conditions, critical sections
• Shared memory and messaging
• Semafors and monitors
• Deadlocks: description, avoidance, prevention, recognition
1. Operating systems—storage handling
• Hierarchy of storages
• Memory handling: fixed and dynamic partitions, virtual memory
• Paging and segmentation
• Page re-placement algorithms, working set
• Scheduling input and output, reducing serving time
• Organizing disk storage, physical and logical formatting, partitions
• Redundant arrays, array handling systems
• File systems and their implementation
• Block reservation strategies, registering free storage space, journaled file systems
1. Computer networks
• Physical layer, data link layer, MAC, network layer, transport layer—services, methods, protocols
1. Distributed systems
• Definition
• Design goals
• Distribution transparency
• Typesof distributed systems
• Architectures
• Middleware
• Processes
• Virtualization
• Clients-servers
• Code migration
• Types of communication (transient, persistent,message-oriented, RPC, multicasting, data dissemination)
• Naming (flat, structured,attributed)
• Coordination
• Clock synchronization
• Logical clocks
• Vector clocks
• Mutual exclusion
• Election algorithms
• Location systems
• Consistency and replication
1. Databases—query languages
• Relational model, entity–relationship model, transformation from ER to relational model
• Relational algebra, SQL, Datalog
• Recursion inquery languages
• Procedural elements in query langauges (variables, control structures, subprograms, cursors, exceptions)
1. Databases—query execution
• Index structures, sparse and dense index, B+ tree, bitmap index, dynamic hashing
• One-pass and two-pass algorithms, sort based and hash-based algorithms
• Join methods
• Cost of operations
• Query execution plans
You can’t perform that action at this time.