CS 2413 001 Summer 2000 -- Data Structures

Class: Mondays & Wednesdays 1:20-3:20pm, Carson Engineering Center Room 117
Instructor: Dr. Henry Neeman, Sarkeys Energy Center 1252 (Boyd & Jenkins)
(hneeman@ou.edu, 325-5386)
Office Hours: Mondays & Wednesdays 3:30-5:00pm, Sarkeys Energy Center 1252
OR BY APPOINTMENT 24 HOURS IN ADVANCE

Note: please contact me by e-mail unless it's an emergency;
please don't call the Computer Science or CAPS offices if you can't find me in my office.

TA: K. Chandramouli (``Mouli''), Engineering Lab 126
(mouli@ou.edu, 325-0811)
Office Hours: Tuesdays & Thursdays 10:00am-noon, Engineering Lab 126
OR BY APPOINTMENT 24 HOURS IN ADVANCE

Catalog Description: Object-oriented representation of widely used data structures and associated algorithms. The design of medium-size software systems. Written communication required in some projects. Discussion of ethical issues including computer crime, abuse, and hacker ethics.

Prerequisites

CS 1333 (Programming Structures and Abstractions), CS 1813 (Discrete Mathematics),
and by extension CS 1323 (Fundamentals of Computer Programming) and MATH 1523 (Elementary Functions)
(Note: graduate students are not required to have fulfilled these prerequisites, but are advised to consider carefully the amount of catching up that they will need to do in a very short period of time.)

Ambitious (tentative) list of topics to be covered

• Introduction to C++
• Analysis of Algorithms
• Arrays, Strings & Vectors
• Linked Lists
• Stacks & Queues
• Sorting
• Trees
• Priority Structures
• Graphs
• Hashing
• Ethics

Texts

• Object-Oriented Data Structures Featuring C++, S. Radhakrishnan, L. Wise & C. N. Sekharan, 1999
  Available at Sooner Textbooks, Lindsey & Jenkins (15 copies available as of May 30, more expected by June 9)
  
• Computer Ethics, 2nd ed., D. Johnson, Prentice-Hall, 1994
  Available at Sooner Textbooks, Lindsey & Jenkins (11 copies available as of May 30, more can be ordered)
  or at the main University Bookstore (many new and used copies available)
  

Laptops

CS 2413 IS a laptop course.

Required work

• 3-6 Programming Projects (50% of overall grade)
  
• Weekly Quizzes (10%): every Friday at 1:20pm starting June 16 (usually open book)
  Quiz questions will be taken verbatim from the homework assigned the Monday immediately before.
• Midterm Exam (20%): Monday 10 July 2000 1:20-3:20pm CEC 117
• Final Exam (20%): Monday July 31 1:20-3:20pm CEC 117

Recommended work

Weekly homeworks will be assigned every Monday starting June 12. These will form the basis for the quizzes; they will not be collected or graded.

Assignment Postings

• All assignment descriptions will be posted to the class webpage. You are responsible for downloading and printing them as necessary.
  
• Most assignments will be given on a Monday and due on a Friday, either that Friday (4 days later) or the following Friday (11 days later).
  
• Just because you have an assignment pending does not mean that another will not be given. For example, if you get an assignment on Monday the 1st that is due Friday the 12th, you may also get an assignment Monday the 8th that is due Friday the 19th.

July 4^th Holiday

This year, July 4^th falls on a Tuesday. Class will be held both Monday July 3^rd and Wednesday July 5^th. Do not count on assignment due dates being adjusted to accomodate this campus holiday.

Grading

• A: score >= 90%
• B: 80% <= score < 90%
• C: 70% <= score < 80%
• D: 60% <= score < 70%
• F: score < 60%
  We reserve the right to curve the grades as we see fit, but the curve will not be harsher than this.
• Your score will be calculated this way:

  
          q[1]+q[2]+...+q[nq]               p[1]+p[2]+...p[np]            m         f
  Wq ---------------------------- + Wp ---------------------------- + Wm ---- + Wf ----
     maxq[1]+maxq[2]+...+maxq[nq]      maxp[1]+maxp[2]+...+maxp[np]      maxm      maxf
  

  
  where
  • Wa is the percentage weight associated with assignment type a (e.g., Wq, the weight for quizzes, is 10);
  • maxa[i] is the maximum possible score on assignment #i of assignment type a;
  • a[i] is your score on assignment #i of assignment type a.

Web Postings

Most class materials, including lecture slides, homework assignments and programming project descriptions, will be posted to the class webpage. See below.

E-mail

Occasionally, we may need to alert the class when an issue comes up. You should check your e-mail at least twice a week.

Class Policies

• Credit for programming projects
  • No lateness deduction: if turned in by 3:20pm on the due date
  • 25% deducted: if late one class (by 3:20pm the class after the due date)
  • No credit: if later than 3:20pm the class after the due date
• Do your own work!
  You are required to do all of your own work. It is NOT ACCEPTABLE to copy each other's work. Cheating can result in suspension or expulsion, so DON'T EVEN THINK ABOUT IT!
  
• Help from online sources
  Below you will find many online information resources to help you learn about C++. It is NOT ACCEPTABLE to ask for help on assignments from people online (and in any case they will know what you're up to and will offer to send their answers directly to us). Misuse of online resources will be interpreted as cheating. Anyone caught doing so will be dealt with HARSHLY.
• Help from us
  If you have questions or you're having trouble with the material, we urge you to come talk to us during our office hours, or to make an appointment (at least 24 hours in advance) to meet at other times, or to send e-mail.
• Working on programming projects
  Do not wait until the last minute to start your programming projects. As you probably have learned by now, developing software takes time, and may depend on the availability and reliability of systems that you have no control over. If the computers are down the night before a due date, don't count on that buying you extra debugging time -- it certainly won't in the real world.
• Studying for exams
  Do not wait until the last minute to start studying for exams. The best way to ensure success is to keep up with the course material, and to ask questions. Students who actively participate in lectures and come to office hours typically learn and retain the material a lot better.
• Will this be on the exam?
  Yes. Everything covered in class, readings, homeworks/quizzes, programming projects and on the class webpage is fair game unless specifically stated otherwise.

Disability

Any student in this course who has a disability that may prevent him or her from fully demonstrating his or her abilities should contact the instructor personally as soon as possible so that accommodations necessary can be made to ensure full participation and to facilitate your educational opportunities.
Be prepared to bring documentation from the Office of Disabled Student Services.

Academic Misconduct

All cases of academic misconduct will be reported to the Dean of the College of Engineering for adjudication.

A Quick Look at the Unix Operating System

Readings
You should not only read the chapters; you should also type in, compile and run the example programs. This will not only solidify your understanding of the material in the book, it'll also help you to get used to the operating system and the C++ compiler.

• The C++ Preprocessor [PDF] [PostScript]
• C++ Arrays & Strings [PDF] [PostScript]
• OODS Appendix by Monday June 12
• OODS Chapter 1 (Introduction) by Monday June 12
• OODS Chapter 2 (Algorithms & Recursion) by Wednesday June 14
• OODS Chapter 3 (Arrays, Strings & Vectors) by Friday June 16
• OODS Chapter 4 (Linked List Structurese) by Friday June 23
• OODS Chapter 5 (Stacks & Queues) by Wednesday June 28
• OODS Chapter 6 (Sorting) by Monday July 3
• OODS Chapter 7 (Single Dimensional Search Trees) by Friday July 7
• OODS Chapter 8 (Self-Modifying Search Trees) by Wednesday July 12
• OODS Chapter 9 (Priority Structures) by Monday July 17
• Computer Ethics Chapter 6 (Crime, Abuse, and Hacker Ethics) by Friday July 28
  and the slides used in class [PDF] [PostScript]

Homeworks (worth 10% of overall grade)

• Homework #1 [PDF] [PostScript]
  Quiz to be held in class 1:20pm Friday June 16 2000
  Solution
  
• Homework #2 [PDF] [PostScript]
  Quiz to be held in class 1:20pm Friday June 23 2000
  Solution
  
• Homework #3 [PDF] [PostScript]
  Quiz to be held in class 1:20pm Friday June 30 2000
  Solution
  
• Homework #4 [PDF] [PostScript]
  Quiz to be held in class 1:20pm Friday July 7 2000
  Solution
  
• Homework #5 [PDF] [PostScript]
  Quiz to be held in class 1:20pm Friday July 21 2000
  Solution
  

Programming Projects (worth 50% of overall grade)

• Project #0: Thinking of a Number [PDF] [PostScript]
  Not due, not graded
  
• Project #1: Image Compositing [PDF] [PostScript]
  Due in class Friday June 23 2000
  
• Project #2: Dealing Cards [PDF] [PostScript]
  Due in class Friday July 7 2000
  Bonus Section: Counting Bridge Points [PDF] [PostScript]
  Due in class Friday July 7 2000 (NO LATE SUBMISSIONS)
  
• Project #3: Hungry Students [PDF] [PostScript]
  Due in class Monday July 24 2000
  
• Project #4: Self-Modifying Search Trees [PDF] [PostScript]
  Due in class Wednesday July 26 2000 OR FRIDAY JULY 28 WITHOUT PENALTY
  

Exams

• Midterm (worth 20% of overall grade)
  Monday 10 July 2000 1:20-3:20pm CEC 117
  
• Final (worth 20% of overall grade)
  Monday July 31 1:20-3:20pm CEC 117
  

• Usenet newsgroups
  • comp.lang.c++
  • gnu.g++.help
• Bjarne Stroustrup's Homepage (designer of C++)
• C++ FAQ Lite (Frequently Asked Questions)
• Jack Klein's C & C++ Page
• The Development of the C Language (Dennis M. Ritchie, co-developer of C, on which C++ was based)

• College of Engineering Computing Services
• ECN Helpdesk: information about software, Unix, Internet, etc. (going away soon)
• OU Helpdesk
  
• OU School of Computer Science
• OU Summer 2000 Academic Calendar