Discrete Structure · Unit 10
Advanced Topics
Exam-focused notes for Advanced Topics (Discrete Structure, BIT152): what the TU syllabus asks and how it has actually been tested, with 2 solved past questions from this unit.
What this unit covers
- Boolean matrices and operations
- Randomized algorithms
- Computer arithmetic with large integers
- Modular arithmetic applications
Randomized algorithms
List some advantages of randomized algorithm.Given any set of ten natural numbers between 1 and 99 inclusive, prove that there are two disjoint nonempty subsets of the set with equal sums of their elements.How do you generalize permutations and combinations?[2+4+4]
--- 1. Simplicity: Randomized algorithms are often simpler to design and implement than their deterministic counterparts. 2. Efficiency: They can achieve better average-case time complexity, avoiding worst-case inputs that slow deterministic algorithms. 3. ...
Full solved answer →Boolean matrices and operations
What is Boolean matrix and list its operations?Prove that the sum of first NNN odd integers is N2N^2N2 using mathematical induction.[4+6]
--- A Boolean matrix is a matrix in which each entry is either 0 or 1 (i.e., entries belong to the set {0, 1}). It is also called a zero-one matrix or binary matrix. Example: $$A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{bmatrix}$$ --- Let ...
Full solved answer →Make Unit 10 stick
Practice BIT152 with flashcards & quizzes