Design & Analysis of Algorithms

Analysis and Desgin of Algorithms

CS2105 Data Structures & Algorithms with Java

3 hours One requisite

1 Introduction to algorithm behavior and complexity analysis: / Case behaviors (best, worst, average), and asymptotic analysis of upper and expected complexity bounds: Big O Notation, Big Omega, and Big Theta notations (Principles, Examples, and Comparisons), and space complexity analysis. / Analysis of iterative and recursive algorithms by introducing algorithms with various time and space complexities such as constant, logarithmic, linear, quadratic, and exponential. / Algorithm performance comparison: comparison of sorting algorithms, and discussion on memory vs. speed trade-offs. / Recurrence relations, and solving recurrence relations including substitution method, recursion tree method, and master method

2 Algorithm paradigms: / Recursive Backtracking: Principles and applications (e.g., N-Queens problem, Maze-solving algorithms.)

3 Algorithm paradigms: / Divide-and-Conquer Algorithms: Principles and applications (e.g., strassen's algorithm for matrix multiplication, and review of binary search, and quick sort algorithms)

4 Algorithm paradigms: / Randomized Algorithms: Principles and applications (e.g., Explore Randomized Quicksort, and Quickselect)

5 Algorithm paradigms: / Greedy Algorithms: Principles and applications (e.g., interval scheduling, coin change, Huffman coding for compression, greedy Knapsack problem)

6 Algorithm paradigms: / Dynamic Programming: Principles of optimal substructure and overlapping subproblems (e.g., Fibonacci sequence [naïve vs. dynamic], longest common subsequence, maximum sum subarray “Kadane's algorithm”, 0/1 Knapsack problem)

7 Graph Algorithms: / Greedy Algorithms: (e.g., Minimum Spanning Tree (MST): Prim's and Kruskal's Algorithms, and Dijkstra’s shortest paths) / Dynamic Programming: (e.g., Bellman-Ford shortest paths, Floyd–Warshall algorithm) / Heuristics Algorithms: (e.g., A* search algorithm)

8 String-Matching Algorithms: include naïve, memorazion and dynamic Algorithm paradigms. (e.g., Naive approach, Knuth-Morris-Pratt (KMP) algorithm and Boyer-Moore algorithm)

9 Algorithm paradigms: / Heuristic Approaches: Discussion on approximate solutions: (e.g., Travelling Salesman Problem (TSP), Graph coloring)

10 Complexity Classes: Explore key concepts including P, NP, reductions, NP-hardness, and NP-completeness

1.1 Mapped to: K1

Define and describe the fundamental concepts of algorithms and their importance in computational problem-solving.

Teaching Strategy Lectures with real-world examples and discussions.

Assessment Methods Quizzes, exams.

1.2 Mapped to: K2

Explain algorithm efficiency using asymptotic notations and identify common running time complexities.

Teaching Strategy Group discussions, and case studies.

Assessment Methods Homework, final exam.

1.3 Mapped to: K1

Illustrate the concept of NP-completeness and its significance in computational theory.

Teaching Strategy Case studies, guided discussions, and examples.

Assessment Methods Final exam, quizzes.

2.1 Mapped to: S1

Analyze and compare algorithms based on time and space complexity.

Teaching Strategy Problem-solving sessions, practice-based learning.

Assessment Methods Midterm exams, assignments.

2.2 Mapped to: S2

Design efficient solutions using advanced algorithmic techniques, including divide-and-conquer, randomized algorithms, and dynamic programming.

Teaching Strategy Collaborative algorithm design exercises.

Assessment Methods programming tasks and performance evaluation through quizzes.

3.1 Mapped to: V1

Engage in lifelong learning

Teaching Strategy Assignments

Assessment Methods Assignments

Assessment	Weight





Assignments	20%
Quizzes	20%
Mid Term	20%
Final Exam	40%
Total	100%

Official government website of the Government of Kingdom of Saudi Arabia

Link to official Saudi websites end with edu.sa

Government websites use the HTTPS protocol for encryption and security.

Welcome

Login with National Single Sign-On

Design & Analysis of Algorithms

Design & Analysis of Algorithms

Search in the Site