Computational Structures (2)

Computational Structures

MTH1402 Computational Structures (1)

3 hours No requisites

1 Advanced Graph Theory / Connectivity and graph traversal algorithms: / Depth-First Search (DFS), Breadth-First Search (BFS) / Graph representations: / Adjacency matrices and adjacency lists / Applications: / Shortest path algorithms (Dijkstra, Floyd-Warshall) / Minimum spanning trees (Prim, Kruskal)

2 Trees and Tree Algorithms / Basics: / Properties of trees / Binary trees and traversals (in-order, pre-order, post-order) / Advanced Trees: / Binary Search Trees (BST) / Balanced trees (AVL trees, Red-Black trees) / Applications: / Data storage and retrieval / Syntax trees in compilers

3 Formal Languages and Automata / Formal Languages: / Alphabets, strings, and languages / Operations on languages (union, concatenation, closure) / Finite Automata: / Deterministic Finite Automata (DFA) / Non-Deterministic Finite Automata (NFA) / Equivalence of DFA and NFA / Applications: / Lexical analysis in compilers / String matching algorithms

4 Regular Expressions and Grammars / Regular expressions: / Syntax and operations / Conversion to finite automata / Context-free grammars (CFG): / Parse trees / Ambiguity in grammars / Applications: / Validation of inputs / Compiler design

5 Matrices and Linear Algebra in Computation / Basics: / Matrix operations (addition, multiplication, transposition) / Determinants and inverses / Applications: / Graph algorithms / Transformations in computer graphics

6 Computational Complexity / Big-O, Big-Theta, and Big-Omega notation / Growth of functions and asymptotic analysis / Applications: / Analyzing algorithm efficiency / Problem categorization (P vs. NP)

7 Advanced Topics in Modular Arithmetic / Applications in algorithms: / Modular exponentiation / Modular multiplicative inverse / Cryptographic applications: / Basic understanding of RSA and digital signatures

8 Combinatorics / Basic counting principles (addition and multiplication rules) / Permutations and combinations / Applications: / Algorithm design / Optimization problems

1.1 Mapped to: K1

- Understand advanced graph theory concepts, including traversal algorithms and shortest path algorithms.