CSCI 2310/2311 Fall 2007

Announcements

The final exam will be December 10 from 2:00 to 4:30 in Austin 304. You can use two prepared 8.5x11 pieces of paper. The questions will be similar to those that were on the quizzes. You can obtain all of the quizzes below.

Syllabus

This is an introductory computer programming course. See the syllabus for details.

Office hours

MW 12:30-2:00 and TTh 11:00-12:00.

Lab and help hours

Lab assistants are available during certain hours for assistance.

Self-test exercises

1. [8/22/07] Course introduction and syllabus. We began to look at expressions involving integers and real numbers.

2. [8/27/07] We covered material on naming and types, and began looking at functions. Reading:

3. [8/29/07] Quiz. We talked about unit testing and contracts for functions, then looked at boolean expressions and defining functions by cases. Reading:

4. [9/5/07] We looked more at making decisions, then turned to function definitions that use recursion. Reading:

5. [9/10/07] We did the gcd example shown in the notes on Recursion, then began looking at computing with commands. In the lab, students worked on lab assignment 2. Almost all students struggled on the second function, sumDivisorsRange. I have added another page on problem solving to the notes that hopefully will help in writing sumDivisorsRange and similar functions. Reading:

6. [9/12/07] Today's quiz was postponed to Monday. We reviewed problem solving and did some more examples. Most of what we talked about is in

7. [9/17/07] Quiz. We continued to look at computing with commands, including the material from following notes.

8. [9/19/07] We will look at search and scan algorithms. Reading:

9. [9/24/07] We looked at lists and strings, and some algorithms on lists and strings. Reading:

10. [9/26/07] Quiz. We continued to look at lists and aggregates of data.

11. [10/1/07] We looked at the problem of sorting a list, and developed and wrote the quicksort algorithm.

12. [10/3/07] We started making the transition from Cinnameg to Java. Reading:

13. [10/8/07] We will continue to look at Java. Reading:

14. [10/17/07] We looked at objects, classes, instance variables and instance methods in Java.

15. [10/22/07] We looked at programming assignment 7, and discussed more about objects in Java.

16. [10/24/07] Quiz. We looked at arrays in Java.

17. [10/29/07] We looked at the assignment, the skyline problem. We explored arrays more in Java.

18. [10/31/07] We looked at the problem of searching an array. Algorithms include linear search (look at everything) and, when the array is already sorted, binary search, which successively divides the array in half. If there are n things in the array then linear search takes time proportional to n in the worst case, but binary search takes time proportional to log2(n).

19. [11/5/07] We looked at the edit distance problem.

20. [11/7/07] Quiz (on arrays). We went over the quiz.

21. [11/12/07] We looked at some concepts of object-oriented programming, including elementary inheritance and polymorphism.

22. [11/14/07] This was a review day, concentrating on how to approach and solve simple problems that involve writing function or method definitions.

23. [11/19/07] We looked at in-place sorting and the insertion sort algorithm, which takes time proportional to n2 to sort an array of n things.

24. [11/26/07] We continued to look at in-place sorting, and looked again at the Quicksort algorithm. We implemented quicksort, but did not look at the issue of how much time it takes to sort an array of n things.

25. [11/28/07] We did an analysis of quicksort. We also demonstrated that any algorithm that sorts by doing comparisons must do at least log2(n!) comparisons to sort an array of n things, which is close to nlog2(n) comparisons.