December 2009
3 posts
Final Exam Key
Here is the key for the final exam.
Final Exam Information
Our final exam is scheduled (by vote of the class) for 2:00-5:00pm this upcomng Saturday, December 5th.
Here is a study guide for the final exam.
Here are the keys for all of the normal (non-makeup) tests: Test 1, Test 2, Test 3
Here are the keys for all of the homeworks: Homework 1, Homework 2, Homework 3, Homework 4, Homework 5
Wednesday, 12/02/2009 Notes
In lecture today, the following topics were covered:
Answering of questions about lab 11, including the meaning of deep & shallow copy
Discussion of the use of stacks in evaluating postfix expressions and in translating infix expressions to postfix expressions
Here is the code for a postfix evaluator, using the Stack code from Monday: PostfixEvaluator.cpp
Here is a PDF with the powerpoint...
November 2009
18 posts
Lab 11 (Continued): 11/30/2009
The lab for today is to continue working on Lab 11 (originally assigned on 11/16). It is due on Wednesday, 12/2 at 5:00pm.
Monday, 11/30/2009 Notes
In lecture today, the following topics were covered:
General definitions of 2 new linear data structures, Stacks and Queues, and discussion that these data structures are essentially restrictions on how additions and deletions are defined for a container.
Definition of common Stack operations
A discussion of implementing Stack operations using an array and using a LinkedList (LinkedList being...
Monday, 11/23/2009 Notes
In lecture today, the following topics were covered:
Test 3 was handed back and reviewed. The key will be posted here soon.
A few variations of LinkedLists were discussed, such as Circular Linked Lists, Tail-Pointer Based Linked Lists, and Doubly Linked Lists (using prev and next pointers in each Node).
Friday, 11/20/2009 Notes
In lecture today, Test 3 was taken.
Wednesday, 11/18/2009 Notes
Here are documents helpful for reviewing for the upcoming test, which is to be held this Friday, November 20th:
Homework 5 Key
Test 3 Study Guide
Test 3 Practice Problems
Monday, 11/16/2009 Notes
In lecture today, the following topics were covered:
the LinkedList destructor
the utility of re-using other methods (such as deleteFirst() in the destructor)
the idea of iterators
the beginning of a class definition for a LinkedList iterator
Source code for the iterator will be uploaded over the next few days.
Lab 11: 11/16/2009 and 11/30/2009
The lab for this week is to implement a string-data LinkedList container. You are not required to use templating.
Here are the lab documents:
Lab 11 description document
Lab 11 gradesheet
Planned due date for this lab is Wednesday, December 2nd at 5:00pm.
Friday, 11/13/2009 Notes
In lecture today, the following topics were covered:
A review of homework 4. Here’s the key in PDF format.
A discussion of the addAtFront, addAtBack, deleteAtFront, and deleteAtBack operations on LinkedLists. Key ideas are 1) correct management of the head pointer and 2) how to traverse down the nodes
Here are up-to-date LinkedList and Node files: LinkedList.h, LinkedList.cpp, Node.h,...
Wednesday, 11/11/2009 Notes
In lecture today, the following topics were covered:
definition of the data that compose the Node and LinkedList classes
the core methods of the Node class (constructor, get/set data/next)
friend classes
templated classes - useful for building containers
the LinkedList addFront operator
Example code will be posted soon for friend classes, templated classes, and LinkedList operations (as we...
Monday, 11/9/2009 Notes
In lecture today, the following topics were discussed:
the schedule for lab over the next few weeks (operator overloading today, LinkedLists on the 16th and 30th, no lab on the 23rd)
the overloaded subscript [] operator
a debate over whose responsibility it is to handle erroneous inputs into methods
an introduction to the idea of linked lists
Here are powerpoint slides covering the material...
Lab 10: 11/9/2009
Here are the documents for Lab 10. This lab will cover operator overloading for the Vector class developed in Lab 9. I plan to have Lab 9 graded this week so you can integrate cleaning up any mistakes before Lab 10 is due.
Lab 10 description (now available)
Lab 10 gradesheet
Expected due date for this lab is Sunday, November 15 at 9:00pm.
Friday, 11/6/2009 Notes
In lecture today, the following topics were covered:
a decision to move the final exam to Saturday, December 5th, 2:00pm
the intricacy of overloading the assignment operator
l-values and r-values
the similarity of the assignment operator and copy constructor
the necessity of correctly managing dynamic memory allocation in the assignment operator
overloading the output operator
Here are the...
Homework #4
Here is Homework #4, with the planned due date being the start of class, Wednesday 11/11/2009: CSC112Homework4.pdf
This homework deals with designing classes and operator overloading.
Wednesday, 11/4/2009 Notes
In lecture today, a number of topics were covered, all under the general idea of “operator overloading” for classes:
the idea of operator overloading for classes
the notion of operator?? methods being built into our classes
the syntax for operator overloading in .h and .cpp files
the notion that we must choose semantics (meaning) for operator overloading (sure, I can use == on...
Monday, 11/2/2009 Notes
In class today, the following topics were covered:
Review of Test #2 — here is the key: Test2Key.pdf
Discussion of the date for the final exam - please email me when you are not available
Discussion of makefiles - an example makefile has been posted in the Lab 9 post
Lab 9: 11/2/2009
Here are the documents for lab 9:
Lab 9 document (PDF file)
Lab 9 gradehsheet (PDF file)
Example makefile for Rectangle class: makefile
Anticipated due date for this lab is Sunday, November 8th at 9:00pm.
October 2009
17 posts
Friday, 10/30/2009 Notes
In lecture today, the following topics were covered:
continued discussion of the header and cpp files for classes in C++
the notions of abstraction and encapsulation
the compilation process for classes
private and public attributes for variables/methods
the special functions: constructors, destructors
Here is the complete set of files for the Rectangle class we developed in class:
- the...
This guy, not Al Gore, invented the Internet... →
Some interesting thoughts on the Internet and computers presence in our lives from one of the “fathers” of the Internet
Wednesday, 10/28/2009 Notes
In lecture today, the following topics were covered:
Brief discussion of labs 7 (searching sequence database) and lab 8 (maze searching)
The idea of classes as complex user-defined types and objects as instances/variables of that type
The notion that in defining classes one must define both the variables that compose the class and the operations legal on the class (these operations are both...
Lab 8: 10/26/2009
Here are the documents for lab 8:
Lab 8 description document (PDF)
Lab 8 gradesheet (PDF)
Lab 8 program skeleton - lab8.cpp (use this as the basis for your work)
As indicated in an email on Sunday night, I will not be available during the lab but will be afterwards. Nicholas Mertaugh, one of the graduate student TAs, will be present from 4:30pm until 5:15 and knows what the lab is about and...
Friday, 10/23/2009 Notes
In lecture today, the following topics were covered:
A brief bit on advising
Review of Homework #3 - here’s the key: CSC112Homework3Key.pdf
Review for Test #2, which is on Monday. Here are a study guide and some practice problems from old exams. Here are the answers to the practice problems.
Wednesday, 10/21/2009 Notes
In class today, the following topics were covered:
a derivation of why mergesort is O(n*log2(n))
the notion behind function templating in C++ and why templating can be useful
syntax for templating
examples of using templating to “abstract algorithms” such as binarySearch and mergeSort
limitations on templating - that to use a type with a templated function, all operations...
Schedule for Upcoming Weeks
Monday, 10/19/2009 - Homework 3 posted, Lab 7 posted and started
Wednesday, 10/21/2009 - Normal lecture class (finish up sorting)
Thursday, 10/22/2009 - Submit Homework 3 by 5:15pm so I can grade it and discuss it on Friday
Friday, 10/23/2009 - Lecture period is review for Test 2, review of Homework
Monday, 10/26/2009 - Test 2 during lecture period, Start Lab 8 (a new lab) during lab
...
Monday, 10/19/2009 Notes
In lecture today, we covered the following topics:
Moved the test from this Friday to next Monday, 10/26/2009 - it will cover (primarily) recursion, searching, and sortin
Reviewed homework 2. Here is the key: CSC112Homework2Key.pdf
Agreed that a homework 3 will be posted tonight and be due later in the week (I am planning on Thursday, 5:15pm so I can grade them before Friday)
Traced the...
Lab 7: 10/19/2009
Here are the documents for lab 7:
Lab 7 description document (PDF)
Lab 7 gradesheet (PDF)
Database and update files: largeDatabase.txt, largeUpdate.txt
Protein sequence files: H1N1Protein.txt
New functions to revise lab5: lab5Updates.cpp
New functions to use if desired in lab 7: lab7HelperFunctions.cpp
My lab 5 solution: lab5_turkett.cpp
A clean and update on the large database and the...
Wednesday, 10/14/2009 Notes
In lecture today, the following topics were covered:
insertion sort - another O(n^2) sort [worst case], but which performs better on many datasets and which employs shifts instead of swaps
a comparison of standard searching costs vs. sorting and binary searching costs
introduction of merge sort - a recursive O(n log2(n)) sort where most of the work is in merging two smaller ordered lists into a...
Monday, 10/12/2009 Notes
In class today, the following topics were covered:
a discussion of homework question 4, wherein I want you to focus on how many items do you have to look at
a discussion of other measures of efficiency (other than just time): space and energy
an implementation of binary search that is iterative in nature
the definition of the sorting problem, and the terms ascending/descending
the algorithm...
Friday, 10/9/2009 Notes
In class today, we discussed the following topics:
Answering of questions about the lab
Review of Homework #1
Discussion of computational complexity (Big Oh == worst case)
Discussion of computational complexity for front-to-back searching and binary search (O(n) vs O(log2(n))
Here’s the second homework, due Wednesday, 10/14 at the start of class: CSC112Homework2.pdf
Here’s the...
Wednesday, 10/7/2009 Notes
In lecture today the following topics were covered:
a brief review of tail recursion and the benefits of tail recursion
discussion of the searching problem (findInArray)
discussion of searching in a sorted list (such as the phone book) and the possible costs of searching
introduction of the binary search algorithm and a recursive implementation of binary search
Here’s an implementation...
Monday, 10/5/2009 Notes
In lecture today the following topics were covered:
a program that exhibits infinite recursion, causing a stack overflow error
the definition of tail recursion and a discussion of the potential benefits of tail recursion
examples of re-writing two recursive methods using tail recursion - fibonacci, factorial
discussion of how tail-recursive methods can be translated fairly easily into...
Lab 6: 10/05/2009
Here are the documents for lab 6:
Lab 6 description document (PDF, now available)
Lab 6 gradesheet (PDF)
This lab requires writing four small programs, each of which involves a recursive approach to solving a problem.
The planned due date for this lab is Sunday, October 11th at 9:00pm.
Friday, 10/2/2009 Notes
In lecture today, the following topics were covered:
more examples of simple recursion (sum of 1..n, findInArray, fibonacci)
ways of looking at arrays recursively (splitting into head, tail; front,back)
the possibility for >1 base case and/or >1 recursive call
three steps to verify a recursive solution
a continued debate over recursion’s simplicity in writing/reading vs it’s...
Wednesday, 9/30/2009 Notes
In class today, we covered the following:
Review of Test 1 answers
Introduction to the idea of recursion
September 2009
19 posts
Monday, 9/28/2009 Notes
In lecture today, we had Test 1. I plan to have the tests graded and back by Wednesday’s class (which is the drop date). Then we will start on the topic of recursion.
Lab 5: 9/28/2009
Lab 5 and the remaining labs will have a new deadline: Sunday night, 9:00pm.
Here are the required documents for lab 5:
Lab 5 description document (PDF)
Lab 5 grade sheet (PDF)
Here are the required and helpful files for lab 5:
lab5.cpp (shell of program)
sampleDatabase_10_5.txt - Example database file, consisting of 10 length-5 segments; includes repeats so most useful for testing...
Friday, 9/25/2009 Notes
In class today, we reviewed for the upcoming test (Monday, 9/28/2009).
The primary questions asked were:
syntax for dynamic allocation (creating and deleting) of multi-dimensional arrays
meaning of pointer addition
Wednesday, 9/23/2009 Notes
In lecture today, we covered the following topics:
an overview of the GDB gnu-debugging tool. A short manual of the basic keywords/functionality has been added to the left hand toolbar.
Discussion of the notion of char* C-strings (char arrays ended with a null character ‘\0’)
Writing two functions that deal with C-strings - string length (strlen) and string equal
Noting the useful...
Helpful Programming Ideas: #2
Think, use, and re-use patterns.
Much of the process of programming can be described by patterns of syntax. By recognizing these patterns, you can get into habits that reduce the amount of work you do and may help remove some inadvertent errors. Here are two patterns:
By now, you have probably written the same lines to start off a program several times (the #include<iostream> to the int...
Monday, 9/21/2009 Notes
Today’s lecture covered the following topics:
full looping syntax for dynamic allocation and deletion of multi-dimensional arrays
a discussion of the ability to now create arbitrarily shaped (instead of rectangular) arrays (useful for symmetric matrices among other situations)
a discussion of the notion that dynamic allocation does not guarantee contiguous memory locations across memory...
Lab 4: 9/21/2009
Here are the required documents for lab 4:
Lab 4 description document (PDF)
Lab 4 grade sheet (PDF)
Here are the required files for lab 4:
Everything in one file: lab4Source.tar.gz (does not contain PDFs)
Separately: lab4.cpp (shell of program), ppmb_to_ppma.cpp (binary to ASCII ppm converter program), jpeg2ppma.sh (jpeg to ppma converter script), drfulp.ppma (example image #1), drjohn.ppma...
Friday, 9/18/2009 Notes
In lecture today, we covered the following topics:
review of the memory leak problem and definition of the dangling pointer problem
dynamic memory allocation for arrays, and the corresponding delete requirements
dynamic memory allocation and deletion for multi-dimensional arrays (requiring loops)
pointers as first class types, including their use as parameters and return types
how passing a...
Wednesday, 9/16/2009 Notes
In class today, we continued with the lab from Monday. We agreed to extend the due date of the lab until next Monday (9/21/2009).
A regular class will be held on Friday (more on pointers).
Monday, 9/14/2009 Notes
In lecture today, the following topics were covered:
when one can and can’t use slices (subarrays) of a multi-dimensional array
the pointer data type
how pointers relate to addressing and the addressing operator (&)
the notion of dynamic memory allocation
how memory from the stack is different from memory from the heap
the operators used for dynamic memory allocation (new,...
Lab 3: 9/14/2009
Here are the documents for Lab 3:
Lab 3 description document (PDF format)
Lab 3 gradesheet (PDF format)
You will also want to download the following files:
Grab a bundle which has everything, including the PDFs above: lab3.tar.gz
Or individually download:
Sound library (see lab PDF on how to include these with your code when compiling): header file sound.h, library file lsound.o
Support...
Friday, 9/11/2009 Notes
In class today, the following topics were covered:
Another looping example, solving the isPrime problem using a for loop
Example programs demonstrating array addressing and arrays as parameters to functions
Discussion that variables, including arrays, in C++ were not initialized by default
The notion that it is possible to allocate a particular sized array (give it a capacity) but use less...