| Class meeting | 1:00–1:50pm MTWF, Austin 302 |
|---|---|
| Instructor | Karl Abrahamson |
| Office | Sci&Tech C-113 |
| Office hours | MTWF 2:00–3:00 and Tu 11:00–12:00 or by appointment |
| Phone | 328-9689 |
| abrahamsonk@ecu.edu | |
| Course web page | www.cs.ecu.edu/~karl/3200/fall15/ |
| My web page | www.cs.ecu.edu/~karl/ |
| Text (recommended) | Data Structures: Abstraction and Design Using Java, by Elliot B. Koffman and Paul A. T. Wolfgang |
| Lecture notes | CSCI 3200 Notes (www.cs.ecu.edu/~karl/3200/fall15/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 about 10 hours per week outside of class working on reading and assignments for this course. The amount of time that you need to spend will depend on how efficiently you work. 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.
Follow sound debugging procedures, as explained in class. Put useful traces in your program.
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.
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 somewhat familiar with the basics of a programming language, such as Java, C++ or C#. The course will contain a review of Java.
| 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 3200. 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 3200 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 Java.
This course emphasizes concrete aspects of data structures, but covers some abstract data types and object-oriented programming. We concentrate in how to use data structures, with a little bit on how to implement them.
You will come out of the course able to write working Java programs using elementary 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 Java programming language. Variables, expressions and statements. Control structures. Functions. Recursion. Types and data, including structures and arrays.
Arrays and linked lists.
Algorithms on physical data structures, including both iterative and recursive algorithms. Correctness and efficiency of algorithms.
Abstract data types and object-oriented programming.
Designing, understanding, testing and debugging programs.
After successfully completing this course, students will have the following abilities.
There will be 12 quizzes, on the following dates.
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 two quiz grades and count the remaining 11.
The final exam will be at 11:00am-1:30pm Friday, December 11, in Austin 302. 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 | |
|---|---|
| Eleven quizzes (best of 12) | 33% (3% each) |
| A comprehensive final exam | 24% |
| Seven programming assignments | 34% total. By assignment number: (0: 1%) (1: 4%) (2: 4%) (3: 4%) (4: 7%) (5: 7%) (6: 7%) |
| 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.
| 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 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 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.
Grading of submissions is explained in the notes. Read that page about how programs will be graded so that you are aware of expectations.
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.
Attend class. Arrive on time.
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. 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. Ask questions early. Do not wait until the last minute.
Please use a subject indicating that you are asking a question for CSCI 3200, and always include your name in your email. A reasonable subject for a question about assignment 3 is
CSCI 3200 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 (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.
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 |
|---|---|---|
| M. 8/24 |
Introduction. Syllabus. General advice. Java. |
(1. Introduction) (2. Advice) (5.1. Discussion of Java) |
| T. 8/25 |
System: Linux. Logging in. Compiling and running Java programs. Submitting assignments. Assn. 0 assigned. |
3.1. Logging in 3.2. Basic Linux 3.3. Compiling and running Java programs (3.4. Submitting assignments) |
| W. 8/26 |
Java: Numeric expressions and types. Precedence. Variables and assignment. Abbreviations for assignments. |
5.3.1. Expressions 5.3.2. Numeric expressions 5.3.5. Precedence 5.6. Variables |
| F. 8/28 |
Statements and sequencing. Boolean values and expressions. Comparisons. If-statements. |
5.5. Statements 5.4.3. Boolean values and expressions 5.7.1. Making decisions |
| M. 8/31 |
Java: Compound statements. Indentation. Coding standards for if-statements. Defining and using static methods. |
6.9.2. Standards: Components of statements 5.8.1. Static methods 5.8.2. Defining static methods (6.1. Standards: Motivation) (6.8.1. Standards: Statements) (6.8.3. Standards: Conditionals) (6.3. Standards: Variable and method names) (6.4. Standards: Variables and parameters) |
| T. 9/1 |
Java: Procedures. The main method. Output. Input. |
5.8.3 Procedures 5.8.4 Main 5.8.5 Java programs 5.10.1. Standard input and standard output 5.10.2. Output 5.9.2.3. Input |
| W. 9/2 |
Documentation: Contracts. Review. Assn. 0 due. |
5.2. Java comments 4.2. Contracts (4.1. Documentation) (4.3. Other documentation) |
| F. 9/4 |
Quiz 1. Javadoc. |
Review: 5.4.1. Expressions 5.4.2. Numeric expressions 5.4.3. Boolean values and expressions 5.6. Variables 5.7.1. Making decisions 5.8.1. Static methods 5.8.2. Defining static methods |
| M. 9/7 | Holiday | |
| T. 9/8 |
Assignment 1. Java: While-loops. Java: For loops Assn. 1 assigned. |
5.7.3.1. While-loops 5.7.3.3. For-loops (Assignment 1) |
| W. 9/9 |
Infinite loops. Coding standards for loops. Arrays. Review. |
5.7.3.5. Infinite loops 5.12.1. Arrays 6.8.4. Standards: loops |
| F. 9/11 |
Quiz 2. Java: More arrays. |
Review: 4.2. Contracts 5.8.1. Static methods 5.8.2. Defining static methods 5.7.3.1. While loops 5.7.3.3. For-loops |
| M. 9/14 | Algorithms: Scan algorithms. | 8.4. Scan algorithms |
| T. 9/15 |
Algorithms: Search algorithms. Breaking out of loops. |
8.6. Search algorithms 5.7.3.4. Breaking a loop |
| W. 9/16 |
Java: Scope. Frames. Algorithms: Recursion. |
5.8.2. Frames 5.9. Scope 8.3. Recursion |
| F. 9/18 |
Quiz 3. Assignment 2. Assn. 1 due. Assn. 2 assigned. |
(Assignment 2) Review: 5.11.1. Arrays 8.5 Scan algorithms 8.7 Search algorithms |
| M. 9/21 | Examples of recursion. | 8.3. Recursion |
| T. 9/22 | Java: Characters. Strings. | 5.10. Strings |
| W. 9/23 |
Java: Objects. Review. |
5.13.1. Objects |
| F. 9/25 |
Quiz 4. Imports. |
5.3. Imports Review: 8.3. Recursion 5.12.1. Arrays 5.10. Strings |
| M. 9/28 |
Assignment 3. Java: Classes with only data. Assn. 2 due. Assn. 3 assigned. |
Assignment 3 5.14.1. Classes for data |
| T. 9/29 | Java: Constructors. | 5.14.2. Constructors |
| W. 9/30 |
Lists. Review. |
10.1 Lists |
| F. 10/2 |
Quiz 5. Java: Object references. The null object. |
5.13.4 Object references Review: 5.13.1. Objects 5.14.1. Classes for data 5.14.2. Constructors |
| M. 10/5 | Data structures: Linked lists. | 10.2. Linked lists |
| T. 10/6 |
Assignment 4. Assn. 4 assigned. |
Assignment 4 |
| W. 10/7 |
Data structures: Nondestructive operations on linked lists. Review. Assn. 3 due. |
10.3. Nondestructive operations on linked lists |
| F. 10/9 |
Quiz 6. More nondestructive operations on linked lists. |
10.3. Nondestructive operations on linked lists Review: 5.13.4 Object references 10.1 Lists 10.2. Linked lists 10.3. Nondestructive operations on linked lists |
| M. 10/12 and T. 10/13 | Fall break. | |
| W. 10/14 |
Testing. Successive refinement. Tracing. |
7.1. Error diagnosis 7.2. Hand simulation 7.3. Compile errors 7.4. Program development and testing 7.5. Tracing |
| F. 10/16 |
Algorithm development. Basic tools. Top-down design. |
8.1. The design process 8.3. Algorithm discovery |
| M. 10/19 |
Objects with instance methods. Classes with instance methods. |
5.13.2. Objects with instance methods 5.15.1. Classes with instance methods 5.15.2. Visibility |
| T. 10/20 | An example class. | 5.15.3. Example |
| W. 10/21 |
Another example class. Review. |
5.15.4. Another example |
| F. 10/23 |
Quiz 7. Boxing. |
5.13.5. Boxing Review: 5.13.2. Objects with instance methods 5.15.1. Classes with instance methods 5.15.2. Visibility 5.15.3. Example 5.15.4. Another example |
| M. 10/26 |
Assignment 5. Assn. 4 due. Assn. 5 assigned. |
Assignment 5 |
| T. 10/27 | More on assignment 5. | Assignment 5 |
| W. 10/28 |
Reasoning about programs: loop invariants. Review. |
8.5. Loop invariants |
| F. 10/30 |
Quiz 8. Overloading. |
Review:
10.1 Lists 10.2. Linked lists 10.3. Nondestructive operations on linked lists 5.13.2. Objects with instance methods 5.15.1. Classes with instance methods 5.15.2. Visibility |
| M. 11/2 | Destructive operations on linked lists. | 10.4. Destructive operations on linked lists |
| T. 11/3 | More destructive operations on linked lists. | 10.4. Destructive operations on linked lists |
| W. 11/4 |
Exception handling. Review. |
5.16.1. Exceptions 5.16.2. Catching exceptions |
| F. 11/6 | Quiz 9. |
Review: 10.4. Destructive operations on linked lists 5.16.1. Exceptions 5.16.2. Catching exceptions |
| M. 11/9 | More exception handling. |
5.16.3. Throwing exceptions 5.16.4. Throws clause |
| T. 11/10 |
Cost of computation. Big-O notation. Logarithms. |
9.1. Algorithm analysis |
| W. 11/11 |
Sorting: Insertion sort. Review. |
|
| F. 11/13 | Quiz 10. |
Review: 5.16.1. Exceptions 5.16.2. Catching exceptions 5.16.3. Throwing exceptions 9.1. Algorithm analysis |
| M. 11/16 |
Java: Two-dimensional arrays. Assignment 6. Assn. 5 due. Assn. 6 assigned. |
Two-dimensional arrays Assignment 6 |
| T. 11/17 | Sorting: Quicksort. | |
| W. 11/18 |
Sorting: Sorting using a priority queue. Review. |
|
| F. 11/20 | Quiz 11. |
Review: Sorting 9.1. Algorithm analysis |
| M. 11/23 | Sorting a linked list. Mergesort. | |
| T. 11/24 | Java: Interfaces. Concept of inheritance. | |
| W. 11/25 to F. 11/27 | Thanksgiving break | |
| M. 11/30 | Review. | |
| T. 12/1 | Review. | |
| W. 12/2 | Review. | |
| F. 12/4 | Quiz 12. | Review: TBA |
| M. 12/7 | Open. | |
| T. 12/8 | Reading day. | |
| F. 12/11 | Final exam, 11:00am–1:30pm. |
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. If you submit someone else's work as your own, expect to recieve no credit. If your submission is 50% your work and 50% someone else's work, expect to receive no credit.
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. If someone asks for a copy of your work, do not supply it. Doing so risks receiving no credit for your own work.
For information about