Project 7 deadline extended to Nov. 15th, 11.30 AM.
Project 8 is also due on Nov. 15th, 11.30 AM. There will NOT be any extension for Project 8.
Quiz 6 (Take Home) posted. Due on Nov. 13th, 11.30 AM (hardcopy in class)
Exam 3 posted. TAKE HOME. Due in class on Nov. 29th @ 11.30 AM. Late submissions WILL NOT be accepted.
Quiz 7 (in-class) on Nov. 27th @ 11.30 AM. CLOSED NOTES.
—————————————————–
Dr. Meg's Desktop Selected Lecture Videos
Quiz, Exam and Project Schedules
—————————————————–
Syllabus
Teaching Assistant
Lecture Slides
Module 1: Algorithm Efficiency Analysis (Last Updated: Sept. 6th)
Module 2: Divide and Conquer (Last Updated: Sept. 12th)
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
Project Descriptions
Project 1: Brute Force Algorithm for the Element Uniqueness Problem (Due: Sept. 20th, 11.30 AM)
Project 2: Implementation and Performance Comparison of the Bubble Sort and Insertion Sort Algorithms (Due: Sept. 27th, 11.30 AM). Check Canvas for sample code (to use time functions in C++/Java)
Project 3: Algorithm to Determine the Longest Subsequence of Consecutive Integers in an Array using Hash tables, its Optimization and the Analysis of the Space-Time Tradeoff (Due: Oct. 4th, 11.30 AM). Check Canvas for sample code and startup code
Project 4: Recursive Algorithm to Find the Minimum Integer in an Array and its Space-Time Tradeoff Performance Comparison Analysis with an Iterative Algorithm (Due: Oct. 11th, 11.30 AM)
Project 5: Dynamic Programming Algorithm for Optimum Coin Collection in a Two-Dimensional Grid (Due: Oct. 18th, 11.30 AM)
Project 6: Dynamic Programming-based Solution for the Longest Common Subsequence Problem (Due: Nov. 1st, 11.30 AM)
Project 7: Dynamic Programming-based Solution for the Coin Change Problem (Due: Nov. 8th, 11.30 AM). Check Canvas for the startup code
Project 8: Number of Walks of certain Length between any Two Vertices (Due: Nov. 15th, 11.30 AM). Check Canvas for the startup code
Quizzes and Exams
Quiz 2 (Take Home) (Due: Sep. 25th, 11.30 AM)
Quiz 3 (Take Home) (Due: Oct. 9th, 11.30 AM)
Quiz 4 (Take Home) (Due: Oct. 16th, 11.30 AM)
Quiz 5 (Take Home) (Due: Oct. 30th, 11.30 AM)
Exam 2 (Take Home) (Due: Nov. 6th, 11.30 AM)
Quiz 6 (Take Home) (Due: Nov. 13th, 11.30 AM)
Exam 3 (Take Home) (Due: Nov. 29th, 11.30 AM)
Code Tutorial
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
Quiz, Exam and Project Schedules
