Villanova University

Department of Computing Sciences

CSC 8000 Foundations of Algorithms and Data Structures

Professor:         Dr. Lillian N. Cassel

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

Semester: Fall 2011

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.  (

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.


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.



Links_to Slides





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" The list class.

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.
Write a program to input a list of at least 5 items of any kind of thing you wish, sort it, and print it out in reverse order.  Yes, you will be able to do this after just one class!

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



Strings and tuples, numeric types and operations, modules, functions, expressions, booleans


Exercise 2.37 due next week
Read Chapter 4 (short) and 5.1 and 5.2

Quiz 1 - Lists



Control structures: For, conditionals,  while, functions

Control Structures

Project: Exercise 5.36 page 201 of the text
Read chapter 1 of

Quiz 2 - Strings, tuples, numbers



Starting Natural Language Processing

Processing text

  Chapter 1 of the NLTK book (Aux)

Quiz 3 - Control structures



Catching exceptions, Defining Classes   

Exceptions and classes

Text: 5.5Text: Chapter 6

Quiz 4 - Natural Language Processing



Python for graphics -- Guest faculty: Dr. Papalaskari

Python Graphics


Quiz 5 - Exceptions and Classes



Text Corpora        

Text Corpora

Aux: Chapter 2
We will get access to files of text in this chapter, but in a particular style related to natural language processing and using the Natural Language Processing Toolkit

Quiz 6 - Graphics in Python



Fall Break      



I/O and files  -- Local files and information from the Web.

Working with Files

Text Chapter 8
Exercises assigned in slides

Quiz 7 - Corpora



Inheritance and the management of objects

Text Chapters 9 and 10

Quiz 8 -- files



Raw Text, Regular Expressions

Text files & Regular Expressions

Aux Chapter 3

Quiz 9 -- Objects and Inheritance



Recursion, Dictionaries, Sets, Arrays

  Recursion etc 

Text Chapter 11, 12.1-12.5  Aux 4.7, 4.8

Quiz 10 -- Raw text, regular expressions



Algorithms: word tagging and categorizing       

Word tagging

Aux Chapter 5

Quiz 11 -- Algorithm Design and Recursion



Thanksgiving Break -- no class



 Algorithms: Classifying Text

Finish Word tagging and start Classifying text

Aux Chapter 6



Last Class --

Database and Event driven programming

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