| Class meeting | 1:00-1:50 MTWF, Austin 306 |
|---|---|
| Instructor | Karl Abrahamson |
| Office | Sci&Tech C-113 |
| Office hours | M–F 11:00-12:00 or by appointment |
| Phone | 328-9689 |
| abrahamsonk@ecu.edu | |
| Course web page | www.cs.ecu.edu/~karl/3300/fall14/ |
| My web page | www.cs.ecu.edu/~karl/ |
| Text | Programming Abstractions in C, by Eric S. Roberts |
| Lecture notes | CSCI 3300 Notes (www.cs.ecu.edu/~karl/3300/fall14/Notes/). |
The prerequisite is CSCI 2310 or equivalent. You should be familiar with the basics of a programming language, such as Java, C++ or C#.
IMPORTANT: This course offers more advanced material on the general topic covered in CSCI 2310, and so, according to university policy, you cannot repeat CSCI 2310 for credit after completing CSCI 3300. If you received a grade of less than C in CSCI 2310, or if you need to retake CSCI 2310 for any reason, do not take CSCI 3300 without consulting me.
The focus of this course is advanced computer programming techniques and algorithms, primarily those that rely on data representation schemes. The language is C++, with emphasis on the C subset. Students are not expected to have used C++ before. Part of this course is an introduction to C++, covering all aspects needed in this course.
This course emphasizes concrete aspects of data structures, also called physical data structures. Data abstraction, the other side of data structures, is emphasized in CSCI 3310, although we introduce some of its most basic ideas in this course.
You will come out of the course able to write working multi-module C++ programs using complex data structures. You should be able to offer arguments concerning the correctness of your programs, and be aware of algorithmic and efficiency issues. For more, see student competencies below.
The following is a partial list of topics to be covered (though not exactly in the order listed).
The C++ programming language. Variables, expressions and statements. Control structures. Functions. Recursion. Types and data, including structures and arrays.
Pointers and memory management. Dynamic memory allocation and deallocation
Physical data structures, including linked lists, trees and hash tables.
Algorithms on physical data structures, including both iterative and recursive algorithms. Correctness and efficiency of algorithms.
Abstract data types.
Designing, understanding, testing and debugging programs.
After successfully completing this course, students will have the following abilities.
There will be a quiz each of the following dates. All are Fridays.
You can bring one prepared 8.5x11" piece of paper, written on both sides, to each quiz. I will not collect those papers.
I will drop your lowest quiz grade and count the remaining six. There will be no makeups for missed quizzes.
The final exam will be at 11:00-1:30 Friday, December 12, in Austin 306. The final exam will cover all of the material for the course. You can bring two prepared 8.5x11" pieces of paper to the final exam.
Grading will be as follows.
| Six quizzes (best of seven) | 36% (6% each) |
| A comprehensive final exam | 20% |
| Eight programming assignments | 35% total. By assignment: (0: 1%) (1: 3%) (2: 3%) (3: 6%) (4: 3%) (5: 6%) (6: 7%) (7: 6%) |
| Attendance | 9% |
You will start with 9 points for attendance and lose one point for each unexcused absence.
Tentative cutoffs for grades will be as follows. These cutoffs will not be raised.
| A | 93% |
| A– | 90% |
| B+ | 87% |
| B | 83% |
| B– | 80% |
| C+ | 76% |
| C | 72% |
| C– | 68% |
| D+ | 64% |
| D | 60% |
| D– | 56% |
|
Important proviso.
It is not possible to learn the material of this course effectively without actually "getting your hands dirty" and doing the programming. Accordingly: In order to pass this course, you must receive at least a 50% grade in the programming assignments.This outweighs the score computed by adding grades together. |
No incompletes will be issued in this course except for extraordinary circumstances, and even then only if you are nearly done already and have done work of acceptable quality, so that it is realistic that you can pass the course. An incomplete will not be given simply because a student could not find the time to do the course work. By registering for this course, you are committing to finding time to do the work.
The programming assignments for this course are probably larger than you have done before. Expect them to take time to complete. If you start on the due date, you will not be able to complete them. Start early, and plan for unexpected difficulties. If you have two weeks to do an assignment, there is a reason. Use the whole two weeks.
I will compile and run programs using the g++ compiler on Linux. I will use the following warning flags when compiling programs:
-g -Wall -Wshadow -OWarning flag -Wall requests all common warnings, including use of uninitialized variables. But you only actually get warnings about uninitialized variables if you also include flag -O, which causes the compiler to optimize code. (Uninitialized variables are detected during dataflow analysis, which is only performed as part of optimization.) Optimized code can be more difficult to debug than unoptimized code. If you intend to use a debugger, your best bet is to compile with -O to get the warnings, but to recompile without -O before you run a debugger.
Each programming assignment is subject to the coding standards for this course. Be sure that you are aware of them. Scores will suffer for programs that fail to meet the standards.
Other than the specific issues listed with each assignment, programs will be graded according to the following broad criteria.
First, the program must compile without fatal errors.
A program that does not compile receives a score of 0, regardless of how close to correct it might be.Never turn in a program that you have not tested on the Linux system with g++.
The program must be acceptably well indented. I need to be able to read your programs, and I will not read a program that is extremely poorly indented.
A program that is extremely poorly indented will receive a failing grade, regardless of how well it performs the task that it is required to do.
The following are broad guidelines for grading. Many programs will not fit exactly into any of these classifications, but I will try to choose the best fit.
To receive an A (90-100), a program should work on all of the test cases that I use. It should be well indented and well commented. Comments should be clear, correct and complete. Every function should have a clear and correct contract. The program should be broken into fairly short, well-thought-out functions. Variable and function names should be sensible. It should follow the coding standards and all guidelines and requirements that have been set for the assignment. It should compile without warnings.
To receive a B (80-89), a program should work on typical test cases, though it might fail on more esoteric cases. It should be well commented and well indented, though minor problems might be present. It should be broken into fairly short, well-thought-out functions, with a contract for each function. It should mostly follow the coding standards and guidelines and requirements that have been set for the assignment, and not make fundamental mistakes that demonstrate that you have not grasped key concepts. The compiler should not report serious warnings that reflect mistakes in the program.
To receive a C (70-79), a program should work on at least some test cases. It must be reasonably commented and indented, though some comments might be misleading or incorrect. It should be broken into reasonable functions. It should make a reasonable attempt to follow the coding standards and guidelines and requirements that have been set out for the assignment.
To receive a D (60-70), a program might not work correctly on any test cases, but the basics of the design must be present. The program should be acceptably well indented. I will not read a program that is very poorly indented. It should make some attempt to follow the coding standards and guidelines and requirements that have been set out for the assignment.
If you turn in a partial program, I will it grade based on roughly what portion has been completed. For example, if you do half of the work, and that half looks good, you might receive a grade of 50%.
With the exception of assignments 0 and 7, you will have an opportunity to turn in two versions of each program. Assignments 0 and 7 only allow one version.
First version (version a) The first version should be a complete, working solution to the problem. It is not a subproblem. You will receive feedback and a grade for it.
Second version (version b). After reading the feedback on the first version, you can submit a second version. It should also be a complete, working version of the program, with mistakes that were pointed out in the first version fixed.
Late submissions for the first version will not be accepted. Late submissions for the second version will be accepted for up to three days after the deadline, with a 5 point penalty (out of 100).
Your score for assignments 0 and 6 will the score for the first (and only) version. For programming assignments that allow two versions, your score will be computed as follows.
Suppose that x is your grade for version a and y is your grade for version b. Then your grade for the assignment is max(x, 0.20x + 0.80y). So if you receive a perfect score for version a, there is no need to turn in version 2, since you cannot improve your grade. If you receive a grade of 90% for version a and 100% for version b, then your score will be 98%. But if you do not turn in the first version, the highest grade that you can receive is 80%, and that requires a perfect version b.
It should be clear that turning in the first version of each assignment is very important to your performance in this course. But there is even more reason for making sure that you turn in a high quality first version.
You will get extensive, timely feedback on first versions. That not only helps you to do an improved second version of that assignment, but it will help you with other assignments.
On second versions, the feeback will less extensive and will be available much later. If you rely on getting feedback on second versions, you will not receive adequate information in time to make necessary improvements on subsequent programs. You will probably end up with a low score on your programming assignments.
Be sure to get to work on the assignments early so that you are able to submit well written first versions.
You are expected to attend class. You are responsible for announcements and assignments given in class. If you miss a class, it is up to you to obtain notes and any other information that was provided in the class. Excuses that you did not know about something because you did not come to class and did not obtain the information will not count for anything at all.
Those who do not attend class can count on doing poorly in this course. If you choose not to attend class, then you must live with the consequences of that decision, however bad they are.
Even if you believe you already know what we are covering, come to class. If you don't, you will end up missing material that you did not know we were going to cover and you will fall behind.
If you are having trouble understanding the lectures, do not stop coming to class. Come to office hours or ask for help from teaching assistants in the lab (Austin 208/209). Get help as early as possible. I don't bite.
Attend class. Arrive on time. Do not skip class either because you think that you already understand the material or for the opposite reason, that you think you cannot get it.
Do not bring distractions to class. If you read your email, listen to music, or engage in other distracting activities during class, you will get very little out of class.
Ask questions in class. If you do not understand something, ask a question about it.
Do not allow yourself to fall behind. Work on the homework early. Do not wait until just before the deadline. If you start to fall behind, work right away to catch up. If you are falling behind because you do not understand something, ask for help. Do not just give up!
Schedule time to work outside of class.
Read the lecture notes twice. Take a break (like a whole day or longer) in between. Work the exercises. Later in the term, go back over notes that you looked at earlier in the term. You will learn much more that way.
Get adequate sleep. Sleep is important both before and after you learn new concepts. Sleep before enables you to concentrate, and sleep afterwards is critical for moving new information into permanent memory.
If you are having trouble, seek help soon. Do not wait until it is too late.
The following schedule lists brief topics along with sections from the lecture notes that cover them. You should read the relevant sections of the lecture notes before the class. Sections in parentheses are important to read but will probably not be discussed in class except to answer questions.
The notes have exercises, with answers. To do well in this course, you will need to do the exercises. Compare your answer to the answer given.
This outline is tentative and might need to be adjusted.
| Date | Topics | Reading |
|---|---|---|
| T. 8/26 | Introduction and general advice. Linux. Compiling and running C++ programs. Assn. 0 assigned. |
(1 introduction) (2 advice) 3.1 Linux 3.2 compiling (3.5 submitting assignments) (6.1 standards: file names) (6.2 standards: file format) |
| W. 8/27 | C++: Expressions and statements. Numeric expressions. Variables and assignment. |
(5.1 discussion of C++) (5.2 C++ comments) 5.3.1 expressions 5.3.2 numeric expressions (5.3.6 precedence) 5.4 statements 5.5 variables (6.4 standards: variables) (6.5 standards: expressions) (6.7.1 standards: statements) |
| F. 8/29 | C++: Boolean expressions. Making decisions. Coding standards. |
5.3.3 boolean 5.6.1 choice |
| M. 9/1 | Holiday | |
| T. 9/2 | C++: More on making decisions. While-loops. Coding standards. Assn. 0 due. |
5.6.1 choice 5.6.3.1 while loops 5.7.1 functions (6.7.2 standards: components of statements) (6.7.3 standards: choice) (6.7.5 standards: commas and gotos) |
| W. 9/3 | C++: Functions. Defining functions. Parameter passing. |
5.7.2 defining functions (6.3 naming functions) (6.4 standards: parameters) |
| F. 9/5 | Quiz 1.. C++: Procedures. |
New: 5.7.4 procedures Review: (5.3.1 expressions) (5.3.2 numeric expressions) (5.5 variables) (5.3.3 boolean) (5.6.1 choice) (5.6.3.1 while loops) (5.7.1 functions) (5.7.2 defining functions) |
| M. 9/8 | C++: Input and output using the stdio library. |
5.9.1 I/O 5.9.2.1 output 5.9.2.3 input (5.9.4 buffering) |
| T. 9/9 | C++: Main function. Documentation: Contracts. Assn. 1 assigned. |
5.7.6 main (4.1 documentation) 4.2 contracts (4.3 other documentation) (6.6 standards: functions) (Assignment 1) |
| W. 9/10 | C++: Scope, frames. Algorithms: recursion. |
5.8 scope 5.7.2 frames 8.3 recursion |
| F. 9/12 | Algorithms: Scan algorithms. Recursive and looping definitions. | 8.5 scan algorithms |
| M. 9/15 | Algorithms: Search algorithms. Recursive and looping definitions. Tail recursion. |
8.4 tail recursion 8.7 search algorithms |
| T. 9/16 | C++: For-loops, breaks, infinite loops. Assn. 1A due. Assn. 2 assigned. |
5.6.3.3 for loops 5.6.3.4 break 5.6.3.5 infinite loops (6.7.4standards: loops) (Assignment 2) |
| W. 9/17 | C++: The memory and pointers. |
5.10.1 memory 5.10.2 pointers |
| F. 9/19 | Quiz 2. |
Review: (4.2 contracts) (5.7.2 defining functions) (8.5 scan algorithms) (8.7 search algorithms) (5.10.1 memory) (5.10.2 pointers) |
| M. 9/22 | C++: Arrays |
5.11.1 arrays 5.11.2 array size |
| T. 9/23 | C++: Two-dimensional arrays. Go over assignment 3. Assn. 2A due. Assn. 3 assigned. |
5.11.7 2d arrays Assignment 3 |
| W. 9/24 | C++: Allocating and deallocating memory. Areas of memory. Dangling pointers. Arrays as pointers. Allocating and deallocating arrays. |
5.10.3 areas of memory 5.10.4 the heap 5.10.5 dangling pointers 5.11.3 arrays as pointers 5.11.5 allocating arrays |
| F. 9/26 | C++: Calling modes. Arrays as parameters. Tracing |
5.7.5 parameter passing 7.5 tracing 5.11.4 arrays as parameters (6.9 standards: tracing) |
| M. 9/29 | Debugging and testing: diagnosis, hand simulation. successive refinement, debuggers. |
7.1 diagnosing errors 7.2 hand simulation 7.4 program development 7.6 using a debugger (7.3 compile errors and warnings) |
| T. 9/30 | System: linking, header files, make. C++: the preprocessor. Assn. 1B due. |
3.3 linking 5.7.3 function prototypes (3.4 make) (5.15 preprocessor) (6.8 standards: preprocessor) (6.10 standards: other) |
| W. 10/1 | C++: Structures. |
5.13.1 structures 5.13.2 using structures |
| F. 10/3 | Quiz 3. |
Review: (5.10.1 memory) (5.10.2 pointers) (5.10.4 the heap) (5.10.5 dangling pointers) (5.11.1 arrays) (5.11.3 arrays as pointers) (5.11.5 allocating arrays) (5.7.5 parameter passing) (5.11.4 arrays as parameters) (5.13.1 structures) (5.13.2 using structures) |
| M. 10/6 | C++: Constructors. Structures as function parameters. |
5.13.3 constructors 5.13.4 structure parameters |
| T. 10/7 | Data structures: Conceptual lists, abstract data types, equations on lists. Assn. 2B due. |
10.1.1 conceptual lists 10.1.2 equations |
| W. 10/8 | Data structures: Linked lists. Functions on linked lists. |
(5.13.5 additional issues on structures) 10.1.3 linked lists 10.1.4 nondestructive functions on linked lists |
| F. 10/10 | Data structures: Looping over linked lists. Destructive operations. |
10.1.6 looping over lists 10.1.7 destructive operations |
| M. 3/13, T. 3/14 | Fall break | |
| W. 10/15 | Assignment 4. Data structures: Priority queues. Assn. 3A due. Assn. 4 assigned. |
Assignment 4 10.3.4 priority queues |
| F. 10/17 | Quiz 4. |
Review: (5.13.1 structures) (5.13.2 using structures) (5.13.3 constructors) (10.1.1 conceptual lists) (10.1.2 equations) (10.1.3 linked lists) (10.1.4 nondestructive functions on linked lists) (10.1.6 looping over lists) (10.1.7 destructive operations) |
| M. 10/20 | Data structures: More on linked lists. Memory sharing. Comparison with arrays. |
10.1.5 memory sharing 10.1.8 comparison |
| T. 10/21 | C++: Characters. Null-terminated strings. String constants. |
5.3.4 characters 5.12.1 strings 5.12.2 string type |
| W. 10/22 | Assignment 5. Assn. 4A due. Assn. 5 assigned. | Assignment 5 |
| F. 10/24 | Algorithms: process, discovery |
8.1 process 8.2 discovery |
| M. 10/27 | Algorithms: Discovery, loop invariants and verification. | 8.6 loop invariants |
| T. 10/28 | Cost: Algorithm analysis, functions, O-notation. |
9.1 analysis 9.2 example (9.3 profilers) |
| W. 10/29 | Data structures: Trees |
10.2.1 trees 10.2.2 trees in C++ 10.2.3 traversing trees |
| F. 10/31 | Quiz 5. |
Review: (5.3.4 characters) (5.12.1 strings) (8.6 loop invariants) (9.1 analysis) (10.2.1 trees) (10.2.2 trees in C++) |
| M. 11/3 | Data structures: Functions on trees. | |
| T. 11/4 | Data structures: Tables, binary search trees. Assn. 3B due. |
10.2.4 tables 10.2.5 binary search trees |
| W. 11/5 | Assignment 6. Assn. 4B due. Assn. 6 assigned. | Assignment 6 |
| F. 11/7 | Data structures: More on binary search trees | |
| M. 11/10 | Data structures: Balanced binary search trees. | 10.2.6 balanced search trees |
| T. 11/11 | Data structures: More on balanced binary search trees. Assn. 5A due. | 10.2.7 implementation |
| W. 11/12 | Data structures: Heaps and priority queues. | 10.3.5 heaps |
| F. 11/14 | Quiz 6. |
Review: (10.2.1 trees) (10.2.2 trees in C++) (10.2.3 traversing trees) (10.2.5 binary search trees) (10.2.6 balanced search trees) |
| M. 11/17 | Data structures: More on heaps. | |
| T. 11/18 | Assignment 7 Assn. 7 assigned. | Assignment 7 |
| W. 11/19 | Algorithms: Sorting. Elementary sorting. A lower bound for sorting. Assn. 6A due. | |
| F. 11/21 | Quicksort. HeapSort. | 10.3.6 heapsort |
| M. 11/24 | Sorting a linked list. | |
| T. 11/25 | Data structures: FIFO queues. |
10.3.1 FIFO queues 10.3.2 linked queues |
| W. 11/26 – F. 11/28 | Thanksgiving break | |
| M. 12/1 | Data structures: More on FIFO queues. |
10.3.3 array queues 5.11.6 reallocating an array |
| T. 12/2 | Data structures: Hash tables with chaining. | 10.4 hash tables |
| W. 12/3 | Data structures: Hash tables with open addressing. Assn. 5B due. | |
| F. 12/5 | Quiz 7. |
Review: (10.3.5 heaps) (10.3.6 heapsort) (10.4 hash tables) (10.1.1 conceptual lists) (10.1.2 equations) (10.1.3 linked lists) 10.1.4 nondestructive functions on linked lists) (10.1.6 looping over lists) (10.1.7 destructive operations) |
| M. 12/8 | Open. Assn. 7 due. | |
| T. 12/9 | Open. | |
| T. 12/10 | Reading day. Assn. 6B due. | |
| F. 12/12 | Final exam, 11:00–1:30. |
You are encouraged to ask questions about your programs when you are stumped, especially if you come up against a difficulty with the C++ language. For example, if you cannot understand why your program gets a compile error, and you are stuck, ask for help. Send questions early, to leave yourself time to make progress after receiving an answer.
A good way to ask questions is by email. Please use a subject indicating that you are asking a question for CSCI 3300, and always include your name in your email. A reasonable subject for a question about assignment 3 is
CSCI 3300 question about assignment 3Please send email to the address listed on the first page of this syllabus. Do not expect immediate answers. Give yourself time to get answers.
If you are asking questions about your program, attach the entire program, including all files. I do not have direct access to your work. Sometimes the real problem is not in the part that you think is at fault. There is no need to explain that what you have sent is incomplete, a work in progress. I know that.
You can feel free to get help from anyone on the following issues concerning programming assignments.
But, other than from the instructor or graduate student tutor, it is considered cheating to obtain assistance for the following.
Never submit someone else's work as your own. That is plagiarism. Do not get a copy of a function definition from someone else and insert it into your program. Violations of these policies will be handled in a manner consistent with official university policy.
Note. To avoid problems with people stealing your work, do not recycle printouts of your program code in a place whether other students can pick them up.
For information about