Villanova University

Department of Computing Sciences


CSC 8000 Foundations of Algorithms and Data Structures


Professor:         Dr. Lillian N. Cassel

E-mail:            lillian.cassel@villanova.edu  (Please put CSC 8000 in the subject line to get my attention)
Office Hours:  Tuesday 5 - 6 Thursday 3 to 5 pm.  Others by request.  When my door is open, you are welcome to come in. 


Semester: Fall 2012


Course Description: (From the department web site) Programming in Java or another object-oriented language. Program design with an emphasis on the object paradigm. Classic algorithms and data structures. Significant programming assignments are required.

(For this instance)  We will use "another object-oriented language."  Specifically, this course will develop ability to write and debug programs using Python.  We will focus on the object paradigm and will explore classic algorithms and data structures.  Weekly programming assignments and a larger project will provide ample experience.  The domain for many examples will be information extraction and analysis using substantial data sets that allow very real experience.


Textbook:  Object-Oriented Programming in Python.  Goldwasser and Letscher.  Pearson/Prentice Hall Publisher.  © 2008.

This text provides comprehensive coverage of fundamental computing topics related to algorithms and data structures, explored through the python programming language.  It is used as an undergraduate introduction, but at a much slower pace than we will move through it.  We assume some experience with programming, though not extensive experience or expertise.  You should expect to move through this book quickly and to use most of it.  The book includes a reference appendix for moving from Python to other important programming languages, including C++ and Java.


Secondary Textbook:  Natural Language Processing with Python.  Bird, Klein, Loper.  O'Reilly Publisher.  © 2009.

This book provides introductory level Python in the context of Natural Language Processing. It allows sophisticated text processing with very little overhead so we can see some real work getting done very quickly. The book is available online.  (http://www.nltk.org/book)


Course Goals:

Prepare incoming MS and MSE students to do the problem analysis and programming requirements of masters level courses in computer science and software engineering.




Information about the course management:

Introduction : 

Every indication is that the best way to learn is to be actively involved in discovery, in creating your own knowledge. As a result, your active participation is a fundamental requirement of this course. You will write and run programs every week.  You will discuss issues related to algorithms and data structures, sometimes in class, sometimes in online discussions.  


Additional information : 

Attendance: I assume that every student will attend every class unless I have heard previously that you have a reason for missing class. In all cases, you are responsible to discover what has been done in the class you miss. Just keeping up with class by hearing about happenings from other students is not sufficient, however. Your input into our discussions is important. Your absence not only hurts you; it deprives the rest of the class of the valuable contributions you would have made. A part of the grade is reserved for active participation in every class session. 


Online component: 

This class will include regular classroom sessions and also some online sessions.  There will be some occasions when I participate in the class from a distance.  For these classes, you will need access to a computer and internet connection sufficient to display live video.  If you have this type of resource, you may attend the class from your chosen location.  If you do not have access to these resources, they will be provided for you and you will be expected to attend at Villanova.  In any case, your attendance and active participation will be required.


Writing:

The writing component to this class will be limited to documentation of your running programs.  This is a serious expectation and will be considered as part of the course requirements.  No papers or presentations are required for this course.

I like this quote, found on the department web page:

                                  Any fool can write code that a computer can understand. Good programmers write code that humans can understand.

                                                                                                                                                                      — Martin Fowler

We aspire to be good programmers.


Grading Policy

Grades will be based on successful and timely completion of assignments and projects, and on active participation in class and in online discussions.

A graduate student who does satisfactory work in assignments receives a grade of B. Better work receives better grades. An A grade requires exceptional work, not just meeting requirements.  A grade of A is certainly achievable, but it is not automatic if you just meet requirements.

Programming projects will be graded.  In addition, there will be periodic quizzes.  If this seems to go well, we will not have any long examinations.  If it appears that we need the forced focus that exams provide, then we will have them.  


Course Web Presence

There are advantages and disadvantages to the Blackboard course management system used at Villanova.  I prefer that my materials be open and accessible, so I will use this public web site.  We will use the Blackboard site from time to time to take advantage of tools that are there.  Be sure to log in to the course site and become familiar with its use.


Semester Schedule

The following calendar will be developed as the class progresses.  We begin with an approximate schedule of topics and readings for the class up until the Fall break week.


Week


Subject

Links_to Slides

Notes/Assignments

Activity

1

8/29

Introduction to the course and its goals.  Computing environment for course exercises.  Basics of the object paradigm.  Compilers and Interpreters.  Levels of languages.  The Python interpreter.  "Hello World"
Simple text processing from NLTK

Intro and beginning Python

Chapters 1 and 2 of text -- read by next week.  That is a lot to read, but it gets through what we talk about during classes 1 and 2.

Be sure that the computer you will use for assignments has Python and the Natural Language Tool Kit installed and that you know how to use them. (Time during class for this)

2

9/5

Strings and tuples, numeric types and operations, modules, functions, expressions, booleans
Accessing text corpora and lexical resources

Strings, Tuples, Numbers

Write Program 1 - see the Blackboard page
NLTK book, chapter 2

Quiz 1 - Lists

3

9/12

Graphics in Python-- Guest Faculty member, Dr. Papalaskari

Python Graphics

Steganography assignment
This is also available in the Blackboard site.
Quiz 2 - Strings, Tuples, Numbers

4

9/19

Graphics from the book -- Chapter 3 of the Python book.

No slides.  Use the detailed steps of the chapter.
Exercise 3- 16 of the Python book.
Use your imagination and make something interesting on the canvas, then allow the user to draw the path. 

Be sure to do good testing of your program.  Use variable names that are meaningful.  Use internal documentation that tells what the program segments are doing.
Steganography quiz
The chapter is a step-by-step guide to the use of the special graphics package the authors developed.  Go through that and try the various instructions.  You will need to download the graphics package.  Just put it where you put the nltk materials.

5

9/26

Control structures, file access, function definition

Control
The slides include narration for some things.  Please display the slides as a slide show and click on the icons for the narration.
Quiz on Graphics

6

10/3

Natural Language Processing and corpora

NLP and corpora

Choose any one of the programming exercises numbered 8 to 22 at the end of Chapter 2 in the NLTK book.  Pick whatever looks interesting to you. -- Due next week

7

10/10

Classes, Exceptions
ClassesPlus


8

10/17

Fall Break      




9

10/24

Text Sources, Regular Expressions

Text & RE
See assignment at end of slides

10

10/31

Completing Regular Expressions
Recursion, Search
Recursion


11

11/7

Python Containers
Included in previous slide set


12

11/14

Word Tagging
Tagging


13

11/21

Thanksgiving break



14

11/28

Event handling and databases  DB, Event, Network programming


15

12/5

Text Classification Classification


16

12/12

Last Class -- Candidates:  Interface design + ???






References (This list will be expanded as the class progresses)


  1. Goldwasser, Michael H. and David Letscher.  Object-Oriented Programming in Python.  Pearson Prentice Hall Publisher.  2008. (Course Text book)
  2. Bird, Steven and Ewan Klein, Edward Loper.  Natural Language Processing with Python -- Analyzing Text with the Natural Language Toolkit.
  3. Gooch, Tom.  UML Tutorial - Class Diagrams http://atlas.kennesaw.edu/~dbraun/csis4650/A%26D/UML_tutorial/class.htm