• Class Time: Thursdays 12:45 pm - 3:15 pm,
• Class Location: Tomkins Hall of Engineering 206

• Name: Timothy Kim
• Email: timothyk at gwu.edu
• Office Hours: By appointment only

• https://github.com/GWU-KIM-CSCI/6212-Fall-2015

• Optional: "Introduction to Algorithms (Third Edition)" Cormen, Leiserson, Rviest, Stein - The MIT Press

• 30% - Quizes
• 35% - Closed-book Midterm
• 35% - Closed-book Final
• 5% - Optional Project

There will be homework assignments every week. However, they are not graded. They are purely optional. However, I highly recommend doing them. It will greatly help you towards the midterm and final. The answers to the homework will be posted week before the midterm and the final. Homework will be posted on the website.

No make-up exam/quiz will be given except for documented illness or personal emergency. The instructor must be notified at least day PRIOR to the scheduled exam time in order for a make-up exam to be granted. A 15-minute quiz will be given at the beginning of class (12:45-1:00pm). You should arrive in class on time. No make up for missed quizes.

Lecture slides will be posted to the website prior to each lecture.

Schedules are subject to change

• Week 1 (09/03/2015) - Intro/Bound Theory
• Week 2 (09/10/2015) - No Class
• Week 3 (09/17/2015) - Divide and Conquer (quiz)
• Week 4 (09/24/2015) - Divide and Conquer
• Week 5 (10/01/2015) - Greedy Algorithms (quiz)
• Week 6 (10/08/2015) - Greedy Algorithms
• Week 7 (10/15/2015) - Graph Theory / Review (quiz)
• Week 8 (10/22/2015) - Midterm
• Week 9 (10/29/2015) - Dynamic Prgoramming
• Week 10 (11/05/2015) - Dynamic Prgoramming (quiz)
• Week 11 (11/12/2015) - Backtracking/Branch and Bound
• Week 12 (11/19/2015) - Theory of Computation (quiz) / Review
• Week 13 (11/26/2015) - No Class (Thanksgiving)
• Week 14 (12/03/2015) - Final Exam

1. Introduction
2. Bound Theory/Asymtotic Notation
3. Data Structures
4. Divide-and-Conquer
5. The Greedy Method
6. Dynamic Programming
7. Graph Algorithms
8. Theory of Computation

• Stacks
• Queue
• Binary Trees
• Graph
• Heap
• Disjoint Set (Union/Find)

• Min-Max
• Mergesort
• Quicksort
• Selection Algorithm
• Matrix Multiplication

• Selection sort
• Optimal Merge Patterns
• Knapsack
• Minimum spanning tree (shortest path)
• Mean Retrieval Time

• Principle of Optimality
• Matrix Chain
• All-Pairs Shortest Path
• Optimal Binary Search Tree
• Traveling Salesman

• Binary Tree Traversal
• Depth First Search
• Breadth First Search
• Biconnectivity

• 4-Queens Problem
• Sudoku

All graded work must be completed in accordance with GW Code of Academic Integrity and CS Department Policy on Academic Integrity. http://www.cs.seas.gwu.edu/academics/integrity/cs_integrity