| Class meeting |
1:00–1:50 MTuWTh MW Brewster C-103 TuTh Brewster D-203 |
|---|---|
| Instructor | Karl Abrahamson |
| Office | Sci&Tech C-113 |
| Office hours | MWF 10:00–10:50 and MW 2:00–3:15 or by appointment |
| Phone | 328-9689 |
| abrahamsonk@ecu.edu | |
| Course web page | www.cs.ecu.edu/~karl/2530/fall16/ |
| My web page | www.cs.ecu.edu/~karl/ |
| Text (recommended) | Programming Abstractions in C, by Eric S. Roberts |
| Lecture notes | CSCI 2530 Notes (www.cs.ecu.edu/~karl/2530/fall16/Notes/). |
This class will interfere with your social life. It will cut into your leisure time.
You will need to read the lecture notes and work the exercises in the lecture notes to be successful. Plan to spend significant time each week outside of class reading, working the exercises and doing the assignments for this course. The amount of time that you need to spend will depend greatly on how efficiently you work, and that will depend largely on whether you follow the instructions. If you cannot commit adequate time to this course, I recommend that you drop the class.
I will show you how to work efficiently. In the past, many have ignored my advice (and even their own reasoning) and used methods that are proven time wasters. Hopefully, this class will do better. Here are a few things that you should do and things to avoid.
Do.
Read the notes. Do the exercises in the notes. The exercises will help you to remember what you read and understand what you are doing when you work on assignments.
Start to work on assignments early.
Write sensible, concise and precise documentation in your programs early. Do not try to keep information about what a function does only in your head. Writing it down forces you to make your thoughts precise, and that is crucial. It also is very valuable when you come back to your work. You will have forgotten things, and you do not want to spend time reverse-engineering what you wrote earlier.
Follow sound debugging procedures, as explained in class. Put useful traces in your program. Learn how and when to use a debugger.
Proofread what you write.
Draw pictures of data structures that you use. You cannot keep them in your head.
Ask questions when you are stuck. Do not just give up. Do not spend a lot of time trying to figure out one small issue.
Do not.
Do not wait until the due date to start an assignment.
If your program does not work, do not try random experimentation to try to get it work. That will waste your time as you make your program further and further from correct.
If you start late, you will be tempted to turn in someone else's work. Do not plagiarize work, regardless of how tempting it is.
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 2530. 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 2530 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 or 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.
For many of you, the material in this course is the closest you will come to machine language, an important topic for software developers to understand. This course therefore concentrates on the C subset of C++, with only a few features of C++ used. We will not use C++ libraries such as the Standard Template Library. We will see how things are done at a level close to machine architecture without relying on others do have implemented the ideas for us.
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).
Basics of the C subset of C++. 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 and components of programs.
After successfully completing this course, students will have the following abilities.
There will be 7 quizzes, on the following dates.
Each quiz will take somewhat over half of the class period. After the quiz, I will go over it.
There will be no makeups for missed quizzes.
You can bring one prepared 8.5x11" piece of paper, written on both sides, to each quiz. You can write anything that you like on that paper. I will not collect it.
I will drop your lowest quiz grade and count the remaining 6.
The final exam will be at 11:00-1:30 Friday, December 9, in Brewster C-103. 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.
Grades will be computed as follows.
| Grading | |
|---|---|
| 6 quizzes (best 6 of 7) | 33% (5.5% each) |
| A comprehensive final exam | 23% |
| Nine programming assignments | 35% total. By assignment number: (0: 1%) (1: 3%) (2: 3%) (3: 3%) (4: 3%) (5: 3%) (6: 6%) (7: 6%) (8: 7%) |
| Attendance | 9% |
You will start with 9 points for attendance and lose one point for each unexcused absence. I will base attendance not only on what I record in class but also based on whether you took a quiz and on whether you were present to pick up a quiz when it was returned.
Tentative cutoffs for grades will be as follows. These cutoffs will not be raised.
| Grade cutoffs | |
|---|---|
| A | 93% |
| A– | 90% |
| B+ | 87% |
| B | 83% |
| B– | 80% |
| C+ | 76% |
| C | 72% |
| C– | 68% |
| D+ | 64% |
| D | 60% |
| D– | 56% |
| IMPORTANT |
|---|
|
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% overall grade in the programming assignments.This supersedes 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 are available from the course web page.
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.
I will compile and run programs using the g++ compiler on Linux. I will use the following flags when compiling programs:
-g -Wall -Wshadow -Wuninitialized -OI strongly suggest that you test your programs using the same compiler with the same flags.
Students who do inadequate testing can expect low grades.
Never make a modification, no matter how trivial, without testing your work before submitting it.
Grading of submissions is explained in the notes. Read that page about how programs will be graded so that you are aware of expectations.
An important point concerns programs that do not compile without fatal errors. I expect you to write working computer programs. I expect you to test your programs on several inputs. If your program does not compile, I know that you have not tested it even once. Accordingly,
| IMPORTANT |
|---|
| A program that does not compile without fatal errors receives a grade of 0, regardless of how much work you have put into it or of how close it is to working. |
Plagiarism of programming assignments is a serious problem. Never submit someone else's work as your own. Do not get a copy of a function definition from someone else and insert it into your program. You are expected to do all of your own work. If your submission is 50% your work and 50% someone else's work, then your work is considered to be plagiarized.
| IMPORTANT |
|---|
|
If I believe that you have submitted plagiarized work,
you will receive a grade of −50 points on
that assignment.
Yes, your points will be negative. If you share your work with another student, expect that student to submit your work with his or her name on it. That has happened many times. Both of you will receive a score of −50. |
If I say that your assignment is plagiarized and you do not agree, you are welcome to discuss it with me to explain the circumstances.
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.
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 choice, 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.
Attend class. Arrive on time.
Do not bring distractions to class. If you read your email, listen to music, send and receive text messages or engage in other distracting activities during class, you will get very little out of class. That will show up in your grade.
Ask questions in class. If you do not understand something, ask a question about it.
Ask questions outside of class. Your best bet is to use email. If you have a question about an assignment, attach all of your files to the email message. Do not just copy the part that you think is wrong into the email message. Failure to attach all relevant files will lead to a delay in getting a response as I need to ask you to send the files. Ask questions early. Do not wait until the last minute.
Please use a subject indicating that you are asking a question for CSCI 2530, and always include your name in your email. A reasonable subject for a question about assignment 3 is
CSCI 2530 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.
Schedule time to work outside of class.
Do not allow yourself to fall behind. Work on the assignments 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!
Read the lecture notes twice. Take a break (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 think clearly, and sleep afterwards is critical for moving new information into permanent memory.
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.
Quiz dates list review material for the quiz. You should be able to understand what each quiz will cover based on that review material.
This outline is tentative and might need to be adjusted, based on how many questions there are and on how quickly we are able to cover topics.
| Date | Topics | Reading | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| M. 8/22 |
Assignment 0 assigned. Introduction: Syllabus. General advice. Grading of programming assignments. Avoiding the swamp. C, C++, Java and Smalltalk. |
|
||||||||||||||||
| Tu. 8/23 |
System: System: Linux, NX, ssh. C/C++ and machine language. Compiling and running C++ programs. Grading and standards: Grading of assignments. Coding standards. Braces. How to work assignments. |
|
||||||||||||||||
| W. 8/24 |
C++: Numeric expressions and types. Numeric Constants. Numeric operators. Operator precedence. Statements Variables and assignment. Abbreviations for assignments. |
|
||||||||||||||||
| Th. 8/25 | C++: Scope Boolean values and expressions. Comparisons. Converting from English to boolean expressions If-statements. Compound statements. Indentation. Coding standards for if-statements. Watch out: semicolons. |
|||||||||||||||||
| M. 8/29 |
Assignment 0 due. Functions. Defining functions. Using functions. Definition order. Standards for function definitions. Function names. Function contracts. Characteristics of Contracts. |
|||||||||||||||||
| Tu. 8/30 |
C++: While loops. Functions with loops. Hand-simulating loops. Static properties of loops. Watch out: semicolons |
|
||||||||||||||||
| W. 8/31 |
C++: For-loops. Standards for for-loops. Breaking out of loops. The main function. |
|
||||||||||||||||
| Th. 9/1 | Quiz 1. |
Review: (work all of the exercises!) |
||||||||||||||||
| M. 9/5 | Holiday | |||||||||||||||||
| Tu. 9/6 |
Assignment 1 assigned. C++: Procedures. Input and Output using the stdio library. |
|
||||||||||||||||
| W. 9/7 |
C++: Function calls and frames. Algorithms: Recursion. |
|
||||||||||||||||
| Th. 9/8 |
C++: Elementary arrays. Algorithms: Scan algorithms with loops. Search algorithms with loops. |
|
||||||||||||||||
| M. 9/12 |
Algorithms: Scan algorithms with recursion. Search algorithms with recursion. Tail recursion. |
|
||||||||||||||||
| Tu. 9/13 |
Assignment 2 assigned. C++: Parameter passing. Call by value and call by reference. Algorithms: More examples. |
|
||||||||||||||||
| W. 9/14 |
Assignment 1 due. Algorithms: Algorithm development. Top-down design. |
|
||||||||||||||||
| Th. 9/15 | Quiz 2. |
Review: (work all of the exercises!)
|
||||||||||||||||
| M. 9/19 |
C++: The memory and pointers. Operations on pointers. Areas of memory. Limitations of the run-time stack |
|
||||||||||||||||
| Tu. 9/20 |
C++: Allocating and deallocating memory in the heap. Dangling pointers. Memory faults. Memory leaks. |
|
||||||||||||||||
| W. 9/21 |
Assignment 2 due. C++: Arrays. Arrays as pointers. Arrays as parameters. Const parameters. Allocating and deallocating arrays. |
|
||||||||||||||||
| Th. 9/22 |
Assignment 3 assigned. Assignment 3. C++: Header files. Linking. Function prototypes. |
|
||||||||||||||||
| M. 9/26 |
More on assignment 3. C++: Array size. Pointer arithmetic. Characters. Null-terminated strings. String constants. |
|
||||||||||||||||
| Tu. 9/27 |
C++: Operations on null-terminated strings. Enumerated types. |
|
||||||||||||||||
| W. 9/28 |
C++: Structures. Operations on structures. Constructors. Passing structures to functions. |
|
||||||||||||||||
| Th. 9/29 | Quiz 3. |
Review: (work all of the exercises!)
|
||||||||||||||||
| M. 10/3 |
Assignment 3 due. Assignment 4 assigned. C++: Parameterless constructors. Arrays of structures. Assignment 4. Data structures: Graphs. Representing a graph as an array of edges. Kruskal's algorithm. |
|
||||||||||||||||
| Tu. 10/4 |
Data structures: Abstract data types. Conceptual lists. Operations on conceptual lists. Equations on lists. |
|
||||||||||||||||
| W. 10/5 |
Data structures: Linked lists. Functions on linked lists. Converting equations to C++. |
|
||||||||||||||||
| Th. 10/6 |
Data structures: More on linked lists. Memory sharing. Looping over linked lists. |
|
||||||||||||||||
| M. 10/10 and Tu. 10/11 | Fall break | |||||||||||||||||
| W. 10/12 |
Data structures: Destructive operations on linked lists. Comparison with arrays. |
|
||||||||||||||||
| Th. 10/13 |
Assignment 5 assigned. Assignment 5. |
|
||||||||||||||||
| M. 10/17 |
Assignment 4 due. Data structures: Implementing abstract data types. Shrink-wrapping priority queues. |
|||||||||||||||||
| Tu. 10/18 | More examples using linked lists. |
|
||||||||||||||||
| W. 10/19 |
Assignment 6 assigned. Assignment 6. Algorithms and data structures: Simulation. Events and the event queue. Representing a graph using an adjacency list. |
|
||||||||||||||||
| Th. 10/20 |
Quiz 4. Assignment 5 due. |
Review: (work all of the exercises!)
|
||||||||||||||||
| M. 10/24 |
Debugging: Tracing. Controlling tracing. Using gdb. |
|
||||||||||||||||
| M. 10/25 |
Data structures: FIFO queues. Represention schemes for a FIFO queue. |
|
||||||||||||||||
| W. 10/26 |
Algorithm analysis: Algorithm analysis. Big-O and big-Θ notation. Logarithms. |
|
||||||||||||||||
| Th. 10/27 |
Data structures: Trees. Functions on trees. |
|
||||||||||||||||
| M. 10/31 |
Data structures: More examples with trees. Traversing a tree. |
|
||||||||||||||||
| Tu. 11/1 |
Assignment 6 due. Assignment 7 assigned. Assignment 7. |
|
||||||||||||||||
| W. 11/2 |
Data structures: Tables and sets. Examples of representations of tables and sets. Binary search. |
|
||||||||||||||||
| Th. 11/3 | Quiz 5. |
Review: (work all of the exercises!)
|
||||||||||||||||
| M. 11/7 |
Data structures: Binary search trees. Operations on binary search trees. |
|
||||||||||||||||
| Tu. 11/8 |
Data structures: Height-balanced binary search trees. Rotations. |
|
||||||||||||||||
| W. 11/9 |
Assignment 8 assigned. Assignment 8. Huffman trees. |
|
||||||||||||||||
| Th. 11/10 |
Data structures: Why do rotations work? When and where to do rotations. Cost of operations on height-balanced binary search trees. |
|
||||||||||||||||
| M. 11/14 |
Assignment 7 due. Data structures: Hash tables with chaining. |
|
||||||||||||||||
| Tu. 11/15 |
Algorithms:
Sorting. Naive sorting. Analysis of naive sorting. |
|||||||||||||||||
| W. 11/16 |
Algorithms: Sorting a linked list using MergeSort. Analysis of MergeSort. |
|
||||||||||||||||
| Th. 11/17 | Quiz 6. |
Review: (work all of the exercises!)
|
||||||||||||||||
| M. 11/21 |
Data structures: Heaps and priority queues. Operations on heaps. |
|
||||||||||||||||
| Tu. 11/22 |
Algorithms: HeapSort. Building a heap Analysis of HeapSort. |
|
||||||||||||||||
| W. 11/23 to F. 11/25 | Thanksgiving break | |||||||||||||||||
| M. 11/28 |
Review: Equations on linked lists. |
|
||||||||||||||||
| Tu. 11/29 |
Algorithms: Quicksort. |
|||||||||||||||||
| W. 11/30 |
Assignment 8 due. Algorithms: Improving quicksort. A lower bound for sorting. |
|||||||||||||||||
| Th. 12/1 | Quiz 7. |
Review: (work all of the exercises!)
|
||||||||||||||||
| M. 12/5 |
Review. Arrays. Null-terminated strings. |
|
||||||||||||||||
| Tu. 12/6 | Reading day. | |||||||||||||||||
| F. 12/9 | Final exam, 11:00am–1:30pm, Brewster C-103 | |||||||||||||||||
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.
For information about
please see the auxiliary information at http://www.cs.ecu.edu/~karl/2530/fall16/syllabus-aux.html.