CS 3212: Algorithms



Java API

  • What is CS-3212 all about?
    CS-3212 covers core computer science material which, along with the material in CS-3313, constitutes a great deal of the science in computer science. It's hard to imagine an intellectual area that is more central to CS than algorithms. We will study classic algorithms and problems in CS - these algorithms will teach us about key problem-solving techniques such as divide-and-conquer.

  • Who should take this course?
    The course is required for students in the B.S. program. B.A. students are welcome to take the course, as are EMSE students or others who've had the pre-requisites.

  • I haven't taken CS-2113. Can I take this course?
    You will need a working knowledge of objects in Java to handle the programming assignments. And you will need the skill-level that comes with completing CS-2113. Thus, if you've done CS-1112 but not CS-2113 but have had considerable programming experience or other programming courses, you ought to be able to take CS-3212. Talk to me about it.

  • I've taken CS-2113, but in another language. Can I take this course?
    If you're not comfortable with Java, this course might be exceptionally challenging. We are not going to teach Java in the course.

  • Is this a programming-intensive course?
    Yes. Many universities teach their algorithms course without much programming, focusing instead on the mathematical analysis of their complexity. This course, on the other hand, introduces you to algorithmic concepts with a strong focus on implementation, based on the belief that there's nothing like coding an algorithm to force one to understand the details.

  • Is this a math-intensive course?
    Not really. We will only reason about algorithmic complexity at the high-level. There is some math involved in understanding the basic terminology and definitions. Your CS-1311 background is more than adequate for this course.

  • Will I be able to work at home?
    Absolutely. If you have Java working, you can download the test environment (which is itself written in Java) and run that at home.

  • What's covered in the labs? Is attendance mandatory?
    The labs are often for extra help, but we will cover additional, new material as well. We will take attendance, but if you're doing really well in the course, we won't worry about your lab attendance record, except for the new material covered in the lab.

  • What's the difference between an in-class exercise and an exercise with a due date?
    The in-class or module exercises are embedded in the course material (modules), some of which we will try to complete in class. Those that we can't should be done the same day preferably, and will be due soon after the class. You need to keep your answers to the module exercises carefully organized, to be ready to show that you've been keeping up with them. These module exercises will be submitted as zip files through Blackboard. Regular exercises and assignments (described in their own pages) are to be submitted formally using our submission procedure.

  • What does "commitment" mean, and how do I earn those points?
    Experience shows that students who aren't scoring well fall into two categories: those who put in the time (are committed) and those who don't. If you're doing well and are attending and participating in your team, you won't have to worry about these points; you'll get them automatically. If you fall behind but are nonetheless committed (strong attendance in class and lab, strong participation in teams, completing assignments ahead of time, showing up at office hours), you'll get some of these commitment points.

Questions about the (algtest) test environment (for those in the course):
  • I'm unable to compile my code even though the syntax is correct.
    There could be several reasons. Some of the common ones are:
    • The CLASSPATH variable is not properly set to find algtest.jar. Please "echo" (different for Windows vs. Mac/Linux) the CLASSPATH variable to make sure the compiler finds algtest.jar.
    • Your code does not override the methods it needs to. You need to implement all methods in the given interfaces exactly as specified (same method signatures) without adding generics or the "@override" annotation.

  • I get an "unchecked or unsafe operation" warning..
    This sometimes happens when the Java compiler cannot determine whether a template (generic) type matches what's required. It's only a warning and not a compilation error. You can ignore it.

  • The test environment is throwing up an exception. Is there a bug in the test environment?
    Very unlikely. The test environment does throw up exceptions but that's usually because your code returns something wrong or unexpected. For example, consider this typical code:
          => passed: Test1: 1-element test
          => passed: Test2: 2-element test
          Exception caught in testing correctness:java.lang.NullPointerException
    	at edu.gwu.algtest.SearchTester.testCompCorrectness(SearchTester.java:589)
    	at edu.gwu.algtest.SearchTester.testCorrectness(SearchTester.java:831)
    	at edu.gwu.algtest.AlgorithmTest.testCorrectness(AlgorithmTest.java:510)
    	at edu.gwu.algtest.AlgorithmTest.testAlgorithm(AlgorithmTest.java:424)
    	at edu.gwu.algtest.AlgorithmTest.process(AlgorithmTest.java:354)
    	at edu.gwu.algtest.AlgorithmTest.main(AlgorithmTest.java:103)
    Here, a null pointer exception occurs inside the test environment during the third test (the code passed the first two). However, that's because the student's code returned something incorrect in the third test.

  • Yes, but isn't it possible that the bug is in the test environment this time?
    The possibility is quite remote. 15 years of using algtest have revealed very few bugs, and only very estoric cases that involve floating point issues. What is much more common is student confidence in their code.

  • OK, how do I debug if I don't know what the test environment expects?
    You will always know the inputs because your methods are called by algtest. You can always print them out the moment your methods are called. Similarly, you can always see what you return by printing just before every return.

  • Can't algtest tell me all the tests it uses ahead of time?.
    The test environment is deliberately set up to test serially starting with easy tests in the beginning, graduating to harder tests. The goal is to mimic real life when your software undergoes testing by someone else. In fact, a real client is often more vague ("it crashed a few days ago").

  • What do I return if the input is not well formed?.
    Generally, when objects or arrays are returned, return null if the input is inconsistent, empty, or there is nothing to return.