Syllabus
CSCI 3300
Introduction to Algorithms and Data Structures
Section 001
Spring 2007

Prerequisites

The prerequisite is CSCI 2310 or equivalent. You should be familiar with the basics of a programming language, such as Java, C++ or C#.

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.

Course objectives

This course covers advanced computer programming techniques and algorithms, primarily those that rely on advanced data representation schemes. The language is C++, with emphasis on the C subset. Students are not expected to have used C++ before, but should be familiar with elementary Java, or a related language. The course will begin with an introduction to C++.

This course emphasizes concrete aspects of data structures. Data abstraction, the other side of data structures, is emphasized in CSCI 3310.

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.

Topics

The following is a partial list of topics to be covered.

1. The C++ programming language. Expressions and statements. Control structures. Types and data, including structures and arrays.

2. Pointers and memory management. Dynamic memory allocation.

3. Data structures, including linked lists, trees and hash tables.

4. Algorithms on data structures, including both iterative and recursive algorithms. Correctness and efficiency of algorithms.

5. Designing, understanding, testing and debugging programs.

6. Understanding data types, and elementary concepts of abstract data types.

Grading

There will be a short quiz each Thursday, at the beginning of class. Grading will be as follows.

You will start with 10 points for attendance, and lose two points for each unexcused absence, up to a maximum of ten points.

Cutoffs for grades will tentatively be 90% for an A, 80% for a B, 70% for a C and 60% for a D. Those cutoffs will not be raised.

Writing and running programs

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.

I will compile and run programs using the g++ compiler. I will use the following warning flags when compiling programs:

-Wall -Wshadow -Wpointer-arith -O

Grading of programs

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.

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 all guidelines and requirements that have been set for the program. 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 guidelines and requirements that have been set for the program. 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 some attempt to follow the guidelines and requirements that have been set out for the program.

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 guidelines and requirements that have been set out for the program.

If you turn in a partial program, I will 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%.

Versions of programs

You will be expected to turn in two versions of each program.

1. First version. The first version should be a complete, working solution to the problem. You will receive feedback and a grade for it, and have an opportunity to improve your grade.

2. Second version. 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.

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).

Computing the score

Your score for a programming assignment will be computed as follows. Suppose that a is your grade for version 1 and b is your grade for version 2. Then your grade for the assignment is max(a, 0.20a + 0.80b). This means that, if you receive a perfect score for version 1, there is no need to turn in version 2, since you cannot improve your grade. It also means that, if you do not turn in the first version, the highest grade that you can receive is 80%, and that requires a perfect version 2. If you receive a grade of 90% for version 1 and 100% for version 2, then your score will be 98%.

Attendance policy

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.

Incompletes

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.

Recommendations for success

1. Attend class. Arrive on time.

2. Do not allow yourself to fall behind. Work on the homework early. Do not wait until just before the deadline.

3. Schedule time to work outside of class.

4. Read your notes and the book twice. Take a break (like a whole day) in between. You will learn much more that way.

5. 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.

6. If you are having trouble, seek help soon. Do not wait until it is too late.

Asking questions by email

You are encouraged to ask questions about your programs when you are stumped, especially if you come up against a difficulty with the 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 3

Student conduct

Smoking is not permitted in classrooms. Please turn off telephones while in class.

Students are expected to abide by the university's Student Honor Code. The homework that you do is a critical part of your education. Each student is expected to do his or her own work. That does not mean you are not allowed to discuss your ideas with other students. Working in groups can be beneficial, and I encourage you to talk through ideas with other students. But outright copying is plagiarism, and is unacceptable. Students who copy other students' work, or who allow their work to be copied, or who copy their work from other sources, such as the internet, will receive no credit.

Weather emergencies

In the event of a weather emergency, information about ECU can be obtained through the following sources:

ECU emergency notices	http://www.ecu.edu/alert
ECU emergency information hotline	252-328-0062

Students with disabilities

East Carolina University seeks to comply fully with the Americans with Disabilities Act. Students requesting accommodations based on a covered disability must go to the Department for Disability Support Services, located in Slay 138, to verify the disability before any accommodations can occur. The telephone number is 252-737-1016.