CS 3212: Algorithms

Course overview, policies



About
Announcements
Modules
Coursework
FAQ


Java API

  • Instructor: Prof. Rahul Simha

  • Time/place:
    • Class: Tuesdays/Thursdays 11.10am - 12.25pm, SEH 1300/1400
    • Lab, section 31: Mondays, 6.10 - 7.30, Tompkins 405.
    • Lab, section 30: Tuesdays, 6.10 - 7.30, Tompkins 405.

  • Office Hours: (2nd week onwards)
    • Tuesdays 4.00-5.00pm online.
    Zoom/webex will posted in Blackboard.
    Note: If nobody shows up in the first 10 minutes, the online session will be terminated.

  • TAs: TBD Jie Hou (houjie@) and Ruocheng Shan (shanruocheng@)

  • TA/LA Office Hours:
    • Mondays: 11-12pm on webex
    • Fridays: 2.30-3.30pm on webex

  • Prerequisites: CS-1311 and CS 2113 (or equivalents) - see undergraduate curriculum. Working knowledge of Java.

  • Course description: In this course, students will learn core concepts in algorithms, data structures, and problem-solving techniques. Students will be exposed to classic problems in computer science (such as searching and sorting), classic data structures (hashing, heaps) and classic optimization problems (such as the Traveling Salesman Problem). Students will be encouraged to write clean, efficient code for their assignments. The course will be conducted lab-style with a mix of lecture, lab assignments and projects.

  • Learning outcomes: By the end of this course, students will:
    • Demonstrate understanding of algorithmic specification and pseudocode through implementation.
    • Strengthen some software development skills: writing to specs, testing and debugging.
    • Be able to implement a complex data structure.
    • Be able to implement a complex algorithm.
    • Be able to analyze the execution time of an algorithm
    • Demonstrate, through homeworks and implementations, an understanding of standard topics in algorithms: sorting, searching, trees, hashing, graph algorithms, dynamic programming, combinatorial optimization, NP-completeness, heuristic search.

  • Textbook: The course does not need a textbook because all the needed material is available to you on this site. However, if you'd like to have one, I recommend one of the following OPTIONAL textbooks:
    • 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.
    • 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.
    • Foundations of Algorithms. R.Neapolitan and K.Naimpour (Jones and Bartlett). This book is a compromise between the sweeping coverage of the Cormen book and the tight, condensed Dasgupta book. The book covers some topics, such as backtracking and branch-and-bound, that are hard to find in other books. Overall, a nice book with solid coverage of topics that are well-presented.

  • Programming load: The course will be fairly programming-intensive, comparable with CS-2113 or CS-3411. If you are taking TWO OTHER programming-intensive courses, you could be in for a rough semester. Stop by and discuss the issue with me.

  • Java: The course will make strong use of Java, especially in the assignments. See the CS-2113 homepage for some Java references.

  • Coursework and grading: (Approximate, subject to some change)
    • 800 points: unannounced quizzes.
    • 600 points: commitment (see the FAQ).
    • 1600 points: module exercises (also called in-class exercises)
    • 2000 points: five 1-week exercises (400 each)
    • 3600 points: four 2-week assignments (900 each)
    • 1000 points: exam
    NOTE: the weightage may change depending on how the course evolves.

  • Commitment to this semester: Read and stick to these commitment principles.

  • Submission:
    • All exercises and assignments that have their own webpages (linked to from the coursework page) will be submitted via your Unix accounts. Follow these instructions when submitting work.
    • The module exercises will need to be submitted via Blackboard. Use a single zip file for each module's exercises.
    • All module exercises need to be submitted, regardless of whether they are covered in class, unless otherwise specified (For some modules, the Coursework table will explicitly list exercises.)

  • Late work policy:
    • Every student will get to use four extensions in the semester:
      • A single one-time-use 1-day extension.
      • A single one-time-use 2-day extension.
      • A single one-time-use 3-day extension.
      • A single one-time-use 6-day extension.
    • Each extension can be used only once, and the entire extension will be applied. (That is, you can't submit something three days late, and claim that you've used only part of the 6-day extension.) You do NOT need to tell us you are using an extension, we will merely apply the best fit in the order we get the submissions. You also cannot pick and choose which extension to apply.
    • Using three or more extensions means you forfeit half the commitment points. Thus, only one extension is totally "free".
    • None of the extensions can be applied to the very last assignment (Assignment 4) since we need to have enough time for final grades.
    • Thus, a submission is considered on time if it's submitted by the deadline or if one of the extensions above are applied. Otherwise, it's late.
    • For any exercise that is late inspite of extension, or if extensions are used up, no points will be awarded.
    • For any assignment that is late inspite of extension, or if extensions are used up, points will be taken off as follows: 33% for each 24-hour period after the due date/time. These points will not be pro-rated hourly. Thus, if an assignment is due 5pm Oct 19th, a submission at 5.05pm Oct 19th loses 25 percent.
    • It's best to save the 6-day extension for illness. If an illness requires more than 6 days of recovery during which doing school work is very difficult, a doctor will need to clarify that more than 6 days are needed.

  • Laptop/phone/device policy: You are expected to turn off or silence your phones and other such devices in class. Since all material is available online on this website, there should be no need to take notes on a laptop. Only one laptop per team should be open during class time. All other laptops and devices should be closed during class.

  • Email policy: You can send email to my GW email address or to the TAs. We will answer most class email during specific times set aside during the week for this purpose - so do not expect an instantaneous response. Since this is an advanced class, you may not perform "debugging by email". That is, do not send us code snippets and ask us to identify the problem. If you want us to look at your code, you have to stop by in person during office hours and bring your laptop along. Email is typically used for clarification regarding coursework.

  • Teams and groupwork: See this page

  • Academic Integrity policy:
    • In this course, you will be expected to work on all assigned coursework by yourself, unless otherwise specified by instructions on the course website. If you have any questions whatsoever regarding these policies, see me during office hours.
    • You may not, without permission from the instructor, exchange course-related code with anyone (including anyone not registered in the course), or download code for use in your coursework, or use material from books. Likewise, you may not look at anyone else's code or show your code to anyone else. Protect your work: for example, be careful not to leave your printouts around. The only exception is when team or groupwork is explicitly specified.
    • If using a tutor, you may not show your CS-3212-related code to your tutor nor use code shown or written by your tutor. All tutors for CS-3212 need to first register with me, by meeting me during office hours.
    • If you use material in your assignments that are from outside the course material, then you should be prepared to explain that material. The instructor and TA's reserve the right to question you on your use of extraneous material. Failure to answer such questions might be viewed as grounds for an integrity violation.
    • The Academic Integrity Code or Student Conduct Code will apply to this course. Please read through the code carefully.
    • Penalties for violating the code or the policies described here include failing this course, and are elaborated in the Academic Integrity Code.

  • If you have a disability that may effect your participation in this course and wish to discuss academic acommodations, please contact me as soon as possible.

  • Directory structure on your laptop:
    • Create a directory (folder) called cs3212 off of your home directory. All your course materials, programming assignments and in-class exercises will be inside this folder.
    • Under cs3212, create one folder for each module, such as module1, module2 ... etc. Inside module1 is where you will have your answers to the in-class exercises for Module 1.
    • You will similarly create folders for the assignments and exercises as we proceed in the course.

  • Coding standards:
    • Having completed CS-2113, you are expected to submit well-written code:
      • Include high-level documentation.
      • Comments must be substantive and must follow pseudocode where appropriate (more about this later).
      • Select readable variable names and method names.
    • Use consistent Java style:
      • Consistent indentation (preferred: two or four spaces).
      • Variable and method names start lowercase.
      • Class names start uppercase.
      • Capitalize multi-word names instead of using underscores.
    • You will learn to write efficient code in this course, but also need to pay attention to the three golden principles of coding: simplicity, clarity and generality.
    • Points may be taken off for "ugly code" even if correct and efficient.

  • GW's emergency preparedness guide.

  • 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

  • Statement on inclusive teaching. It is my intent that students from all backgrounds and perspectives be well-served by this course, and that the diversity that the students bring to this class be viewed as a resource, strength and benefit. Your suggestions are encouraged and appreciated. Please let me know ways to improve the effectiveness of the course for you personally, or for other students or student groups.