Bard College — Computer Science 201
Data Structures
Keith O'Hara <kohara@bard.edu>
http://drablab.org/keithohara/cmsc-201-2018f/
This course introduces students to essential principles of program design and analysis that underlie applications of computation to internet communication, digital media, and artificial intelligence. Building on basic programming skills, we will focus on the construction of more sophisticated and reliable computer programs that employ the most important data structures. Data structures, common ways in which data is organized and manipulated, are an important aspect of modern programs. Consequently, throughout the course students will learn to create and use the most useful data structures, including files, lists, stacks, trees, and graphs. Students will write several programs, ranging from short lab assignments to larger systems of their own design.
Data Structures
Why?
"Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won't usually need your flowcharts; they'll be obvious." -- Fred Brooks (Turing award 1999)
Why?
"Representation is the esssence of programming" -- Fred Brooks (Turing award 1999)
Why?
"[Barbara Liskov (Turing award 2008)] led the design and implementation of the CLU programming language, which emphasized the notions of modular programming, data abstraction, and polymorphism. These concepts are a foundation of object-oriented programming used in modern computer languages such as Java and C# ..."
Why?
"Bad programmers worry about the code. Good programmers worry about data structures and their relationships." -- Linus Torvalds
Syllabus
Logistics
Lecture: Mon & Wed 10:10am-11:30am in RKC 100
Lab: Friday 10:30am-12:30pm in RKC 100
Office Hours
- RKC 204
- Tuesday & Wednesday 3:00pm-4:00pm; night hour?
- And by appointment
- Tutoring in RKC 100 most nights
Textbook
- Algorithms. Sedgewick and Wayne. 4th Edition. 2011. Pearson.
Website
http://drablab.org/keithohara/cmsc-201-2018f/
- Course Schedule
- Readings
- Assignments
- Resources
http://moodle2.bard.edu enrollment key:
We'll be using Google Classroom and GitHub (get an account)
Grading
| 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|
| excellent | good | satisfactory | unsatisfactory | no credit |
- Exams (60%): Three closed-book; closed-note; closed-computer exams
- Labs (25%): Weekly programming assignments
- Quizzes and Homework (10%): Pencil and Paper work given every week
- Presentation (5%): Presentation of an advanced data structure
Policies
- Labs due the night before the next lab period; hardcopy & submitted electronically.
- Quizzes and exams cannot be taken late without prior special permission.
- No late work will be accepted unless an extension is approved two days before the deadline.
- Keep work private (Google Drive; USB drive)
- It is your responsibility to submit them before the deadline, regardless of Internet, computer, or other problems.
- Is it Nice? Is it Necessary? Is it True? Pick Two.
Submission Procedure
All work submitted as a zip file that expands into a folder:
cmsc201-assignment-lastname-firstname
with your programs inside starting with a comment:
/**
* Name <bard email>
* date
* CMSC 201
* Assignment Name
* Collaboration I (worked alone | collaborated) on this assigment
* Statement [with (student | tutor) X]
* [with assistance from
* (website link | book | student | tutor) Z].
*/Academic Dishonesty
Do not claim other's work as your own
Careful Collaboration*
- Peers
- Tutors
- Professors
- Stack Overflow
- World Wide Web
*collaborators not available for exams
Programming as Theory Building (1985)
- Peter Naur
- 2005 Turing Award Winner
Programming as Theory Building
"the theory built by the programmer has primacy over such other products as program texts, user documentation, and additional documentation such as specifications"
Programming as Theory Building
"The programmer [CS student] having the theory of the program can ...
explain how the solution relates to the affairs of the world that it helps to handle...thus the programmer must be able to explain, for each part of the the program text and for each of its overall structural characteristics, what aspect or activity of the world is matched by it."
Programming as Theory Building
"The programmer [CS student] having the theory of the program can...
explain why each part of the program is what it is, in other words is able to support the actual program text with a justification of sort."
Programming as Theory Building
"The programmer [CS student] having the theory of the program can...
respond constructively to any demand for a modification of the program so as to support the affairs of the world in a new manner."
Learning Programming
"Progress is an Never-ending Circle" by AC Gillette
Advanced Data Structures Presentations
| tim sort | skip list | quad-tree | kd-tree |
| range tree | decision tree | B-tree | AVL-tree |
| splay-tree | distributed hash table | bloom filter | count-min sketch |
| trie | directed acylic graph | python dictionaries | cuckoo hashing |
Java
x = 50
if x > 42 and 54:
print ("Big Number")- Statically Typed
- Compiled
- Object-Oriented
Java
public static void main (String[] args){
System.out.println("Hello, World");
}- Statically Typed
- Compiled
- Object-Oriented
Java
public class NewThing{
public static void main (String[] args){
System.out.println("Hello, World");
}
}- Statically Typed
- Compiled
- Object-Oriented
Java Documentation
Java Refresher (Intro)
For next time ...
- Section 1.1 (pg. 8 -- 38)
- Homework: 1.1.1, 1.1.2, 1.1.4, 1.1.5, 1.1.7 (try without computer first)