Prof. Christopher L. Dancy
Office: Dana 340
Phone: 570.577.1907
Office Hours: M 2-3:30pm, Th 2-3:30pm - My calendar
Consider all of the tweets on Twitter or all of the status messages on Facebook. If someone asked you to design a method to search or sort every tweet or message ever sent, how would you begin to think about such a problem? How about if someone asked you to design a program to serve as memory for a virtual agent in Minecraft? How do you know the difference between an approach that takes 200 milliseconds and 200 years to run the primary operations? How would you organize the data in a way that helps you meet your goals? How do you even know where to start?
In this course, we will give you the tools to answer these questions. We will study the organization of data and learn how to analyze the impact of algorithms not only in our own programs, but in programs that must handle thousands, millions, or billions of data points. We will learn about the following topics:
Standard Data Structures: A data structure is a way of organizing and manipulating data (for example, Python lists). A smart choice of structuring your data can mean the difference between dramatically speeding up your program's execution or rendering a program so slow that it becomes unusable. In 204, we are going to learn both the organization and use of classical data structures (stack, queue, array, linked list, tree).
Data Abstraction: Throughout the course, we will be familiarizing ourselves with the powerful notion of separating abstract properties of data types from their concrete implementations in Python. We will learn to view complex programs as combinations of individual pieces (through Object-Oriented Programming) and reason about the behavior of those pieces independently of their implementation. This will ultimately help you develop more versatile software that is easy to update and reuse.
Algorithm Analysis: Programs are often judged by how fast they run and how effectively they utilize memory space. Interestingly, how fast a program runs can be established by looking at their underlying algorithms in theory only. We will study how to describe the efficiency of algorithms and evaluate various approaches to implementing data structures and algorithms. This will allow us to make an intelligent choice and alter a data structure suitable for a particular program.
Stack exercise #1 Due: 10-October
Queue exercise #1 Due: 23-October before class
Queue exercise #2 Due: 25-October before class
Tree exercise #1 Due: 01-November before class
Other course exercises will be on repl.it
Project 1 Phase 1 Due: 18-September, Phase 2 Due: 27-September
Project 2 Phase 1 Due: 03-October, Phase 2 Due: 09-October, Phase 3 Due: 18-October, Phase 4 Due: 25-October, Phase 5 Due: 04-November
Project 3 Phase 1 Due: 15-November, Phase 2 Due: 02-December, Phase 3 DueL 10-December