CSCI 3212

Course Description:
This course explores core concepts in design and analysis of algorithms and problem-solving techniques. Hashing, heaps, trees. We explore specific searching, sorting, scheduling and graph algorithms, and classes of algorithms including dynamic programming, greedy algorithms, and an exploration of the equivalence of problem complexity and NP-completeness.
Textbook:
The assigned textbook is "Algorithms", by Jeff Erickson. It is freely available in electronic form. http://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf.
Weekly Topics:
The course will roughly follow this schedule of weekly topics, although I may modify the schedule depending on our progress throughout the semester. In each week we will discuss in depth one chapter of the Erickson Book:
  1. [ 9/1, 9/3] Chapter 0 -- Introduction and algorithmic thinking
  2. [ 9/8, 9/10] Chapter 1 -- Recursion
  3. [9/15, 9/17] Chapter 2 -- Backtracking [Note, this was updated]
  4. [9/22, 9/24] Chapter 3 -- Dynamic Programming
  5. [9/29, 10/1] Chapter 4 -- Greedy Algorithms
  6. [10/6, 10/08] Chapter 5 -- Graph Algorihtms
  7. [10/13, 10/15] Chapter 6 -- Depth First Search
  8. [10/20, 10/22] Chapter 7 -- Minimum Spanning Tree
  9. [10/27, 10/29] Chapter 8 -- Shortest Paths
  10. [11/03, 11/05] Chapter 9 -- All Pairs Shortest Path
  11. [11/10, 11/12] Chapter 10 -- Max Flows and Minimum Cuts
  12. [11/17, 11/19] Chapter 11 -- Applications of Flows and cuts
  13. [11/24] Chapter 12 -- NP-Completeness
  14. [12/01, 12/03] Free Form Algorithm Design Challenges
Additional textbooks and resources
  1. Algorithms. By S.Dasgupta, C.Papadimitriou and U.Vazirani (McGraw-Hill) This is an elegant, small-ish textbook with just the right material for a first course in algorithms. Explanations of algorithmic ideas use excellent examples and proofs are easy to follow. It is not, however, as comprehensive as the one below.
  2. Introduction to Algorithms. T.H.Cormen, C.E.Leiserson and R.L.Rivest. (McGraw-Hill). This book covers much more material than can be handled in a single-semester course. It's advantages are that it makes a useful desktop reference, algorithms are fleshed out in detail with examples and accurate pseudocode, and the book is up-to-date in most areas. Disadvantages: it's bulky, and can initially be intimidating.
  3. The following online lecture notes are also fantastic:
Prerequisites:
CSCI 1311, CSCI 2113.
Learning outcomes:
At the end of this course, student should understand and be able to define paradigms for solving algorithmic problems, including dynamic programming, greedy algorithms, divide and conquer. Given an unfamiliar problem, they should be able to formulate that problem in mathematical terms and to understand which algorithmic paradigms are appropriate to solve the problem. Students should be able to implement an algorithmic approach to a problem, understand the trade-offs that come from choosing different data structures, and be able to formally prove the correctness of their algorithm and to formally evaluate its running time.
Use of Electronic Course Materials and Class Recordings
Students are encouraged to use electronic course materials, including recorded class sessions, for private personal use in connection with their academic program of study. Electronic course materials and recorded class sessions should not be shared or used for non-course related purposes unless express permission has been granted by the instructor. Students who impermissibly share any electronic course materials are subject to discipline under the Student Code of Conduct. Please contact the instructor if you have questions regarding what constitutes permissible or impermissible use of electronic course materials and/or recorded class sessions. Please contact Disability Support Services if you have questions or need assistance in accessing electronic course materials.
University policy on observance of religious holidays
In accordance with University policy, students should notify faculty during the first week of the semester of their intention to be absent from class on their day(s) of religious observance. For details and policy, see: students.gwu.edu/accommodations-religious-holidays.
Academic integrity code
Academic dishonesty is defined as cheating of any kind, including misrepresenting one's own work, taking credit for the work of others without crediting them and without appropriate authorization, and the fabrication of information. For details and complete code, see: studentconduct.gwu.edu/code-academic-integrity
Minimum course load:
In a 15-week semester, including exam week, students are expected to spend a minimum of 100 minutes of out-of-class work for every 50 minutes of direct instruction, for a minimum total of 2.5 hours a week. A 3-credit course includes 2.5 hours of direct instruction and a minimum of 5 hours of independent learning, or a minimum of 7.5 hours per week. More information about GW’s credit hour policy can be found at: provost.gwu.edu/policies-forms
Support for students outside the classroom
Disability Support Services (DSS): Any student who may need an accommodation based on the potential impact of a disability should contact the Disability Support Services office at 202-994-8250 in the Rome Hall, Suite 102, to establish eligibility and to coordinate reasonable accommodations. For additional information see: disabilitysupport.gwu.edu/ Mental Health Services 202-994-5300: The University's Mental Health Services offers 24/7 assistance and referral to address students' personal, social, career, and study skills problems. Services for students include: crisis and emergency mental health consultations confidential assessment, counseling services (individual and small group), and referrals. For additional information see: counselingcenter.gwu.edu/