CSC 323 Algorithm Design and Analysis, Fall 2016

Exam 3 (Take Home Part) posted. Click here. Due on: Dec. 6 @ 9 AM  in Room ENB 212.

Exam 3 (In-class Part) Reading List posted. Click here.

Exam 3 (In-class Part) will be on Dec. 6 @ 9 AM in Room ENB 212.

Quiz 8 (Take Home) posted. Due on: Dec. 1 @ 11.30 AM.   NO late submissions!

TERM PROJECT PRESENTATION SCHEDULE

 

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

Syllabus
Lecture Slides
Question Bank
Project Descriptions
Term Project
Quizzes and Exams
Code Tutorial
Dr. Meg's Desktop Selected Lecture Videos
Quiz, Exam and Project Schedules

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

Syllabus

CSC 323 Syllabus, Fall 2016

Lecture Slides

Module 1: Algorithm Efficiency Analysis

Module 2 – Classical Design Techniques

Module 3: Greedy Strategy

Module 4: Dynamic Programming

Module 5: Graph Algorithms

Module 6: NP-Complete Problems and Heuristics

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: Element Uniqueness Problem, Due: Sept. 29

Project 2: Iterative vs. Recursive Algorithms to Compute the Factorial of an Integer, Due: Oct. 13

Project 3: Binary Search vs. Brute Force Search Algorithms for Finding a Local Minimum in a Two-Dimensional Array, Due: Oct. 27

Project 4: Optimum Coin Collection in a Two-Dimensional Grid, Due: Nov. 17

 

Term Project

Term Project Descriptions and Team Assignments

Team 1: Algesa Haywood Jr., Brian Williams, Michael D. Moore

Team 2: Kabinad Melaku, Kirubel Benalfew, YosefGetachew

Team 3: Karmeen Powell-Childress & Deonta Kilpatrick

Team 4: Quavanti Hart, Nicholas Whitfield, Alishia Harmon

Team 5:  Darius Leroy, Ladarius Felix, Shawndon Portis

 

 

 

Quizzes and Exams

Quiz 1 Solutions

Quiz 3 (Take Home): Due on Oct. 4 at 11.30 AM

Quiz 4 and Bonus Quiz 1 (Take Home): Due on Oct. 11 at 11.30 AM

Quiz 6 (Take Home; Due: Oct. 25 @ 11.30 AM)

Exam 2 (Take Home; Due: Nov. 1 @ 11.30 AM)

Quiz 7 (Take Home: Due on Nov. 10 @ 11.30 AM)

Quiz 8 (Take Home) posted. Due on: Dec. 1 @ 11.30 AM

 

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 (Chapter 2): 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    

Module 2 (Chapters 3-6): Classical Algorithm Design Techniuqes

Brute Force Algorithms QB – String Matching Problems

Decrease and Conquer – Insertion Sort Algorithm and Examples

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 (Chapter 9): Greedy Technique

Greedy Technique – Fractional Knapsack Problem

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

Module 4 (Chapter 8): 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