Software engineering | JSE

Numerical methods review week questions

Feel free to share any other resources in the comments section! (Btw, was there any video on variational methods recorded by prof, or it's me imagining extra stuff?)

"So, as I miss the Lecture and Tutorial, I recorded videos to explain Gradient Descent Methods" Video of Lecture https://www.youtube.com/watch?v=IkwGAlrWC6w Video of Tutorial https://www.youtube.com/watch?v=btActkKnTsU

Don't forget about those! But still make sure that you are using the method taught by professor!

10questions (120minutes) 7 problem, 3 from theoretical parts 7 problem (open ended ) includes: Convex programming (Lagrange theorem) Gradient Descent Variation methods (Jacobi method and Legendre equations) Dynamic programming 3 questions will be open ended No formula sheet (All basic formulas must be learnt. Prof will not ask for gradient descent formulas but rather how to use them properly to solve the problem.) Calculator is allowed Just a recommendation, review all homework tasks.

You can use this YouTube playlist (that I am appending till the end of ML exam) as preparation: https://youtube.com/playlist?list=PLIlUIDVf6mk4AYHu67NnGC-cFQx9FxT2q&si=f56t3m8mNzvAUQd3

Topics that should be covered from ML: - Neural Networks - Linear Layers - Convolutional Neural Networks - Recurrent Neural Networks - Attention Neural Networks - Ensemble Models Professor Kh.Juraev also highlighted that there will be problems from this doc in the final: https://nlp.seas.harvard.edu/2018/04/03/attention.html

Materialized Views: When the results of a view expression are stored in a database system, they are called materialized views. The process of keeping the materialized views updated is know as view maintenance. Database system uses one of the three ways to keep the materialized view updated: - Update the materialized view as soon as the relation on which it is defined is updated. - Update the materialized view every time the view is accessed. - Update the materialized view periodically. Materialized view is useful when the view is accessed frequently, as it saves the computation time, as the result are stored in the database before hand. Materialized view can also be helpful in case where the relation on which view is defined is very large and the resulting relation of the view is very small. Materialized view has storage cost and updation overheads associated with it.

While ordinary checkpoint is being carried out it does not let transactions to be carried out While fuzzy checkpointing lets us to carry out transactions even if there is a checkpoint in process A fuzzy checkpoint in database systems is a type of checkpointing mechanism that allows the database to record the state of its transactions without needing to bring all database operations to a halt. It's called "fuzzy" because it does not require the system to be in a completely consistent state when the checkpoint is taken. This is in contrast to a strict checkpointing process, where the database must ensure that all transactions are either fully completed or rolled back, and no transaction is in an active state. Here's how a fuzzy checkpoint generally works: The database starts recording the checkpoint by noting the current log sequence number or an equivalent marker. It continues to process transactions, without waiting for ongoing transactions to commit or abort. The database flushes all dirty pages (pages that have been modified but not yet written to disk) to disk. However, it does not necessarily wait for all of these flushes to complete before moving forward with operations. The checkpoint record is written to disk, which includes the state of all transactions that were active at the time the checkpoint began and any other necessary metadata. The database maintains a log of changes that occur after the checkpoint starts. If there is a crash, the database uses the checkpoint and the log to recover. Transactions that were active during the checkpoint and not yet completed will be rolled back using the log to ensure the database's consistency. The advantage of fuzzy checkpoints is that they allow the system to recover to a consistent state more quickly after a crash without imposing a significant performance overhead during normal operations, as they reduce the need for all transactions to reach a commit or abort state before taking a checkpoint. This method is especially beneficial for high-throughput database systems where transactions are constantly occurring, and minimal downtime is critical.

Serializability is a concept in the field of databases, particularly in transaction processing, that ensures the consistency of a database in a multi-user environment. It is the highest level of isolation between transactions and implies that transactions are executed in such a way that they produce the same state of the database as if the transactions had been executed serially, one after the other, without overlapping in time. When multiple transactions are executed concurrently, serializability ensures that their interleaved execution does not leave the database in an inconsistent state or produce results that would be different from those obtained if the transactions were executed one at a time, in some order. There are two types of serializability: Conflict Serializability: A schedule is said to be conflict-serializable if it can be transformed into a serial schedule (transactions ordered one after another) by swapping non-conflicting operations, such as two reads of the same data. Conflicting operations are those that involve at least one write operation on the same data item. A conflict-serializable schedule ensures that the transactions are effectively isolated in terms of their read and write operations on the same data items. View Serializability: A schedule is view-serializable if it results in the same final state of the database as a serial execution would, and if each transaction reads the same initial values as it would in a serial execution. This is a broader condition than conflict serializability, as it allows for more schedules to be considered correct, but it is also more complex to determine. Serializability is important because it simplifies reasoning about the effects of concurrent transactions. It enables users to think as if transactions are being executed one by one, even though in reality, for performance reasons, they are often run concurrently. Database systems use various concurrency control mechanisms, such as two-phase locking (2PL) or timestamp ordering (TSO), to achieve serializability. Different levels of isolation may be offered in practice due to performance considerations, and each level provides a different trade-off between consistency and throughput. Higher levels of isolation (closer to full serializability) typically result in lower concurrency and higher system overhead.

A hash join is a method used to join two tables (or datasets) based on a join key. It is particularly efficient when joining large tables and is designed to be faster than other join methods, like nested loop joins or sort-merge joins, under certain conditions. Here's how a hash join typically works: Partition Phase: The algorithm begins by selecting one of the two tables as the build input, usually the smaller one. It scans this table and applies a hash function to the join key of each row to partition the table into hash buckets. The rows with the same hash value (for their join key) are stored in the same hash bucket. Build Phase: A hash table is built in memory using the hashed join keys from the build input. This hash table maps the hash values to the corresponding rows in the build input. Probe Phase: The algorithm then scans the larger table, known as the probe input. As it reads each row, it applies the same hash function to the row's join key to determine the hash bucket it belongs to. Using the hash value, the algorithm quickly locates the corresponding entry in the hash table created from the build input. If the join key from the probe input matches the join key in the hash table, the algorithm retrieves all the corresponding rows from the build input and combines them with the current row from the probe input to produce the joined rows. The efficiency of a hash join comes from the speed at which rows with the same join key can be found using the hash table, avoiding the need to compare every row from one table to every row from the other table (as done in nested loop joins) or the need to sort the tables (as required in sort-merge joins). However, the effectiveness of a hash join depends on several factors, such as the size of the input tables and the available memory. If the build input is too large to fit into memory, the hash join algorithm may have to use a variant called a "partitioned hash join," which partitions both tables into smaller pieces that can be processed individually in memory.

The slide is discussing a schedule of operations under a concept called Timestamp Ordering (TSO), which is a concurrency control method used in databases to maintain consistency. To determine if the schedule is valid under TSO, we need to consider the rules of TSO and the specific details given in the slide. In Timestamp Ordering, every transaction is given a unique timestamp when it starts. This timestamp dictates the order in which transactions should logically occur, to maintain consistency and serializability. Each data item has a read timestamp (R-TS) and a write timestamp (W-TS) that indicate the timestamp of the latest read and write operations performed on them, respectively.