**Assignments 4 (Due: 02/25), 5 (Due: 02/27), 6 (Due: 03/03) and 7 (Due: 03/05) (all programming-based) posted.**

-----------------------------------------------------

Dr. Meg's Desktop Selected Lecture Videos

-----------------------------------------------------

###
**Syllabus**

**Amanuel Gebre: Mondays, Fridays: 10 AM to 3 PM; Wednesdays: 11 AM to 3 PM**

**Office:** John A. Peoples Building, Room 218

**E-mail:** J00801049@students.jsums.edu** **

###
**Lecture Slides**

Module 1: Algorithm Efficiency Analysis

Module 6: P, NP, NP-Complete Problems

###
**Question Bank**

QB Module 1: Algorithm Efficiency Analysis

QB Module 2 - Classical Design Techniques

QB Module 4 - Dynamic Programming

QB Module 5 - Graph Theory Algorithms

###
**Assignments**

Check Canvas for the timer code.

**Assignment 4 (Programming): Design and Implementation of a Θ(n) Algorithm to Determine the Most Frequently Occurring Integer in an Array of Integers **

Check Canvas for the code.

**Assignment 5 (Programming): Comparison of two Recursive Algorithms to Determine the Minimum Element in an Array**

Check Canvas for the code.

**Assignment 6 ****(Programming): Using the Merge Sort Algorithm to Determine the Number of Inversions and the Inverted Pairs of an Array**

Check Canvas for the code.

**Assignment 7 (Programming): Binary Search vs. Brute Force Search Algorithms for Finding a Local Minimum in a Two-Dimensional Array**

###
**Exams**

###
**Dr. Meg's Desktop Selected Lecture Videos (YouTube Links)**

####
__Module 1: Analyzing the Efficiency of Algorithms__

Time-Complexity analysis of a recursive algorithm to compute the factorial of an integer

Example for solving recurrence relations

Time-complexity analysis of an iterative algorithm to determine whether an array has unique elements

Decrease and Conquer - Insertion Sort Algorithm and Examples

####
__Module 2: Classical Algorithm Design Techniuqes__

Brute Force Algorithms QB - String Matching Problems

Divide and Conquer - Theorem-Proof: In order Traversal of a Binary Search Tree

Divide and Conquer - Master Theorem

Binary Search Algorithm and Examples

Comparison of Bottom-up and Top-down Approaches for Heap Construction

Transform and Conquer - Proof for Euclid's GCD Formula

Transform and Conquer - Heap Sort

Space-Time Tradeoffs for the Sorting Algorithms (Merge, Insertion and Heap Sorts)

####
__Module 3: Greedy Technique__

Greedy Technique - Fractional Knapsack Problem

Greedy Technique - Huffman Codes (Variable Length Prefix-free Encoding)

####
__Module 4: Dynamic Programming__

Dynamic Programming: Coin-row Problem Discussion and Example

Dynamic Programming: Binomial Coefficient

Dynamic Programming Solution for the Coin Collecting Problem in a Two-Dimensional Grid

Dynamic Programming: Integer Knapsack Problem (0-1 Knapsack Problem)

####
__Module 5: Graph Theory Algorithms__

Depth First Search on Directed Graph

Depth First Search and Articulation Points

Breadth First Search and 2-Colorability of Graphs

Topological Sort on DAGs and Proof for Neccessary and Sufficient Condition

Dijkstra's Algorithm for Shortest Path Trees and Proof for Correctness

Bellman-Ford Algorithm for Shortest Path Trees and Examples New!!

Kruskal's Algorithm: Examples to find Minimum Spanning Trees

Kruskal's Algorithm: Proof of Correctness

Properties (1 and 2) of Minimum Spanning Tree: IJ-Cut and Minimum Weight Edge

Prim's Algorithm for Minimum Spanning Trees and Proof for Correctness

**Floyd's All Pairs Shortest Paths Algorithm**

Part 1 Part 2 Part 3 Part 4 Part 5 Part 6 Part 7

####
__Module 6: P, NP and NP-Complete Problems__

Polynomial Reduction: Hamiltonian Circuit to Traveling Salesman Problem

Polynomial Reductions: Independent Set, Clique and Vertex Cover

Multi-fragment Heuristic for the Traveling Salesman Problem