Israel Bagrut Computer Science 5 Units flashcards

33 cards. Read the term and the definition here. The deck at the top of this page is optional.

Loop invariant

A property true before and after every iteration of a loop; used with initialization, maintenance, and termination to prove algorithm correctness.

Master Theorem

Method solving T(n) = aT(n/b) + f(n) by comparing f(n) with n^(log_b a), yielding Θ(n^(log_b a)) when f is polynomially smaller.

Greedy-choice property

A condition under which a locally optimal choice can be extended to a globally optimal solution, making a greedy algorithm correct.

Dynamic programming

Technique solving problems with overlapping subproblems by storing subproblem results in a table or memo, avoiding recomputation.

String immutability

In Java and C#, String objects cannot be modified; concatenation creates new objects, so StringBuilder is used for repeated appends.

Pass by value

Java and C# default semantics: the argument's value (or object reference) is copied into the parameter, so reassignment does not affect the caller.

Integer overflow

When an arithmetic result exceeds the type's range, bits wrap around silently; Java int is 32-bit two's complement.

try-with-resources

Java construct that automatically closes resources declared in the try header, even when an exception is thrown, replacing manual finally blocks.

Dynamic dispatch

Runtime selection of an overridden method based on the actual object type, enabling polymorphism through superclass references.

Liskov Substitution Principle

Subtypes must be usable wherever the supertype is expected without breaking the program's correctness, preserving the supertype's contract.

Composition over inheritance

Design preference where a class holds another object (has-a) rather than extending it (is-a), reducing coupling and fragile base-class problems.

Abstract class versus interface

An abstract class may hold state and partial implementation; an interface declares a contract that classes can implement in multiple combinations.

Hash table load factor

Ratio of stored entries to buckets; when it exceeds a threshold (about 0.75), the table rehashes to keep average lookup near O(1).

Binary search tree

A binary tree where each node's left subtree holds smaller keys and right subtree larger keys; search costs O(h) for height h.

In-order traversal

Visiting left subtree, then node, then right subtree; applied to a binary search tree it yields keys in ascending sorted order.

Heap property

In a min-heap, each parent is no greater than its children; stored in an array where children of index i are 2i+1 and 2i+2.

Adjacency list

Graph representation storing each vertex's neighbors in a list; uses O(V+E) memory and suits sparse graphs efficiently.

Big-Theta notation

Θ(f(n)) denotes a tight asymptotic bound: the function grows at the same rate as f, both above and below by constants.

Amortized complexity

Average cost per operation over a worst-case sequence; dynamic array append is amortized O(1) despite occasional O(n) resizing.

Turing machine

Abstract model with an infinite tape, finite states, and a transition function; it defines what is effectively computable.

Decidable language

A language for which some Turing machine halts on every input, accepting members and rejecting non-members with a definite answer.

P versus NP

P contains problems solvable in polynomial time; NP contains problems with polynomial-time verifiable certificates. Whether P = NP is open.

Agile sprint

A fixed-length iteration in Scrum delivering a working increment, planned from a prioritized backlog and reviewed at the end.

Regression testing

Re-running tests after changes to confirm that existing functionality still works and no previously fixed defect has reappeared.

Test-driven development

Cycle of writing a failing test (red), writing minimal code to pass (green), then refactoring while keeping all tests green.

Refactoring

Restructuring code to improve readability or design without changing external behavior, typically protected by an automated test suite.

Pumping lemma

Property of regular languages: any sufficiently long word splits as xyz with |xy| ≤ p, |y| > 0, and xy^i z in the language for every i.

Context-free grammar

A set of production rules of the form A → γ with a single nonterminal on the left; generates context-free languages recognized by pushdown automata.

Chomsky hierarchy

Nested classes of formal languages: regular, context-free, context-sensitive, and recursively enumerable, each tied to a computational model.

Two's complement

Binary encoding of signed integers where negation is bit inversion plus one; an n-bit signed value ranges from -2^(n-1) to 2^(n-1)-1.

Fetch-decode-execute cycle

CPU loop that fetches the instruction at the program counter, decodes it, executes it, and updates the program counter.

CIA triad

Core security goals: confidentiality (authorized access only), integrity (data unaltered), and availability (accessible when needed).

Digital signature

A hash of a message encrypted with the sender's private key, verifying integrity and authenticity using the sender's public key.