NORFOLK STATE UNIVERSITY
700 PARK AVENUE * NORFOLK, VIRGINIA * 23504
Robinson Technology Center (RTC)
Office:: (757) 823-9454     Fax: (757) 823-9229
Email: CompSci@nsu.edu

Computer Science Courses

DEPARTMENT OF COMPUTER SCIENCE SYLLABUS

COURSE NUMBER & TITLE:
CSC-372   Data Structures
COURSE CREDITS:
3
PREREQUISITES:
CSC 260 (Computer Programming II).
CO-REQUISITES:
See Instructor
COURSE DESCRIPTION:

An analysis of data structures and algorithms using C++ as the implementation language. Detailed examination of lists, heaps, trees, graphs, file structures, and the use of formal methods. Emphasis is placed on the development and analysis of efficient algorithms.

COURSE MATERIALS / REQUIRED TEXT(s) / SUPPLEMENTARY READINGS:
    Textbooks
    Required E-Book
  • Data Structures and Algorithm Analysis in C++, 3rd Edition, Clifford A. Shaffer, 2012.
    The most recent version of this e-book is Edition 3.2.0.7, dated November 19, 2012. This e-book is freely available at http://people.cs.vt.edu/~shaffer/Book/C++3e20121119.pdf and in Blackboard. If you wish to have a printed version of this textbook, print copies are published by Dover Publications (ISBN-10: 0-486-48582-X, ISBN-13: 978-0-486-48582- 9).

  • References
  • C++ Programming: Program Design Including Data Structures, 6th Edition, D. S. Malik, Cengage Learning, 2013, ISBN-10: 1-133-52632-2, ISBN-13: 978-1-133-52632-2.
  • Data Structures and Algorithms in C++, 4th Edition, Adam Drozdek, Cengage Learning, 2013, ISBN-10: 1-133-60842-6, ISBN-13: 978-1-133-60842-4.
  • Data Structures and Other Objects Using C++, 4th Edition, Michael Main and Walter Savitch, Prentice Hall, 2011, ISBN-10: 0-132-12948-5, ISBN-13: 978-0-132-12948-0.
  • Data Structures and Algorithms in C++, 2nd Edition, Michael T. Goodrich, Roberto Tamassia, and David M. Mount, John Wiley & Sons, 2011, ISBN-10: 0-470-38327-5, ISBN-13: 978-0-470-38327-8.
  • Data Structures and Algorithm Analysis in C++, 3rd Edition, Mark Allen

Purchase books/supplies Online at NSU Barnes & Nobles Bookstore (http://norfolkstate.bncollege.com)

COMPUTER SCIENCE OFFICE LOCATION:

The Department of Computer Science is located in Suite 320 Robinson Technology Center. The individual faculty offices are located within the suite.

COURSE RATIONALE:

This course is a required course for the Bachelor of Science Degree in Computer Science. Activities and assignments in this course support the program outcomes currently listed on our departmental website (http://www.cs.nsu.edu/programs/ugradprogram.html). Specifically, this course enables the following objectives (click list of objectives below to see details)

Computer Science CourseProgram Objectives
CSC361 SURVEY OF PROGRAMMING LANGUAGES A,B,C,I,J,K
Click list above to see more details.

COURSE GOALS & INTENDED OUTCOMES

    A goal of the course is to introduce the concepts behind the analysis of algorithms.
    The students will be able to:
  • Give a big-O analysis of simple algorithms.
  • Explain the difference in algorithmic efficiencies among various sorting and search algorithms.
  • Explain the differences in algorithmic efficiencies of various operations on linked lists and arrays.
  • Explain how some algorithms with apparently poor performance might be better choices than those with better performance analyses.

  • A goal of the course is to introduce fundamental data structures and their abstract data types.
    The students will be able to:
  • Modify abstract data types for lists, stacks, and queues.
  • Design simple abstract data types for other data structures.

  • A goal of the course is to introduce trees as a natural storage device.
    The students will be able to:
  • Trace level-order (breadth-first), preorder, inorder, and postorder traversals of binary trees.
  • Trace the implementation of searching a binary search tree.
  • Trace the implementation of inserting an item into a binary search tree.
  • Trace the implementation of deleting an item from a binary search tree.
  • Build additional functions to the binary search tree abstract data type.
  • Explain at least two methods of balancing a binary search tree.

  • A goal of the course is to introduce hashing into a simple table.
    The students will be able to:
  • Trace the insertion of and search for items in a hash table.
  • Evaluate the qualities of various hash functions.
  • Evaluate the qualities of various collision resolution strategies.

  • A goal of the course is to introduce graphs and various algorithms applied to graphs.
    The students will be able to:
  • Trace the topological sort algorithm on directed, acyclic graphs.
  • Trace Dijkstra’s Algorithm on positively weighted graphs.
  • Explain at least two different minimum spanning tree algorithms on weighted graphs.
  • Apply stacks and queues to tree traversals.
  • Trace both breadth-first and depth-first tree traversal algorithms.

COURSE OUTLINE

  • Welcome
  • Algorithm Analysis:
  • Mathematical Background
  • Big-O Notation
  • Evaluating Algorithms

  • Abstract Data Types:
  • Lists, Stacks, and Queues

  • Recursion

  • Trees - Implementation:
  • Binary Trees and Traversals
  • AVL Trees and Other Tree Balancing
  • Binary Search Trees (and ADT)

  • Graph Algorithms:
  • Definitions and Representations
  • Topological Sort
  • Shortest-Paths (Dijkstra’s Algorithm)
  • Minimum Spanning Tree
  • Depth-First and Breadth-First Searches and Traversals

  • Sorting:
  • O(n2) Sorting Algorithms
  • O(n lg n) Sorting Algorithms
  • Linear Order Sorting

  • String Matching
  • Hashing:
  • Hashing Functions
  • Open and Closed Hashing
  • Review

  • Final Examination

PRIMARY METHOD(S) OF INSTRUCTION / METHODS TO ENGAGE STUDENTS

This course is taught using a variety of instructional methods including lecture, laboratory, class discussion, class work (students working individually or in groups), tutorials, readings, problem solving, student presentations to class, or use of guest speakers. Blackboard, an Internet-based education software, will be used. You can access Blackboard at http://www.nsu.edu/blackboard/.

Although there is a required textbook for the course (see the section titled Textbooks), I will use material from a variety of resources, including other textbooks and research papers; so the main source for the course will be my lecture notes. I will make my lecture notes available in Blackboard after the relevant lecture. It is your responsibility to obtain notes written on the board and material given or discussed in class that are not available in electronic format; such material will not be available in Blackboard. In order to access class-related material, log in to Blackboard and choose your CSC 372 link. All class-related material will be available in the folder titled CSC 372 Material. If you wish to access more resources, check the Norfolk State University library for resources including e-books and print books.

GRADING STANDARDS

Examinations (60% of the course grade)
A variety of examinations of equal or varying weight will be given. All class examinations are considered to be a major part of the course work upon which a large part of the course grade depends. You must take all the course examinations. Depending on the situation, a course grade of “F” may be assigned if any examination is missed. There are no make-up examinations. If you have a conflict, you must contact me well in advance of the examination. In case of an extreme emergency, contact me before the scheduled examination. If I am not in, leave a message and your number and I will return your call. Acceptable proof of the emergency will be required. Failure to do so will result in an examination grade of zero.

I reserve the right to keep all examinations. You will be informed as to the exact format of an examination as well as the format of the questions on an examination. After the examinations have been graded, you have one week to come by and see the examination. After a week, the examinations are no longer in my office and cannot be reviewed.

Homework / Laboratory Assignments (35% of the course grade)
A variety of assignments of equal or varying weight will be given. All assignments are due at the announced time on the specified due date. Late assignments will not be accepted unless you had a conflict and had contacted me in advance. You have one week after receiving your assignment grade to verify it. No changes to grades will be made after this time. Students should keep all graded assignments until the final grade for the course had been posted.

For this class, it is permissible to assist classmates in general discussions of computing techniques. General advice and interaction are encouraged. Each person, however, must develop his or her own solutions to the assigned homework and laboratory exercises. Do not let anyone copy your work. Students may not “work together” on assignments. Such collaboration constitutes cheating, unless it is a group assignment. A student may not use or copy (by any means) another’s work (or portions of it) and represent it as his or her own.

If you have any questions about the course or need assistance, contact me in person, by phone during office hours, or by e-mail at any time. Any e-mail message for my personal attention must be submitted to my Norfolk State University e-mail account. Use only your Norfolk State University e-mail account to contact me; any message sent to me from a non-Norfolk State University e-mail account will not be read. Do not send e-mail messages for time critical information; e-mail messages may not be read on a daily basis. Always give your name and class when sending e-mail messages. Put “CSC 372: ” at the start of the subject line of your e-mail followed by the specific subject about which you are contacting me.

Quizzes (5% of the course grade)
A variety of quizzes of equal or varying weight will be given. A grade of zero will be assigned for any missed quiz unless you had a conflict and had contacted me in advance. You have one week after receiving your quiz grade to verify it. No changes to grades will be made after this time. Students should keep all graded quizzes until the final grade for the course had been posted. I may drop your lowest quiz score when your quiz average is computed.

Grading System
The final grade for the course will be computed as follows:

  • Examinations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60%
  • Homework / Laboratory Assignments. . . . . . . . . . . . . . 35%
  • Quizzes.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 %

  • The final grade for the course will be computed using the following scale:

    Percentage Value*
    Letter Grade
    GPA Value (per credit hour)
    90-100
    A
    4.00
    87-89.9
    B+
    3.30
    80-86.9
    B
    3.00
    77-79.9
    C+
    2.30
    70-76.9
    C
    2.00
    67-69.9
    D+
    1.30
    60-66.9
    D
    1.00
    0 - 59.9
    F
    0.00
    * I reserve the right to lower these values if necessary.

    Class attendance, participation, and other contributions may be taken into consideration in the final calculation of the course grade, especially in the case of borderline grades (within a certain percentage of grade threshold). A case-by-case decision will be made whether to assign the next higher grade.

    The instructor expects students to write organized answers to essay-style questions. Answers that have weak organization may result in a penalty. For example, an answer was so disorganized that it took significant work to find the relevant material in the mass of irrelevancy. Do not miss the point of the question and spend a lot of space on irrelevant material. If you do not know the answer to a question, leave the question blank. Inappropriate use of the English language, including grammar, punctuation, spelling, and capitalization may result in a penalty. The instructor expects students to write legibly; sloppy handwriting may result in a penalty.

    Extra credit work and/or points may be given. If circumstances beyond the student’s control prevent completion of course requirements, a student may request an incomplete grade from the instructor. It is the instructor’s decision to grant or deny a request for an incomplete grade. Requests for an incomplete grade must be made on or before the date of the final examination. Depending on the situation (especially in an emergency situation that had prevented a student from taking the final examination), requests for an incomplete grade may be made after the final examination as long as the final grades for the course had not been entered into the university’s academic computer grading system. The final grades for the course will be available to students immediately after they are electronically submitted. The final grades will be submitted by the university final grade submission deadline (which can be found on the university website). Please note that submitted grades cannot be updated.

    ACADEMIC INTEGRITY STANDARDS

    Academic Honesty
    All class assignments are to be done independently, unless specified. If in my judgment a student is found cheating on an examination, assignment, or quiz, the student will be penalized. I consider the person who did the work (examination, assignment, or quiz) and the person copying the work as both cheating. Students should save all developmental copies of their assignments so that individual assignment development can be verified to me if I think it is necessary.

    The Department of Computer Science employs a no tolerance policy on cheating. Cheating includes, but is not limited to, copying others work, misrepresenting the work of others as your own (including online sites), plagiarism, sharing when unauthorized, and the use of cellular phones and/or electronic media when unauthorized. The following outlines the departmental procedure if a student is suspected of cheating during his or her academic tenure with the Computer Science Department at Norfolk State University.

      Offense 1 –
    • The student will receive a grade of zero on the assignment and a note will be placed in the student’s permanent departmental file. Non-CS Majors will receive a zero and be reported to the chair of their respective department.
    • Offense 2 –
    • The student will receive a letter grade of “F” for the course and the student will be reported to the Office of Student Rights and Responsibilities for adjudication.

    COURSE POLICIES

    The Department of Computer Science adheres to the Norfolk State University policy on class attendance. The university expects students to attend all classes. While unnecessary absences are discouraged, the university recognizes that, on occasion, students may have legitimate reasons for being absent. Not more than 20% of class meetings (excused and/or unexcused) may be missed by a student during a given semester. Please read your student handbook for more details.

    Class attendance is a very important aspect of a student’s success in this course. Please enter the classroom only after the previous class has finished. Roll will be taken regularly at the beginning of class. If you are not in class when I call roll, you are absent. If you come in late, your tardiness will be noted and you will be penalized, including taking points off from your course grade and/or counting it as an absence. If you are absent from class, please do not come by my office and ask me to repeat the class lecture. In order to eliminate class disruptions, please do not come to class late or leave early. No one may enter the classroom once class has started. Students are expected to stay in the classroom the entire time. If there is an emergency and you need to leave early, notify me before the class. Please refrain from packing your belongings before the end of class. There is no smoking, no chewing tobacco, no chewing gum, no eating or drinking, no bare feet, and no sleeping in the classroom. Trash must be thrown away in the trash bin. You may not sit on the classroom tables. Cellular phones, headsets of any type, CD players, radios, and similar devices are prohibited in the classroom and must be turned off before you enter the classroom. You may not use your cellular phone for text messaging. No cellular phone may be visible to me at anytime. If you expect an important message, inform me before class starts. Recording devices are not permitted; if you wish to record the lecture for further study, you need to get approval from me.

    Calculators and computers are prohibited during examinations and quizzes, unless specified. Laptop computers may be used in lecture for the purpose of taking notes only. I have the right to ban laptop computers in the classroom at anytime without specifying a reason. You must not use the classroom computers unless you are asked to do so by the instructor. You may not sit at the instructor’s desk or use his computer without permission. Students are expected to exhibit proper classroom behavior and language, and not engage in any behavior that would be disruptive to other students and/or the instructor. If you have a question, raise your hand and ask the instructor; do not ask other students. Talking to others while I am speaking will not be tolerated. Please take all of your personal belongings at the end of the class meeting. I am not responsible for any belongings that are left in the classroom. Only students officially registered for the course and approved assistants may attend class. Please bring your textbook, lecture notes, and relevant material to every class meeting.

    Graded work will be given in class. If you missed class, it is your responsibility to stop by my office during office hours to pick the graded work. I will not post any course grade in Blackboard. Graded work will be given in class. However, if you wish to find out your grades and/or where you stand in class, please contact me via e-mail to set up an appointment so I could bring my grade book. I will not give out grades via e-mail, phone, or mail (unless I find it necessary to do so); meet with me in person to see your grades. When asked to do work (examination, assignment, or quiz) in class, you must turn in the work to the instructor; do not leave class with any work. Students who leave class with any work will be penalized.

    Check your Norfolk State University e-mail account daily for information regarding this course. Please do not leave your homework assignments or any other work under my office door or the Department of Computer Science’s office door; do not leave your homework assignments or any other work in my department mail box, unless specified. Please do not bring food or drinks to class. Students are expected to abide by the Norfolk State University Spartan Code of Ethics. I reserve the right to change this syllabus at any time. I will notify you of any change through verbal and/or written notification.

    SCHOOL-WIDE TUTORING SERVICES STATEMENT

    The college of Science, Engineering, and Technology provides tutoring services through the STARS Tutoring Center for those NSU student who may be experiencing difficulties in Mathematics, Computer Science, Engineering, Biology, Chemistry, Nursing, Technology and Physics courses. The STARS office is located in Suite 100, RTC. This service is free of charge and provided to NSU students only. You can access information about this service by going to http://stars.nsu.edu.

    AMERICANS WITH DISABILITIES ACT (ADA) STATEMENT

    In accordance with Section 504 of the Rehabilitation Act of 1973 and the Americans with Disabilities Act (ADA) of 1990, we ask if you have a disability or think you have a disability, please contact O.A.S.I.S., the Office of Accessibility Services, upon registration at Norfolk State University to confidentially discuss any accommodation needs.

      Audrey M. Wells, Coordinator, O.A.S.I.S.
      Office of Accessibility Services and International Student Services
      Norfolk State University, 700 Park Ave., Student Services Center, Suite 110, Norfolk, VA. 23504
      Phone: 757-823-8325, Fax: 757-823-2640, Email: amwells@nsu.edu

    UNIVERSITY ASSESSMENT STATEMENT

    As part of NSU's commitment to provide the environment and resources needed for success, students may be required to participate in a number of university-wide assessment activities. The activities may include tests, surveys, focus groups and interviews, and portfolio reviews. The primary purpose of the assessment activities is to determine the extent to which the university's programs and services maintain a high level of quality and meet the needs of students. Students will not be identified in the analysis of results. Unless indicated otherwise by the instructor, results from University assessment activities will not be computed in student grades.

    WRITING COMPETENCY ASSESSMENT

    All first-time freshmen and readmitted students entering Fall 2001 and thereafter and transfer students entering Fall 2002 and thereafter are required to take an exit examination to assess writing competency. After completing ENG 102, students must register for ENG 299 (no credit, no charge) until successfully passing the Examination of Writing Competency. Degree-seeking students at the baccalaureate level are required to take the writing examination before completing 90 semester hours. Associate degree-seeking students must take the exam no later than one semester prior to the anticipated date of graduation. For more information, refer tot he NSU Undergraduate catalog.

    UNIVERSITY WIDE & COURSE-SPECIFIC REQUIREMENTS

      Information Technology Literacy
    • Learning foundation skills (hardware, software, and operating systems).

      Critical Thinking
    • Solving problems utilizing application software from a narrative description.
    • Knowing the appropriate software application to apply to a specific task.

      Laboratory
    • Demonstrating proficiency in utilizing software applications.
    CLASS ATTENDANCE POLICY

    A student is expected to attend all classes. The student assumes all responsibility for work missed due to an absence. Make-up work may be permitted at the discretion of the instructor. Refer to the NSU Student Handbook (https://www.nsu.edu/Assets/websites/student-affairs/student-handbook/NSU-Student-Handbook.pdf)

    NSU EMAIL ACCOUNT

    In an effort to keep student informed about Norfolk State University updates and account information, students must check their official NSU email account frequently. You may access your official NSU email account through the MyNSU portal at https://www.nsu.edu/mynsu/index. Once there, follow instructions provided to login to the MyNSU portal (NOTE: you access your NSU email from within the MyNSU portal).

    DISCLAIMER: The instructor reserves the right to revise the syllabus as appropriate and will make reasonable attempts to notify students.