Midterm questions for CSCI 311 in Java

1. ADT's (Conceptual Models): pre and post conditions, etc. (Intro notes and explicitly here)

2. Analysis of Algorithms: Timing
   1. take a program's code and determine step count to get T(n) ( notes)
   2. get T(n) in "closed-form" (i.e., no summations - just in terms of n) ( might help)
   3. [if needed] prove that our closed-form expression is correct (using induction)

   Know the terms for the various "orders" of complexity; be able to lis them in increasing order of magnitude ( example - notes here)

3. Big Oh, Omega, Theta - determination and verification (do page 125, #'s 9a, 9d and 11a for review)
   Note that for proving inequalities do not hold, it is not sufficient simply to find specific c's and n's that do not work since I may be able to find a c or n that does. Hence, you need to show that sooner or later any choice of c will have a problem. This is usually done by considering the fact that the statement must be true "for all n, n > n₀". Specifically, that n approaches infinity.
   Here are answers but DO NOT LOOK AT THEM UNTIL YOU HAVE TRIED THEM!

4. Recursion: Consider an example for necessary parts of a recursive program

5. Trees: representations and manipulation (representation, traversals, forests, etc.)

6. Binary Search Trees (insert, delete, find, traverse)

Test is open book since we do not have monitors. HOWEVER, it is highly suggested that you make yourself a "cheat sheet" so that you do not waste precious time during the test looking up material. The test is timed - and I did not allow/consider time for you to look things up. Specifically, if you have to look things up you will not have time to finish.

How the tests will be administered

Specifically, you have 2 hours total (from start time of first access to end time of submission). So make sure you have access to a printer to download the test (right button gives print choice), and then be close to a fax or scanner so that you can send me your results within that time.
My fax number is (530) 898-5995.
My email is akeuneke@csuchico.edu if you want to send me a digital copy (I can read .gif (.jpg, .tiff, .png, etc) and also .pdf and .ps files). Our mailer will not accept .zip files so do not try to attach .zip files. Instead, rename the .zip to .jar and send it. I will change the extension back when I get it. Our mailer has no problems with .jars.

I repeat
Even though the midterm is open book and open notes, since it is a timed test, students usually do not have time to look things up if they do not already have some idea about the concepts. I highly suggest that for the test you make up an 8x11 page "cheat sheet". I have found this to be the best way to study since it makes students go through things and think about what is important. Also, in writing it down it helps you realize if you understand it or not and thus study uncertain concepts. Almost always the students with the best cheat sheets do better. Carefully go through the course notes and homeworks.