General Information

Instructors:

Lecture Hours: Tuesdays & Thursdays, 2:15 p.m. to 3:45 p.m.
Room: Park 349
Lab: Wednesdays 10:00 a to Noon in Room 231 (additional lab hours will also available, see below)

Laboratories:

• Computer Science Lab Room 231 (Science Building)
• You will also be able to use your own computer to do the labs for this course.

Lab Assistants: The following Lab assistants will be available during the week (names and schedules will be posted by the end of this week) for assistance on lab assignments.

1. Angie Yunqi Chen: Mondays 3:00p to 5:00p and Wed 7:00p to 9:00p in Room 231 PSB
   
2. Renee Jingling Li: Tuesdays 7:00p to 9:00p and Fridays 3:00p to 5:00p
   
   

---

Texts & Software

---

Syllabus

Course Description (from the Course Catalog): Introduction to the fundamental algorithms and data structures using Java. Topics include: Object-Oriented programming, program design, fundamental data structures and complexity analysis. In particular, searching, sorting, the design and implementation of linked lists, stacks, queues, trees and hash maps and all corresponding complexity analysis. In addition, students will also become familiar with Java’s built-in data structures and how to use them, and acquire competency in using a professional grade IDE.

Here is what we plan to learn this semester:

• Overview of Data Structures: data, data abstractions, structures, algorithms, implementation, IDEs.
• Review of Processing
  Assignment#1: Processing Review
• From Processing to Java
• Java Basics
• Eclipse: An Introduction
• Object-Oriented Programming: Core Ideas
• Object-Oriented Programming in Java
• Class Hierarchies
• Test Driven Development
• Lists & Java Collections Framework
• ArrayLists, Linked Lists
• Algorithm Efficiency
• Stacks & Queues
• Recursion
• Trees
• Sets & Hash Tables
• Sorting Algorithms
• Graphs
• Need Some inspiration? Watch this video...

she++: The Documentary from Ellora Israni on Vimeo.

---

Important Dates

January 21 : First lecture
February 18: Exam 1
March 27: Exam 2
April 29: Last lecture
May 1: Exam 3

---

Assignments

1. Assignment#1 (Due on Tuesday, January 28): Click here for details.
   
2. Assignment#2 (Due on Tuesday, February 4): Click here for details.
   
3. Assignment#3 (Due on Thursday, February 13): Click here for details.
   
4. Assignment#4 (Due on Tuesday, March 4): Click here for details.
   
5. Assignment#5 (Due on Thursday, April 3): Click here for details.
   
6. Assignment#6 (Due on Thursday, April 17): Click here for details.

---

Lectures

• Week 1 (January 21, 23)
  
  January 21: Class Cancelled due to snow storm.
  
  Assignment#1 (Due on Tuesday, January 28): Click here for details.
  
  January 23: Course introduction, adminstrivia. Looking at data, data abstractions, structures, algorithms, etc. Processing/Java review.
  
  Sample code: The USPS Volume Processing program (without the data). If you'd like, you can get the data from here.
  
  

  ---

• Week 2 (January 28, 30)
  
  January 28: Today, we will meet in the CS Lab (Room 231 PSB). On to Java. Introduction to Eclipse. Writing Java/Processing programs in Eclipse.
  
  Read: Chapter 1 from Koffman & Wolfgang.
  
  Assignment#2 (Due on Tuesday, February 4): Click here for details.
  
  January 30: Java Basics: program structure, basic input/output, simple dialog-based I/O, Data types and variables, constants, type conversion, reference variables, arrays, statements, methods - class methods and instance methods, error detection and correction: exceptions, try-catch blocks.
  
  Read: Appendix A from Koffman & Wolfgang
  
  

  ---

• Week 3 (February 4, 6)
  
  February 4: Today, we will meet in the CS Lab (Room 231 PSB). Exception Handling in Java. File I/O in Java.
  
  
  February 6: OOP in Java: Interfaces, classes, objects, fields, methods, inheritance, abstract classes, packages.
  
  Assignment#3 (Due on Thursday, February 13): Click here for details.
  
  Program(s) from class: Fraction.java, Fractions.java
  
  

  ---

• Week 4 (February 11, 13)
  
  February 11: Lab Session. Today you will work on your Assignment#3 under supervision. You will learn about incremental design and implementation.
  
  February 13: No class due to snowstorm.
  
  

  ---

• Week 5 (February 18, 20)
  
  February 18: Exam 1 is today.
  
  February 20: Data Structures as collections. Sequential data structures: lists. The java.util.List interface. ArrayList class in java.
  
  Read Chapter 2 (pages 61-71 only) from Koffman & Wolfgang.
  
  Assignment#4 (Due on Tuesday, March 4): Click here for details.
  

  ---

• Week 6 (February 25, 27)
  
  February 25: Implementing (Array) Lists: using static arrays and dynamic arrays. Implementing generic collections/classes.
  
  Read Chapter 2 (pages 71-80 only) from Koffman & Wolfgang.
  
  Extra Credit for Assignment#4: After finishing the Assignment with ArrayLists, implement the dynamic array version of GENERIC Lists as discussed in class and use it in your program. Hand in the code for both versions. Clearly mark the Extra Credit portion of your submission.
  
  February 27: Implementing Lists using dynamic arrays.
  
  

  ---

• Week 7 (March 4, 6)
  
  March 4: Implementing Lists using Linked Lists (and variants: double-linked lists, circular lists, etc.).
  
  Read: Chapter 2 from Koffman & Wolfgang.
  
  March 6: No class today, Deepak is out of town.
  

  ---

• Week 8 (March 11, 13)
  
  No classes. Spring Break!
  

  ---

• Week 9 (March 18, 20)
  
  March 18: Timing and complexity of algorithms: an introduction. Linear Structures, contd. Stacks & Queues.
  
  Read: Chapter 3 from Koffman & Wolfgang. Specifically, (skim over stack implementations on pages 162-170)
  
  Code: PostfixEvaluator code from text. Try this code to run several postfix experessions (as well as ones with syntax errors).
  
  March 20: Stack applications: postfix expression evaluation. Converting infix to postfix expressions, and others. Queues, applications of queues. Case Study: Discrete Event Simulation.
  
  Read: Chapter 4 from Koffman & Wolfgang.
  

  ---

• Week 10 (March 25, 27)
  
  March 25: Queue Applications: Simulating a printer operation.
  
  Assignment#5 (Due on Thursday, April 3): Click here for details.
  
  March 27: Exam 2 is today.
  

  ---

• Week 11 (April 1, 3)
  
  April 1: Recursuion: Writing and composing recursive functions.
  
  Read: Chapter 5
  
  April 3: Recursion, contd. Hierarchical Data Structures: Trees - terminology, binary trees, expression trees, binary search trees, tree traversals: Preorder, inorder, and postorder traversals.
  
  Read: Chapter 6

• Week 12 (April 8, 10)
  
  April 8: Binary Trees and Binary Search Trees: Java implementations.
  
  Assignment#6 (Due on Thursday, April 17): Click here for details.
  
  April 10: Binary Search Trees, contd. Heaps & priority Queues.
  

  ---

• Week 13 (April 15, 17)
  
  April 15: Sets and Maps in Java Collections Framework. Hash Tables: An introduction.
  
  Read: Chapter 7.
  
  April 17: Hash table basics: open addressing, linear probing, quadratic probing; chaining. Graphs: Introduction, terminology, data structure representations: Adjacency Lists, Adjacency Matrices.
  
  Read: Chapter 10

  ---

• Week 14 (April 22, 24)
  
  April 22: Graphs: representations: adjacency lists, adjacency matrices. Graph traversals: Depth-first Traversal & Breadth-First Traversal.
  
  April 24: Graph Algorithms: Dijkstra's Shortest Path algorithm for DAGs. Sorting Data: Selection Sort, Bubble Sort, and Insertion Sort.
  
  Code: Graph.java, UseGraph.java (Version from text)
  
  Read: Chapter 8.
  

  ---

• Week 15 (April 29, May 2)
  
  April 29: Sorting: Selection Sort, Insertion Sort, Bubble Sort. Course review & Wrap up.
  
  Read: Chapter 8.
  
  May 1 : Exam 3 is today.

Course Policies

Communication

Attendance and active participation are expected in every class. Participation includes asking questions, contributing answers, proposing ideas, and providing constructive comments.

As you will discover, I am a proponent of two-way communication and I welcome feedback during the semester about the course. I am available to answer student questions, listen to concerns, and talk about any course-related topic (or otherwise!). Come to office hours! This helps me get to know you. You are welcome to stop by and chat. There are many more exciting topics to talk about that I won't have time to cover in-class.

Please stay in touch with me, particularly if you feel stuck on a topic or project and can't figure out how to proceed. Often a quick e-mail, phone call or face-to-face conference can reveal solutions to problems and generate renewed creative and scholarly energy. It is essential that you begin assignments early.

Grading

There will be eight assignments, weighted equally in the final grading (see below).  Assignments must be submitted according to the Assignment Submission instructions. 

At the end of the semester, final grades will be calculated as a weighted average of all grades according to the following weights:

Exam 1: 20%
Exam 2: 20%
Exam 3: 20%
Assignments: 40%
Total: 100%

Incomplete grades will be given only for verifiable medical illness or other such dire circumstances.

Technology in the classroom

The class meetings/lectures will be a place to learn the concepts that are a part of the syllabus. I will, in the course of a lecture, write code on the board, and/or even do some live coding in class. The objective of this is to illustrate to you how to go about applying the concepts in practice. It is NOT a place for you to open your laptops and start to code with me. In fact, you are encouraged NOT to bring your laptops to class to use them for any purpose. It is distracting to other students. Phone (smart or otherwise) and tablet use during class meetings is also strongly discouraged. Listen, understand, ask questions, and take notes in a notebook if you need to. You will learn more! There will be scheduled class meetings in the lab. I will announce these and this is where you will be doing the coding under my supervision.

The assignments in this course are a place for you to exercise your learning of the concepts and apply them in actual working programs. The best way to get the most of of this course is to try out and code the concepts learned in the class (outside the class!). Do not be afraid to try things! This will improve your understanding and raise questions that you should feel free to bring forward in class. A quick word of advice: stay abreast of the material covered in class, and start your assignments on the day they are announced.

Submission, Late Policy, and Making Up Past Work

Exams

There will be three exams in this course.  The exams will be closed-book and closed-notes.  The exams will cover material from lectures, homeworks, and assigned readings.

Study Groups

I encourage you to discuss the material and work together to understand it. Here are some thoughts on collaborating with other students:

• The readings and lecture topics can be group work. Please discuss the readings and associated topics with each other. Work together to understand the material. I highly recommend forming a reading group to discuss the material -- I will explore many ideas and it helps to have multiple people working together to understand them.
  
• It is fine to discuss the topics covered in the homeworks, to discuss approaches to problems, and to sketch out general solutions. However, you MUST write up the homework answers, solutions, and programs individually without sharing specific solutions, mathematical results, program code, etc.  If you made any notes or worked out something on a white board with another person while you were discussing the homework, you shouldn't use those notes while writing up your answer.
  
• Under ABSOLUTELY NO circumstances should you share computer code with another student, printed, electronic, or otherwise.  Similarly, you are not permitted to use or consult code found on the internet for any of your assignments.
  
• Exams, of course, must be your own individual work.

---

Links

• Watching sorting algorithms at work: Click here!
• The Data Structure Canon, George V. Neville-Neil
  Communications of the ACM, Vol. 53 No. 4, Pages 33-34
  10.1145/1721654.1721668
• Robot demonstrating Sorting Algorithms: Bubble Sort v. Quicksort, Merge Sort v. Quicksort,
• 15 Sorting algorithms in 6 minutes
• And now for something completely different: Illustrating sorting with folk dances!

Created on January 7, 2014.