Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
346 lines (240 sloc) 30.1 KB

CS-242 02 --- Fall 2015

CS-242 Data Structures

This is a LASC course and can be taken to satisfy the Quantitative Literacy Across the Curriculum requirement.

Credit and Contact Hours

4 credits
Lecture: 4 hours/week

Catalog Course Description

Introduces time complexity and covers fundamental data structures: lists, stacks, queues, search trees, dictionaries, priority queues, B-trees and inverted files.

Instructor

Dr. Karl R. Wurst
See http://cs.worcester.edu/kwurst/ for contact information and schedule.

Meeting Times and Locations

MW 2:00-3:40pm
ST 107

It's in the Syllabus


<a href=http://www.phdcomics.com/comics.php?f=1583>http://www.phdcomics.com/comics.php?f=1583

Textbook

*Data Structures: Abstraction and Design Using Java, Second Edition*
Elliot B. Koffman and Paul A. T. Wolfgang
John Wiley & Sons, Inc, 2010
ISBN-13: 9780470128701
[Textbook website](http://www.wiley.com/WileyCDA/WileyTitle/productCd-EHEP001607.html)
[Source code and solutions to odd number Self-Check Exercises](http://bcs.wiley.com/he-bcs/Books?action=index&itemId=0470128704&bcsId=5643)

Required Materials

In addition to the textbook, to successfully complete this course you will need:

  1. Laptop Computer: You will need a laptop computer that you can bring to class sessions and can use at home. The brand and operating system (Windows, Mac OS X, Linux) is unimportant – the software we will be using runs on all major operating systems and can be downloaded for free. It is expected that you will download and install required software as needed over the course of the semester. The computer you plan to use will need:

    1. Web Browser – You will need a web browser to access the Blackboard course site and Piazza (see Internet Access below.)
    2. PDF Reader – All course materials will be distributed as PDF files, and all graded work will be returned electronically as PDF files. You must have software to read PDFs.
    3. Eclipse – The Eclipse software is Free and Open Source Software and can be downloaded from https://eclipse.org/downloads/ and is available for Windows, Mac OS X and Linux operating systems. We will install Eclipse on your computer during the first class.
    4. Git --- We will use this software to share code during lab, and submit code to the instructor. We will download and install this software during the first class.
  2. Internet Access: You will need Internet access for access to:
    2. Blackboard – All course materials and announcements will be made available through the course site on Blackboard. Students will be required to use Blackboard as the course tool and be familiar with uploading files. 3. WSU Gmail – You must check your WSU Gmail account on a regular basis. All communications to the class, such as corrections to problem sets or changes in due dates, will be sent to your WSU Gmail account. 4. Piazza – This is an online service that lets you ask (and answer other students’) questions about the course assignments, materials, and topics. 5. GitLab --- This is a git server hosted by the Computer Science we will use to host and submit our code. 6. Stypi --- We will use this site as a way to for you to help me write code during lectures. 7. Socrative --- We will use this site as a way for you to answer questions during lectures so I can assess how well you are following the material.

Where Does This Course Lead?

  • CS 282 Unix Systems Programming
  • CS 343 Software Construction, Design and Architecture
  • CS 353 Information Organization, Management and Retrieval
  • CS Electives
  • Your professional career

Course Workload Expectations

This is a four-credit class. You should expect to spend, on average, 12 hours per week on this class.

You will spend 4 hours per week in class. In addition, you should expect to spend, on average, at least 8 hours per week during the semester outside of class, reading the textbook, studying, doing assignments, working on projects, and practicing in order to master the concepts and techniques covered in the course. (See Definition of the Credit Hour)

Definition of the Credit Hour

Federal regulation defines a credit hour as an amount of work represented in intended learning outcomes and verified by evidence of student achievement that is an institutional established equivalence that reasonably approximates not less than –

  1. One hour of classroom or direct faculty instruction and a minimum of two hours of out of class student work each week for approximately fifteen weeks for one semester or trimester hour of credit, or ten to twelve weeks for one quarter hour of credit, or the equivalent amount of work over a different amount of time; or
  1. At least an equivalent amount of work as required in paragraph (1) of this definition for other academic activities as established by the institution including laboratory work, internships, practica, studio work, and other academic work leading to the award of credit hours.

---New England Association of Schools and Colleges, Commission on Institutions of Higher Education, Policy on Credits and Degrees

Prerequisites

Since this course has a prerequisite of Introduction to Programming (CS 140), I assume that you have a good understanding of:

  • Basic programming constructs – conditionals, repetitions, assignment statement, relations, logical and arithmetic operators
  • Classes, objects, static and instance methods and variables
  • Inheritance, interfaces, inner classes, abstract classes
  • Java's String class
  • Arrays and ArrayLists
  • How to write a reasonably large program (with multiple files) in Java
  • How to use good software engineering practices including writing good documentation

If you do not have this background, you should not take this course.

Corequisite

This course has a co-requisite of Discrete Mathematics I (MA-220). You must be taking MA-220 at the same time as this course (or have successfully completed it prior to taking this course.)

Students will apply the mathematical concepts learned in MA-220 in CS-242. Specific topics from MA-220 that will be applied in CS-242 include:

  • Functions
  • Asymptotic notation
  • Complexity of algorithms – worst case, average case and best case complexities; solving recurrence relations
  • Writing recurrence relations for recursive methods
  • Applying the master theorem to solve recurrence relations
  • Apply set theoretic concepts – membership, set union, set intersection and set difference (while designing Binary search trees, hash tables and Balanced trees)
  • Various proof techniques

Through this integrative learning effort, student learning will be enhanced by immediately applying the mathematical concepts learned in MA-220 in CS-242. Thus, students will have the opportunity to make connections not only between these two courses, but also between how what is being learned in the classroom fits into a broader scope of learning.

Attendance

You are expected to attend every class. (See Attendance and Class Participation below.)

Course-Level Student Learning Outcomes

Upon successful completion of this course, students will be able to:

  • Trace, Code, compile, test and debug fairly large multi-module Java programs given a program design/specification by choosing an appropriate data structure (Emphasis)
  • Evaluate algorithms, selecting from a range of possible options, providing justification for that selection, and implementing the algorithm in a particular context. (Emphasis)
  • Evaluate the best, average, and worst case behaviors of an algorithm using Big O notation (Introduction)
  • Classify algorithms as constant, logarithmic, linear, quadratic, and exponential complexity and compare their performance (Introduction)
  • Measure the performance of algorithms empirically (Introduction)
  • Write Java programs that use the following data structures: lists, binary search trees. Priority queues, balanced trees (Emphasis).
  • Discuss how various data structures improve program structure, software quality, and programmer productivity (Emphasis)
  • Explain how Java programming language implementations organize memory into global data, text, heap, and stack sections and how features such as recursion and memory management map to this memory model (Mastery)
  • Use a version control system to commit and revert changes on a single-user repository (Emphasis)
  • Document code for other programmers, users of modules, users of programs (Emphasis)
  • Construct and debug programs using the standard libraries available in Java programming language (Emphasis)
  • Compare multiple designs or implementations for a problem using various data structures. (Emphasis)

LASC Student Learning Outcomes

This course will contribute to the students’ ability to:

  • Demonstrate effective oral and written communication.
  • Employ quantitative and qualitative reasoning.
  • Apply skills in critical thinking.
  • Understand the roles of science and technology in our modern world.
  • Make connections across courses and disciplines.

LASC Quantitative Literacy Across the Curriculum Outcomes

This course will:

  1. Enable students to appreciate that mathematics is itself a domain of knowledge, rich in ideas, not just algorithms.
  2. Engage students in mathematical ideas and show them how mathematics is connected to other areas of study.
  3. Improve the quantitative and mathematical skills of students, and help them better appreciate the importance and utility of mathematics.
  4. Use mathematics as a language informing humanistic ideas.
  5. Enable students to examine a given problem, situation, or experiment, ask suitable mathematical questions, and draw various conclusions and interpretations through the application of mathematics.
  6. Enhance students' knowledge about how mathematics is used in various disciplines by devoting a substantial portion (minimum of 25%) of the course assessment to mathematics. Examples would include problems in the field that require mathematics solutions.

Program-Level Student Learning Outcomes

This course addresses the following outcomes of the Computer Science Major:

Students will be able to:

  1. Analyze a problem, develop/design multiple solutions and evaluate and document the solutions based on the requirements. (Emphasis Level)
  2. Communicate effectively both in written and oral form. (Emphasis Level)
  3. Demonstrate an understanding of and appreciation for the importance of negotiation, effective work habits, leadership, and good communication with teammates and stakeholders. (Emphasis Level)
  4. Learn new models, techniques, and technologies as they emerge and appreciate the necessity of such continuing professional development. (Emphasis Level)

Course Topics

The course outline will be covered on a best-effort basis, subject as always to time limitations as the course progresses.

  • Overview of the Java Language – Arrays, ArrayLists, Abstract classes, Interfaces
  • Algorithmic Complexity – Big O notation, worst case, average case and best case complexity
  • Evaluating the complexity of simple code segments
  • Evaluating the complexity of recursive code using recurrence relations (Master theorem)
  • Sequential data structures – Singly linked lists, doubly linked lists and circular lists
  • Hierarchical Structures – Binary trees, Binary Search Trees, Red-Black trees, Height-Balanced trees, and B-trees
  • Priority Queues
  • Simple Graph Algorithms
  • Sorting and Searching algorithms
  • Using Java Collection classes and the Iterator interface
  • String matching algorithms

Course Philosophy

During this semester we will study various data structures that are used to solve a wide variety of programming problems. The emphasis will be on developing the judgment necessary for determining what tools and techniques are available and appropriate in a given situation. Modern programming languages come with large libraries that include fundamental data structures. As the code in these libraries is (presumably) well designed, well debugged, and efficient, it makes sense for programmers to use the provided code rather than developing their own from scratch. However, it is difficult to make informed decisions without understanding the underlying implementation of a data structure.

Therefore, we will also be paying close attention to the implementation issues behind algorithms and data structures. You will be implementing and experimenting with several data structures using Java. We will briefly touch upon the worst-case time complexity of algorithms.

Even though this course will be using the Java programming language and its associated libraries, much of what you will be learning is language independent. Therefore, we will also place an emphasis will be on concepts and techniques, in addition to the particulars of the Java API.

You are encouraged to help each other out, in and out of the classroom, as long as you do your own work. (See Academic Conduct below.)

Instructional Methods

This class will not be a traditional “lecture” class, and will incorporate some teaching methods that may be unfamiliar to you.

Flipped Classroom

You will be given reading assignments in the textbook and from other sources, and you will be expected to complete a short quiz on the reading assignment(s) before the class meeting. Your answers from the quiz will be used to tailor what we do in the classroom. If everyone understands a topic or concept, we will not spend time on it in class. If a large portion of the class is having difficulties with a topic or concept, we will work on it in class to make sure everyone understands.

Your quizzes will be graded on the effort you put into explaining your answer. If you do not complete the quiz by the specified time, you will not receive any points for that quiz.

This flipped classroom technique means that I will spend much less time “telling” you things that you already understand from the reading, and more time on the concepts that you find difficult.

Peer Instruction

In the classroom, you will often be presented with a problem and a set of possible answers. You will “vote” for the correct answer using your browser. Then you will discuss your answer and your explanation with your classmates. Once you have completed your discussions, you will vote again. If the discussions have helped the class understand the material better, we will move on to other topics. If there is still difficulty with the material, we will spend more time with additional explanations and problems.

This time spent actively discussing the material with your classmates will help you develop a deeper understanding of the concepts.

Pair Programming

Often, during class time, you will be working on hands-on assignments. For these assignments, you will work in a pair with one of your classmates. One of you will type while the other makes suggestions, watches for errors, reads the assignment, and thinks ahead. You will switch roles frequently during the lab session.

You will be randomly assigned a new partner each lab. This will allow you to get to know the other members of the class, work with partners of different abilities and programming styles, and develop relationships that may extend beyond to classroom.

Supplemental Instruction Sessions

Your success in this course is important, and is being supported in the Fall 2015 semester by Supplemental Instruction sessions, funded by a Massachusetts Department of Higher Education grant for the retention of STEM students. Supplemental Instruction will be provided in selected courses in Biology, Chemistry, Computer Science, Earth Science, and Mathematics.

Supplemental Instruction (SI) sessions are student-led, instructor-supported, group study and review sessions run by trained student facilitators who were highly successful themselves in CS-242. These student leaders have been trained to develop group learning activities using a variety of strategies. The SI leaders will be attending the regular classroom sessions and meeting with the course instructors regularly to prepare their SI sessions.

There will be four CS-242 SI sessions offered per week by two different SI leaders. You can attend any one of the sessions that fits your schedule (you may even attend more than one if you wish!) The sessions will consist of group activities where you will interact with your classmates to form a deeper understanding of the course material.

Attendance at these sessions is voluntary, but highly encouraged. National research has shown that students who attend SI sessions have a significantly lower rate of D grades, failures and course withdrawals. And SI sessions are not just for struggling students - the same research has shown that all students who attend SI sessions get higher grades than those who do not.

The SI student leaders will introduce themselves during the first class session, and times for the sessions will be announced soon after classes start.

Your attendance at the SI sessions is not reported to the course instructor, to ensure that all students in the course are treated equally and fairly with regard to grading.

Grading Policies

There will be in-class work, two exams, programming projects, and a final project and presentation. Your grade in the course will be determined as follows:

Assignment Category Percentage
Exams 40%
Assignments/Labs 50%
Attendance and Class Participation 10%

Grading Scale

Percentage Letter Grade
93-100% A
90-93% A-
87-90% B+
83-87% B
80-83% B-
77-80% C+
73-77% C
70-73% C-
67-70% D+
63-67% D
60-63% D-
less than 60% E

Each range includes the lower value, but not the upper value. For example, the range of 80 to 83 includes all grades up to, but not including 83. The highest range does, however, include 100%.

Note: Every time you come and see me in my office with relevant questions regarding course material and/or assignments you will be given 5 extra points towards your attendance and class participation portion of the grade.

Exams

There will be several exams in the course. Exam dates will be announced at least a week in advance.

There is no final exam for this course.

Assignments/Labs

The programming projects will give you a chance to apply the material to larger tasks.

These projects will require you to interpret requirements, do some planning and design, implement your program and test and debug it. Your work will have to be up to professional standards and documentation and formatting guidelines will need to be followed.

Attendance and Class Participation

You are expected to attend every class. Class time will be divided between lecture and hands-on in-class work. Past experience has shown that students who do not attend class do not do as well on exams and projects.

The in-class lab work will give you a chance to apply the material from the lecture in an environment where you can benefit from the help of the instructor and your classmates. Once you have developed a level of comfort and confidence with the material, then you can be expected to apply it on larger projects outside of class.

Missed in-class work cannot be made up after the fact. If you know that you will have to miss class, let me know beforehand and we can make arrangements for you to do the in-class work at another time.

Readings

The readings provide a basis for everything we do. You are responsible for the content - even if we never actually discuss a given reading. Required reading is assigned from the textbook; collateral readings are linked from the Blackboard site.

Deliverables

All work will be submitted electronically through a variety of tools. The due date and time will be given on the assignment. The submission date and time will be determined by the submission timestamp of the tool used.

Please do not submit assignments to me via email. It is difficult for me to keep track of them and I often fail to remember that they are in my mailbox when it comes time to grade the assignment.

It is strongly recommended that you keep copies of your projects. Students are responsible for reproducing any lost work including unreadable files.

Graded assignments (with comments and solutions) will be returned to you electronically. Please make sure that you review the comments and solutions provided, so that you can improve your future assignments.

Late Submissions

Late assignments are not accepted. This is so that we may discuss the assignment soon after the due date.

I understand that occasionally circumstances beyond your control (work, family emergencies, illness, etc.) may prevent you from completing an assignment on time. If that is the case, please e-mail me before the assignment is due and I will certainly consider your case.

Getting Help

If you are struggling with the material or a project please see me as soon as possible. Often a few minutes of individual attention is all that is needed to get you back on track.

By all means, try to work out the material on your own, but ask for help when you cannot do that in a reasonable amount of time. The longer you wait to ask for help, the harder it will be to catch up.

I am here to help you understand the material and be successful in the course.

Contacting Me

You may contact me by email (Karl.Wurst@worcester.edu), telephone (+1-508-929-8728), or see me in my office. My office hours are listed on the schedule on my web page (http://cs.worcester.edu/kwurst/) or you may make an appointment for a mutually convenient time.

If you email me, please include “[CS-242]” in the subject line, so that my email program can correctly file your email and ensure that your message does not get buried in my general mailbox.

If you email me from an account other than your Worcester State email, please be sure that your name appears somewhere in the email, so that I know who I am communicating with.


<a href=http://www.phdcomics.com/comics.php?f=1795>http://www.phdcomics.com/comics.php?f=1795

You may expect that I will get back to you within 24 hours of your email or phone call (with the exception of weekends and holidays), although you will likely hear from me much sooner.

Code of Conduct/Classroom Civility

All students are expected to adhere to the policies as outlined in the University's Student Code of Conduct (http://www.worcester.edu/CodeofConduct/).

Student Responsibilities

  • Contribute to a class atmosphere conducive to learning for everyone by asking/answering questions, participating in class discussions. Don’t just lurk!
  • Seek help when necessary
  • Start assignments as soon as they are posted. Do not wait until the due date to seek help/to do the assignments
  • Make use of the academic success center (see below)
  • Expect to spend at least 9 hours of work per week on classwork.
  • Each student is responsible for the contents of the textbook readings, handouts, and homework assignments.

Americans with Disabilities Act

Worcester State University and this instructor are committed to the full participation of all students, and will provide accommodations for any student with documented disabilities who are registered with the Disability Services Office (DSO). Please contact the instructor as early as possible to discuss necessary accommodations. All information regarding disabilities will be treated with confidentiality. The DSO is located in the Administration Building, Room 131 and can be reached by phone (508-929-8733) or email (dso@worcester.edu).

Tutoring Services/Academic Success Center

Tutoring Services are offered through the Academic Success Center (ASC). The ASC is located on the first floor of the Administration building, A-130. Tutoring services are provided to students FREE of charge. Students seeking academic assistance should visit the center as soon as possible or contact the Tutoring Coordinator at 508-929-8139

The Math Center

The writing center provides free assistance to students in Mathematics. It is located on the first floor of the Sullivan Academic Building, S143.

The Writing Center

The writing center provides free assistance to students in the areas of research and writing. It is located on the third floor of the Sullivan Academic Building, S306. To schedule an appointment, please call 508-929-8112 or email the Center at writingcenter@worcester.edu. To find out more information about the Writing Center including the Center’s hours and the Center’s Online Writing Lab, visit their website at www.worcester.edu/writing

Worcester State Library

Worcester State Library has access to many articles through online databases including J-STOR. In addition many articles and book chapters are available to students through Inter-Library Loan (ILL). With a little planning, ILL expands your ability to get credible information sources about topics you pursue in your course work. Finally WSU students are free to use many of the library resources within the consortium. Given all of these resources it is extremely unlikely that you should have to pay for access to individual articles. Please work with the reference librarians to find the appropriate way to access materials you need. You have already paid for these resources through your fees—please make use of them.

Academic Conduct

Each student is responsible for the contents of the readings, discussions, class materials, textbook and handouts. All work must be done independently unless assigned as a group project. You may discuss assignments and materials with other students, but you should never share answers or files. Everything that you turn in must be your own original work, unless specified otherwise in the assignment.

All work must be done individually. Students may help each other understand the language and the development environment but students may not discuss actual solutions, design or implementation, to their programming assignments before they are submitted or share code or help each other debug their programming assignments. The assignments are the primary means used to teach the techniques and principles of computer programming; only by completing the programs individually will students receive the full benefit of the assignments. If you are looking at each other’s code before you submit your own, you are in violation of this policy. All students that collaborate on an assignment will receive a 0 for that assignment if that is the first offense. Students that collaborate a second time will receive an ‘E’ for the course.

Students may not use solutions to assignments from any textbooks other than the text assigned for the course, or from any person other than the instructor, or from any Internet site, or from any other source not specifically allowed by the instructor. If a student copies code from an unauthorized source and submits it as a solution to an assignment, the student will receive a 0 for that assignment.

Any inappropriate sharing of work or use of another's work without attribution will result in a grade of zero on that assignment for all parties involved. If you do so a second time, you will receive an “E” for the course.

Academic integrity is an essential component of a Worcester State education. Education is both the acquisition of knowledge and the development of skills that lead to further intellectual development. Faculty are expected to follow strict principles of intellectual honesty in their own scholarship; students are held to the same standard. Only by doing their own work can students gain the knowledge, skills, confidence and self-worth that come from earned success; only by learning how to gather information, to integrate it and to communicate it effectively, to identify an idea and follow it to its logical conclusion can they develop the habits of mind characteristic of educated citizens. Taking shortcuts to higher or easier grades results in a Worcester State experience that is intellectually bankrupt.

Academic integrity is important to the integrity of the Worcester State community as a whole. If Worcester State awards degrees to students who have not truly earned them, a reputation for dishonesty and incompetence will follow all of our graduates. Violators cheat their classmates out of deserved rewards and recognition. Academic dishonesty debases the institution and demeans the degree from that institution.

It is in the interest of students, faculty, and administrators to recognize the importance of academic integrity and to ensure that academic standards at Worcester State remain strong. Only by maintaining high standards of academic honesty can we protect the value of the educational process and the credibility of the institution and its graduates in the larger community.

You should familiarize yourself with Worcester State College's Academic Honesty policy. The policy outlines what constitutes academic dishonesty, what sanctions may be imposed and the procedure for appealing a decision. The complete Academic Honesty Policy appears in: http://www.worcester.edu/CodeofConduct/ If you have a serious problem that prevents you from finishing an assignment on time, contact me and we'll come up with a solution.

Schedule

Our first class will be on Wednesday, 2 September 2015.

Our last class will be on Monday, 7 December 2015.

We will not have class on Monday, 7 September (Labor Day), Monday, 12 October (Columbus Day), Wednesday, 11 November 2015 (Veterans Day), and Wednesday, 25 November 2015 (Thanksgiving)

Our final exam will be on Wednesday, 16 December 2015 - 12:30-3:30pm

##Copyright and License ####© 2015 Karl R. Wurst, Worcester State University

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/4.0/ or send a letter to Creative Commons, 444 Castro Street, Suite 900, Mountain View, California, 94041, USA.