Teaching assistant:
Ojaswirajanya Thebe, othebe@knox.edu
Office hours: (in the Cat lab) Monday 7-9pm
Website: http://courses.knox.edu/cs142
In this class, you will continue to develop your programming skills and begin to consider program design and efficiency. Central to these concerns is the choice of data structures, the ways your program can organize information. We will study some of the types of data structures and also different ways in which they can be implemented to achieve different performance goals. Our focus will be on understanding how to select the appropriate data structure types and implementations for specific applications. In addition, the course will include an introduction to Unix development tools.
We meet Monday, Wednesday, Thursday, and Friday during 3rd period (10:40-11:50). On Thursday, we meet in the Cat lab (SMC-E011). The other days, we meet in SMC-D205.
Class will not meet on April 16 or May 14 so you can work on your exams.
Our textbook is "Data structures in Java" by Simon Gray. There is a copy on reserve in the SMC library. I also put "Data Structures & their algorithms" by Lewis and Denenberg on reserve as a reference. The Lectures page will tell you what sections from the text we covered in each lecture and include links to relevant outside resources.
If you find yourself struggling in this course, get help right away. The term will move quickly and concepts in this course build on one another so you can't afford to get too far behind. Don't hesitate to come by my office or email me a question.
There is a tutor available in the Red Room (second floor of Seymour library) Tuesday through Thursday during the evening from 7-9pm. It is also possible to arrange for an individual tutor through the Center for Teaching and Learning (CTL).
Week 1: New programming tools. Testing. Review of inheritence and polymorphism.
Week 2: Linked lists. Testing objects for equality. Exceptions.
Week 3: Iterators. Doubly-linked lists. null.
Week 4: Arrays. List ADT. Intro to amortized analysis. Exam 1.
Week 5: Collections overview. Stack. Queue.
Week 6: GUIs. Binary search. Logs. Sorting. Comparators.
Week 7: Binary search trees. General trees. Tree traversals.
Week 8: Priority queues. Exam 2.
Week 9: Hashing.
Week 10: Graphs.
Expect to work for this class; if this is one of your three classes, you should be spending something like 13 1/3 hours a week on it. (If you find yourself spending more than that, let me know...)
Assignments for this class will feature a mixture of programming and writing. Most assignments will be fairly short, but some longer assignments will also be given. Labs will not be graded directly, but many of the lab assignments will become homework. In addition, we will have two exams (during the weeks of 4/16 and 5/14) plus a final, all take-home.
Be aware that I draw my examples for lecture from student assignments. Don't be surprised if something you submit ends up projected on the screen during class. The purpose of this is to demonstrate important concepts and to provide material for discussion, not to embarrass you. I will endeavor to use these examples anonymously by removing names and any other identifying features.
You should plan on submitting all work by the due date, but I know this is not always possible. Therefore, you get two "late days" that may be used on homework assignments during the term. Each allows you to submit one homework 24 hours late without penalty. They can be used for the same or different assignments. After these two days, assignments lose 10% of their points for each 24 hours they are late. Late submissions are not accepted once solutions have been posted so let me know if you intend to work on something past its normal deadline. Individual extensions beyond these two days require extraordinary circumstances.
I assign extra credit problems infrequently. I will however give extra credit for attending colloquium talks sponsored by the CS department (possibly other departments, depending on the content of the talk) and submitting a short writeup about the talk. Give a quick summary and any impressions you had in a couple of paragraphs (~1 page). It doesn't have to be brilliant prose; the main purpose is for me to see what YOU got out of the talk. This offer applies to any qualifying talk you are not otherwise getting credit to attend and is due within a week of the talk (slight extensions possible, but I want you to still remember the talk...).
If flunk day falls on the day something is due or the day before, that assignment is extended by one day. Flunk day also acts as a free "late day".
Regular attendance is expected, but there is not a specific penalty for missing lecture. You are responsible for your own education. This means that you need to find someone to turn in homework if you are absent on the due date and you must find a way to learn the material covered during absences. In addition, please send me an email if you will be missing class so I know what is going on.
Exams in this class must be completed individually. You are allowed to talk with others about the homework and encouraged to work together in small groups (2-3 students). Even when working together, however, you are expected to write your submission yourself and understand it completely. In addition, you must do two things:
The same policies apply to getting help from inanimate sources. If you use the web or a textbook other than the one we're using, you must cite this source. As in collaborations with another person, you are expected to write you own solution; do not copy text or code from any source. In addition, you may look at other sources for examples or conceptual help, but not actual solutions. Some problems assigned for this class may have been previously assigned to other classes, but you are expected not to deliberately seek solutions. (If you come across one accidently, let me know and I will give you a modified assignment.)
Please feel free to contact me if you have any questions about this policy.
At the end of the term, all of your work will combined into an overall course percentage based on the following weights:
| Homework | 35% |
| Exams | 40% (20% each) |
| Final | 25% |
Note that homework makes up a very high percentage of our course grade; this corresponds to the important role I believe working on it plays in learning the material.
The range of scores mapping to each grade will be determined at the end of the term. It will not be stricter than the "standard" 90/80/70/60 grading and may be more generous. In general, spend your time learning the material rather than worrying about your grade, but feel free to talk with me if you are concerned about it.