CSC 323 Algorithm Design and Analysis, Spring 2018

Exam 3 (Take Home; Due on April 24th at 1 PM; submit in my office, ENB 275)

Reading List for Quiz 7 (in class Quiz, Closed Notes, on April 17th)

Projects 6 – 8 posted. Check in Canvas.
See Canvas.

—————————————————–

Syllabus

Lecture Slides

Question Bank

Project Descriptions

Quizzes and Exams

Code Tutorial

Dr. Meg’s Desktop Selected Lecture Videos

Quiz, Exam and Project Schedules

—————————————————–

Syllabus

CSC323 Syllabus, Spring 2018

Lecture Slides

Module 1: Algorithm Efficiency Analysis (Updated – version #4. Right click and Reload your page to get the latest version)

Module 2: Divide and Conquer
(Updated – version #1. Right click and Reload your page to get the latest version)

Module 3: Greedy Strategy

Module 4: Dynamic Programming(Updated – version #2. Right click and Reload your page to get the latest version)

Module 5: Graph Algorithms

Module 6: P, NP, NP-Complete Problems

Question Bank

QB Module 1: Algorithm Efficiency Analysis

QB Module 2 – Classical Design Techniques

QB Module 3 – Greedy Strategy

QB Module 4 – Dynamic Programming

QB Module 5 – Graph Theory Algorithms

Project Descriptions

Project 1: Brute Force Algorithm for Element Uniqueness Problem (Due by: Feb. 8th 1 PM)
Check Canvas for Startup Code

Project 2: Implementation and Performance Comparison of the Bubble Sort and Insertion Sort Algorithms (Due by: Feb. 15th, 1 PM)

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 by: March 1st, 1 PM)
Check Canvas for Sample Code on Hashtables and a Startup Code for the Project

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 by: March 8th, 1 PM)

Project 5: Dynamic Programming Algorithm for Optimum Coin Collection in a Two-Dimensional Grid (Due by: March 29th, 1 PM, Submission in Canvas)

Project 6: Dynamic Programming-based Solution for the Longest Common Subsequence Problem (Due by: April 5th, 1 PM, Submission in Canvas)

Project 7: Use the Results of Depth First Search to Assign Directions to an Undirected Graph and Obtain a Directed Acyclic Graph (DAG) (Due by: April 12th, 1 PM, Submission in Canvas)

Project 8: Use the Results of Breadth First Search to Extract the Shortest Paths from a Particular Vertex to the Rest of the Vertices in an Undirected Graph (Due by: April 19th, 1 PM, Submission in Canvas)

 

Quizzes and Exams

Quiz 5 (Programming Quiz: Take Home): Implementation of the Greedy Algorithm to Determine an Optimal Allocation of Files in a Tape to Minimize the Average Cost to Access the Files, Due on March 27th @ 1 PM (Submission through Canvas)

Exam 2 (Take Home): Due on March 20th @ 1 PM, in class

Exam 1 (Take Home): Due on Feb. 20th @ 1 PM, in class

Quiz 3 (Take Home): Due on Feb. 27th @ 1 PM, in class

Quiz 4 (Take Home): Due on March 6th @ 1 PM, Submit in Canvas

Quiz 5 (Take Home): Due on March 27th @ 1 PM, Submit in Canvas

Quiz 6 (Take Home): Due on April 3rd @ 1 PM (Hard copy in class)

Code Tutorial

 

Basics of Vector Class

Populating a 1-dim and 2-dim Array with Elements in Random Order chosen from a Vector that has the Elements in Sequential Order

 

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

Time-Complexity analysis of a recursive algorithm to determine the number of bits needed to represent a positive integer

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

Properties (3 and 4) of Minimum Spanning Tree: A graph with unique edge weights has only one minimum spanning tree

Property 5 of Minimum Spanning Tree: Given a graph with unique edge weights, the largest weight edge in any cycle cannot be part of any minimum spanning tree

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

Minimal Number of Uncovered Neighbors Heuristic: Example to determine an Independent Set, Vertex Cover and Clique

Polynomial Reductions: Independent Set, Clique and Vertex Cover

Multi-fragment Heuristic for the Traveling Salesman Problem

Twice around the tree Heuristic for the Traveling Salesman Problem and the Proof for approximation ratio

 

 

 

Quiz, Exam and Project Schedules