Exit Exam Part 2

A comprehensive flashcard set of the 15 courses on the exit exam.

What are String Algorithms?

What are String Algorithms?

String Algorithms are techniques and methods used to manipulate, search, and analyze strings.

Define the term "Pattern Matching."

Pattern Matching refers to the process of finding occurrences of a pattern within a larger text or data.

Why are String Algorithms important?

String Algorithms are important because they enable efficient manipulation and analysis of strings, which is fundamental in various applications such as search engines, data analysis, and text processing.

Name an application where String Algorithms are used.

An application of String Algorithms is in search engines to match user queries with relevant documents.

What is the Brute Force Algorithm?

The Brute Force Algorithm is a simple pattern matching algorithm that checks each position in the text for a match with the pattern.

Define the term "Naive Pattern Matching."

Naive Pattern Matching is the basic approach of comparing characters at each position in the text and pattern.

What is the time complexity of the Brute Force Algorithm?

The worst-case time complexity of the Brute Force Algorithm is O((n-m+1)m), where n is the text length and m is the pattern length.

What is the Knuth-Morris-Pratt (KMP) Algorithm?

The Knuth-Morris-Pratt Algorithm is a string matching algorithm that utilizes a preprocessed pattern to avoid unnecessary comparisons.

What is the Preprocessing Phase in the KMP Algorithm?

The Preprocessing Phase in the KMP Algorithm involves constructing the longest proper prefix that is also a suffix for each prefix of the pattern.

What is the Pattern Matching Phase in the KMP Algorithm?

The Pattern Matching Phase in the KMP Algorithm efficiently matches the pattern by utilizing the computed prefixes.

What is the time complexity of the KMP Algorithm?

The time complexity of the KMP Algorithm is O(n+m), where n is the text length and m is the pattern length.

What is the Boyer-Moore Algorithm?

The Boyer-Moore Algorithm is a fast string searching algorithm that utilizes both bad character and good suffix heuristics.

What is the Bad Character Heuristic in the Boyer-Moore Algorithm?

The Bad Character Heuristic in the Boyer-Moore Algorithm utilizes the last occurrence table of characters in the pattern to skip unnecessary comparisons.

What is the Good Suffix Heuristic in the Boyer-Moore Algorithm?

The Good Suffix Heuristic in the Boyer-Moore Algorithm utilizes information about good suffixes in the pattern to skip comparisons.

What is the time complexity of the Boyer-Moore Algorithm?

The time complexity of the Boyer-Moore Algorithm is O(n+m), where n is the text length and m is the pattern length.

What is the Rabin-Karp Algorithm?

The Rabin-Karp Algorithm is a string matching algorithm that uses hash functions to efficiently search for patterns.

What is a Rolling Hash Function in the Rabin-Karp Algorithm?

A Rolling Hash Function is a technique to compute the hash value of a sliding window in a string.

What is the Pattern Matching technique used with the Rabin-Karp Algorithm?

The Rabin-Karp Algorithm matches the hash values of the pattern and each window in the text.

What is the time complexity of the Rabin-Karp Algorithm?

The time complexity of the Rabin-Karp Algorithm is O((n-m+1)m), where n is the text length and m is the pattern length.

What are Finite Automata in the context of Pattern Matching?

Finite Automata are abstract machines used to recognize patterns or perform pattern matching using a set of states and transitions.

What is a Deterministic Finite Automaton (DFA)?

A Deterministic Finite Automaton is a type of Finite Automaton where each input has a unique transition to the next state.

What is a Non-deterministic Finite Automaton (NFA)?

A Non-deterministic Finite Automaton is a type of Finite Automaton where an input may have multiple possible transitions to the next state.

How are Finite Automata used for Pattern Matching?

Finite Automata can be constructed to recognize or match patterns efficiently by transitioning through states based on the input characters.

Define Regular Expressions.

Regular Expressions are sequences of characters used to define search patterns for text matching and manipulation.

What is Pattern Syntax in Regular Expressions?

Pattern Syntax defines the rules and symbols used to construct regular expressions, specifying the pattern structure and matching conditions.

How are Regular Expressions used for Matching and Searching?

Regular Expressions are applied to search for and match patterns within strings, allowing for powerful text manipulation and extraction.

Name an application of Regular Expressions.

An application of Regular Expressions is in text editors or word processors for searching and replacing specific patterns.

What is a Suffix Tree Data Structure?

A Suffix Tree is a compressed trie-like data structure used to store all the suffixes of a given string.

What is a Suffix Array Data Structure?

A Suffix Array is a sorted array of all the suffixes of a given string, allowing efficient pattern matching and substring search.

Name an application of Suffix Trees and Arrays.

An application of Suffix Trees and Arrays is in bioinformatics for DNA sequence matching and analysis.

Define the term "Longest Common Subsequence (LCS)."

The Longest Common Subsequence refers to the longest subsequence shared by two or more strings, which is not necessarily consecutive.

What is the Dynamic Programming approach for solving the LCS problem?

The Dynamic Programming approach breaks down the problem into smaller subproblems and builds a table to store and compute optimal solutions.

What are the Applications of LCS?

LCS has applications in DNA sequencing, text comparison, plagiarism detection, and data compression.

Define the term "Edit Distance."

Edit Distance is a measure of similarity between two strings, representing the minimum number of operations (insertions, deletions, substitutions) required to transform one string into the other.

What is the Levenshtein Distance?

The Levenshtein Distance is a specific measure of Edit Distance, considering only insertions, deletions, and substitutions as operations.

What is the Wagner-Fisher Algorithm?

The Wagner-Fisher Algorithm is a dynamic programming algorithm that computes the Edit Distance between two strings.

What are the Applications of Edit Distance?

Edit Distance has applications in spell checking, DNA sequence alignment, and natural language processing.

Define the term "Palindrome."

A Palindrome is a string that remains the same when read forward or backward.

How is Palindrome Detection solved using Dynamic Programming?

Palindrome Detection can be solved using Dynamic Programming by building a table to store and compute information about palindromic substrings.

Name an application of Palindrome Detection.

An application of Palindrome Detection is in text editors for highlighting or checking palindromic words or phrase

What is a distributed database?

A distributed database is a database system in which data is stored and accessed from multiple computers or servers.

Define data fragmentation.

Data fragmentation is the process of dividing a database into smaller fragments to be distributed across multiple nodes.

What is the advantage of data replication in a distributed database?

Data replication provides high availability and fault tolerance by maintaining redundant copies of data across multiple nodes.

What is concurrency control in a distributed database?

Concurrency control refers to managing simultaneous access to shared data in a distributed database to prevent conflicts.

Define access control in the context of database security.

Access control refers to managing user access and permissions to ensure that only authorized users can access specific data.

What is authentication in database security?

Authentication is the process of verifying the identity of a user or entity attempting to access the database.

Define data privacy in the context of database security.

Data privacy involves protecting sensitive data from unauthorized access, ensuring that only authorized users can view or modify it.

What is a distributed commit protocol?

A distributed commit protocol coordinates the commit or rollback of distributed transactions to ensure their atomicity and durability.

Define a data warehouse in the context of distributed databases.

A data warehouse is a centralized repository that stores and manages large volumes of data for analysis and decision-making.

What is the purpose of query optimization in a distributed database?

Query optimization aims to optimize the execution plan of a query to minimize data transfer and processing overhead in a distributed environment.

Define a master-slave replication model.

In a master-slave replication model, one node (master) maintains the primary copy of data, and other nodes (slaves) replicate that data.

What is the role of a transaction manager in a distributed database?

The transaction manager is responsible for ensuring the atomicity, consistency, isolation, and durability (ACID) properties of distributed transactions.

Define the client-server architecture in a distributed database.

The client-server architecture involves clients interacting with a centralized server that manages the distributed data across multiple nodes.

What is the purpose of encryption in database security?

Encryption is used to protect data by converting it into a form that can only be accessed with the appropriate decryption key.

Define role-based access control (RBAC) in database security.

Role-based access control is a security model that grants permissions based on the roles assigned to users, simplifying access management.

What is data integrity in the context of database security?

Data integrity ensures that data remains accurate, consistent, and reliable throughout its lifecycle, protecting it from unauthorized modifications.

Define distributed deadlock detection in a distributed database.

Distributed deadlock detection is the process of identifying and resolving deadlocks that can occur when multiple transactions access shared resources.

What is a distributed file system in a distributed database?

A distributed file system is a method of organizing and accessing files stored across multiple nodes in a distributed database environment.

Define data synchronization in a distributed database.

Data synchronization involves ensuring that data copies across multiple nodes in a distributed database are consistent and up to date.

What is the purpose of role-based access control (RBAC) in database security?

RBAC simplifies access control by assigning permissions based on user roles, making it easier to manage and enforce security policies.

Define data masking in database security.

Data masking is the process of obfuscating sensitive data in a database, replacing it with realistic but fictitious values to protect privacy.

What is the two-phase commit (2PC) protocol?

The two-phase commit protocol is a distributed commit protocol that ensures the atomicity of distributed transactions by coordinating their commit or rollback.

Define horizontal fragmentation in a distributed database.

Horizontal fragmentation divides a table into subsets of rows based on a defined condition, distributing these subsets across multiple nodes.

What is the purpose of data encryption in a distributed database?

Data encryption helps protect data confidentiality by transforming it into an unreadable form that can only be accessed with the appropriate decryption key.

Define distributed database recovery.

Distributed database recovery involves restoring the database to a consistent state after a failure or crash, ensuring data integrity.

What is the CAP theorem in distributed databases?

The CAP theorem states that it is impossible to simultaneously achieve consistency, availability, and partition tolerance in a distributed database system.

Define distributed query optimization.

Distributed query optimization aims to minimize the cost and time required to process queries that access distributed data across multiple nodes.

What is a distributed hash table (DHT)?

A distributed hash table is a decentralized distributed database that uses a hash function to map keys to nodes, allowing efficient key-value lookups.

Define data fragmentation in a distributed database.

Data fragmentation divides a table into subsets of columns or rows, distributing these subsets across multiple nodes in a distributed database.

What is the purpose of a distributed transaction coordinator?

A distributed transaction coordinator manages and coordinates the execution of distributed transactions across multiple nodes in a distributed database.

Define the hybrid architecture in a distributed database.

The hybrid architecture combines elements of both client-server and peer-to-peer architectures to provide a flexible and scalable distributed database system.

What is the role of a distributed deadlock detection algorithm?

A distributed deadlock detection algorithm identifies and resolves deadlocks that can occur when multiple transactions access shared resources in a distributed database.

Define distributed database concurrency control.

Distributed database concurrency control manages concurrent access to shared data in a distributed database, ensuring data consistency and preventing conflicts.

What is the purpose of a distributed lock manager?

A distributed lock manager manages locks on shared resources in a distributed database, preventing concurrent access conflicts and ensuring data integrity.

Define the peer-to-peer architecture in a distributed database.

The peer-to-peer architecture allows nodes in a distributed database to act as both clients and servers, enabling direct communication and resource sharing.

What is distributed data integration?

Distributed data integration involves combining data from multiple distributed databases or sources to provide a unified view or analysis.

Define distributed data warehousing.

Distributed data warehousing involves the storage and analysis of data from multiple distributed sources to support decision-making and business intelligence.

What is the purpose of data anonymization in database security?

Data anonymization is the process of removing or encrypting personally identifiable information from a database to protect individual privacy.

Define distributed database consistency.

Distributed database consistency ensures that data copies across multiple nodes in a distributed database reflect the same state at any given time.

What is the purpose of a distributed cache in a distributed database system?

A distributed cache stores frequently accessed data in memory across multiple nodes, improving performance and reducing the load on the database.

What does AJAX stand for?

AJAX stands for Asynchronous JavaScript and XML.

Define AJAX.

AJAX is a web development technique that allows for asynchronous communication between a web browser and a server, enabling dynamic and interactive web applications.

What is the main purpose of using AJAX?

The main purpose of using AJAX is to update specific parts of a web page without reloading the entire page and to perform background data retrieval.

What is the XMLHttpRequest object?

The XMLHttpRequest object is a JavaScript object that provides methods and properties to send HTTP requests to the server and handle the server's response asynchronously.

What are the benefits of using AJAX in web development?

The benefits of using AJAX include improved user experience, reduced bandwidth usage, and faster response times.

Name a limitation of AJAX.

One limitation of AJAX is browser compatibility issues.

What does JSON stand for?

JSON stands for JavaScript Object Notation.

Define JSON.

JSON is a lightweight data interchange format that is easy for humans to read and write and easy for machines to parse and generate. It is based on JavaScript syntax.

What is the syntax of a JSON object?

JSON objects consist of key-value pairs enclosed in curly braces ({}) and separated by commas.

What data types are supported in JSON?

JSON supports data types such as strings, numbers, booleans, arrays, objects, and null values.

How can you convert a JSON string into a JavaScript object?

You can use the JSON.parse() method to convert a JSON string into a JavaScript object.

What is XML?

XML is an extensible markup language used to store and transport data, emphasizing simplicity, generality, and usability.

Explain the structure of an XML document.

An XML document has a hierarchical structure with a single root element that contains nested elements.

What are the advantages of using XML?

The advantages of using XML include human and machine readability, flexibility, and extensibility.

What is the purpose of XML elements?

XML elements represent the structure and content of the data being stored or transported.

What are attributes in XML?

Attributes provide additional information about XML elements and are specified within the start tag of an element.

Compare JSON and XML.

JSON is more lightweight and easier to read and write, while XML is more verbose and supports complex document structures.

What is the main role of XML in web services?

XML is commonly used to structure and exchange data in web services.

How can AJAX and JSON be used together?

AJAX can be used to retrieve JSON data from a server and update the web page dynamically with the received data.

How can AJAX and XML be used together?

AJAX can be used to retrieve XML data from a server and update the web page dynamically with the received data.