The exam will be on

Monday, 9 May 2005, 10:30 am - 1:15 pm.

• 4 quizzes, including "topics" and answers.
• 2 exams, including reviews and answers.
• 14 recitations.
• 27 links to "lecture topics".

Many of these items will also be mentioned below.

No question will come directly from the Weiss book that is not also discussed below. (But the Weiss book might help your understanding.)

Unix:

1. Unix Basics Know all the commands given.
2. vi Editor Know the 18 emphasized commands.
3. lint/make Know how to compile, how to invoke lint, and the basics of the make utility. (Not emphasized.)

C Basics:

4. dice program Study this program and be familiar with:
   • The basic structure of a C program:
     • #include lines, to include header files
     • #define lines, to define constants (among other uses)
     • global variable definitions
     • list of prototypes of functions
     • list of definitions of functions, including perhaps a main function
   • How to write an array as a formal parameter in C.
   • Simple array allocation in C as a local variable inside a function (not possible in Java).
   • Basics of the printf function.

5. Rec 1: Introduction Study the dice.c program.
6. C I/O: (The final link to self-reproducing programs discussed later.)
7. Random Numbers: just the first (introductory) section.
8. Rec 2: Input/Output and Random Numbers.
9. Separate Compilation: Understand the use of separately compiled files in C with header files.
10. Sieve: Study the comparison and contrast between the C program in 3 files and the Java program in 2 files:
    • The C program has a header file included in each of the two other source files to insure compatibility and to allow separate compilation. Java doesn't use these header files (except in interfaces), and one can't compile the file with the main function without compiling the other one.
    • Each Java file has code buried within a class, and C has nothing like this.
    • A number of other differences outlined in the web page.

11. Stack: This is a 3-way comparison, but questions will be about the C version of a stack.
12. O-O Prog: Pay special attention to the table that describes how
    • In C one can use separate files to enable O-O programming.
    • Alternatively, one can use C structures to fake O-O programming.
13. Copy: These character-by-character copy programs are needed for Recitation 3, but it is important to see how C uses getchar() and a test for EOF to copy a file. To copy line-by-line, just realize that in C files appear as if lines are separated from one another by a single newline character.
14. Rec 3: Palindromes.

C Pointers (same as Java references):

15. Pointers Basic pointer notation and concepts, including especially the "address of" operator & and the "dereferencing" operator *. The star is also used to declare pointers. Also the material in the table titled "Pointer examples: pointers.c".
16. Swapping Mainly just the second example titled "C Swap Program with Pointers -- Works" that shows a function that will interchange the values stored at the referenced locations of two pointer parameters.
17. Rec 4: Pointers, etc.
18. Pointers and Arrays All of this, with emphasis on the section "Indexes versus pointers for arrays in C". (Not much emphasis on the large section titled "Array Basics (lecture notes by Mike Maltrud)", since it is mostly standard array material that is the same in C and in Java.)
19. Rec 5: Pointers and Arrays

Strings:

20. String Examples Creating strings, accessing and printing chars from them
21. String Basics (less emphasis on this material)
22. String Functions Examples of functions that work with strings
23. Rec 6: Strings

24. Print Array of Strings
25. Rec 7: Array of Strings : command line arguments (skip self-reproducing programs)
26. Array of Strings as Parameter (less emphasis)

27. 2d-arrays
28. Rec 8: Pascal's Triangle : 2-dimensional arrays -- three ways to look at them:
    • Represented as a single sequence of locations in memory.
    • Represented as an array of pointers to 1-dimensional arrays.
    • In the recitation, simulating a triangular array as a sequence of memory locations.

29. Structs Overview
30. Simple "bare" structs seldom used
31. Rec 9: Structs and RPN Using bare structs, and an array of structs
32. Java vs. C Using pointers (or references) to structs
33. Structs as parameters Examples of both "bare" structs and pointers to structs

34. Linked List Stack Use of self-referential structs
35. Rec 10: Linked list queue

36. File Input/Output
37. Rec 11: Merging Files

Binary trees:

38. Rec 12: Binary trees

39. Rec 13: Hashing

40. Rec 14: Graph algorithms

41. Time in Unix (No questions on this)

42. Heapsort

Please consult this location over the next few days for sample problems.

1. C macros (with #define): possible question.

2. Pointers: some kind of question.

3. Strings: some kind of question. Study mallocing storage for a string.

4. Arrays of strings: Possible question, such as, say, "print an array of strings, one to a line, without using square brackets".

5. 2-dimensional arrays: Probably a question. Understand the two different kinds of 2-dimensional arrays:
   • Ordinary 2-dimensional arrays, either declared as a[5][4]; or malloced as a 1-dimensional array and simulated.
   • Array of pointers to 1-dimensional arrays. Often created with malloc but does not have to be: The array of pointers to 1-dimensional arrays is created on the right side of 2d-arrays without using malloc. Problem 3 of Exam 2 answers shows the creation of an array of pointers to array using only malloc for storage allocation.

6. structs: some kind of question. We used an arrays of structs and an array of pointers to structs. Understand the contrast with arrays:
   • An array variable name always gives the address of the array, so that an assignment a = b would assign the address of b to a, except that arrays are constants and can't assigned to. This assignment is possible if one declares the array as a pointer to the type of the array.
   • A struct variable name refers to the actual "bare" struct. If you want the address of the struct, you need an explicit pointer to the struct. An assignment a = b would assign the contents of struct b to struct a. Usually one works with pointers to structs, passing a pointer and returning a pointer from a function.

7. Linked lists: Probably a question. Understand code to chase down a linked list to the NULL at the end, using code like: while (p != NULL) { /* do something */ p = p -> next;}, where p points to the first node of the linked list. This trashes the pointer p, since it will have value NULL at the end. See the function printstack2 in Linked List Stack.

8. File Input/Output: possible question.

9. Merge files: possible question.

10. Binary search trees: perhaps one question. You should understand how binary search trees work.

11. Hashing: definitely one question. Understand both methods: open addressing and bucketing, though the recitation used open addressing.

12. Graphs and graph algorithms: definitely one question. Be sure to study the adjacency list representation and how to construct it as in Recitation 14:. You should also check out Question 30 in the course list of Questions.

13. Time: No question about time in Unix.

14. Heapsort: definitely one question, perhaps just tracing through the actions of heapsort. For practice, try using the following numbers (where A[0] is not used) (answer is here):

    
    int A[] = {0, 5, 13, 2, 25, 7, 17, 20, 8, 4};