CS 242 - Introduction to Data Structures II
Lynchburg College Computer Science
Sep. 2, 2008
Click image to see Table of Contents
Click to see Table of Contents


Instructor : Dr. Constantine Roussos
Office : Hobbs 104
Phone : Office 544-8395, Home 263-6692

A study of data structures, algorithms and abstraction and they relate to the efficient storage and retrieval of data in digital computers. Topics may include sorting, searching, lists, queues, stacks, trees, graphs, networks, hashing, key structures, file structures as well as techniques of object-oriented analysis and structured programming.

More information, supplementary materials, sample tests, study guides, etc. are located at http://cs-netlab-01.lynchburg.edu/courses/DataStru

COURSE SYLLABUS

    The primary objectives of this course are the following:
  1. Be familiar with the implementation and applications of general trees and graphs.
  2. Program a variety of efficient sorting algorithms.
  3. Implement efficient searching algorithms.
  4. Be familiar with indexing techniques such as B+ trees.
  5. Utilize advanced techniques of lists and arrays.
  6. Understand the theoretical limits to computation and NP completeness.
  1. Using LC's computing facilities.
    1. Getting started
      1. On-campus computing.
      2. Logging into your account.
      a. Username, Password
      b. Directories and subdirectories.
      c. Privileges and access.
       3. Off-campus computing
      a. Using ftp
      b. http
    2. The class website.
    3. Understanding and using files.
      protection, date/time, etc.
    4. Electronic MAIL at LC
      1. Using MAIL commands.
      a. Reading, sending, extracting, etc.
      b. Sending MAIL to me.
       2. Your homework assignments, programs and general communication.

  2. REVIEW of Binary Trees Tree Definitions
    Binary Trees Defined
    Binary Search Tree
    Binary Tree Traversals
    Binary Tree Operations
    Balanced Binary Trees
    Heaps
    RPN & Expression Trees
  3. Multiway Trees B, B* and B+ Trees
    Other types of B- Trees
    Tries
  4. Graphs Graph Representation
    Graph Traversals
    Shortest Paths
    Cycle Detection
    Spanning Trees
    Connectivity
    Topological Sort
    Networks
    Matching
    Eulerian and Hamiltonian Circuits
    Graph Coloring
    NP-Complete Graph Problems
  5. Sorting Review of Elementary Sorting Selection Sort
    Bubble Sort
    Insertion Sort
    Counting Sort     Decision Trees
    Intermediate Sorting Techniques Shellsort
    Quicksort
    Heapsort
    Mergesort
    Binsort and Radixsort     Sorting in the STL
  6. Hashing Hash Functions
    Collision Resolution
    Deletion
    Perfect Hash Functions
  7. Data Compression Conditions for Data Compression
    Huffman Encoding
    Run-Length Encoding
    Ziv-Lempel Code
  8. Memory Management Sequential and Nonsequential Fit Methods
    Garbage Collection
  9. String Matching Exact String Matching
    Approximate String Matching
  10. Appendices
    A: Computing BIG-O
    B: Algorithms in the Standard Template Library
    C: NP-Completeness
  11. FINAL EXAM
Testing :
There will be 3 tests, an undetermined number of pop quizzes, and homework assignments, several programs and a final exam. Class participation will also count towards one's grade.
The above factors will be weighted as follows :
Tests :.33
Programs:.22
Labs :.11
Final Exam :.22
Class Partic, Homework, Quizzes: .12

Grading :
The standard 10 point grading scale will be used. (i.e. 90-100 = A, 80-89 = B, 70-79 = C, 60-69 = D, below 60 = F) THERE WILL BE NO CURVE. You will always know approximately how you are doing in the course by applying the above factors to your grades to date.

Important notes:
  1. If you are having trouble with the course come to me for help right away - DO NOT WAIT.
  2. You are responsible for attending class, completing programs on time, taking tests when scheduled, knowing the college's grading policies, knowing course withdrawal dates and making up all missed work.
  3. As always the honor code is in full effect. You may NOT collaborate on programming assignments or tests. If you are ever in doubt of whether or not an action constitutes an honor violation ask me beforehand.
  4. Class participation on your part is an excellent means of making our classes more interesting and demonstrating to me your knowledge of and interest in the subject matter.

Required Materials:
Data Structures and Algorithms in C++, second edition by Adam Drozdek.
The publisher is Thomson.

Recommended Materials:
Microsoft Visual C++ 6.0 (available in Bookstore)

Statement on Students with Disabilities
Lynchburg College is committed to providing all students equal access to learning opportunities. The Support Services office, located in Academic & Career Services on the second floor of Hall Campus Center, is the campus office that works with students who have disabilities to provide and/or arrange reasonable accommodations. Students registered with Support Services, who have a letter requesting accommodations, are encouraged to contact the instructor as early as possible in the semester -- accommodations are not retroactive. Students who have, or think they may have, a disability (e.g. attentional, learning, vision, hearing, physical, or psychiatric), are invited to contact the Support Services Coordinator for a confidential discussion. Call 434-544-8687 or e-mail the Coordinator at Arnold.sm@lynchburg.edu. Additional information is available at the Lynchburg College Disability Support Services website: http://www.lynchburg.edu/disabilityservices.xml.



Top of this page   Top of page      Home page   Home page