Course Syllabus
Honors Data Structures and Algorithms in Java
Instructor: Daniel Bauer <bauer@cs.columbia.edu>
Time/Location: Lectures Mondays and Wednesdays 1:10 PM - 2:25 PM in 486 CSB (Clic Lab).
Mandatory recitations times TBA.
Course Description
This course introduces fundamental ways of algorithmic problem solving by organizing and processing information efficiently. The course covers basic data types and structures (arrays, linked lists, stacks, queues, trees, sets, and graphs) as well as programming techniques and algorithms that operate on them (sorting, searching, hashing, finding shortest paths,...). We will examine implementations of data structures and algorithms in Java, as well as functional data structures in Scala. The course also covers the rudiments of analyzing space and time requirements of algorithms, including big-O notation and proofs.
Required Textbook
Mark Allen Weiss, Data Structures and Algorithm Analysis in Java, 3rd Edition, Pearson, 2012. ISBN: 9780132576277. This book should be available at the Columbia Bookstore, on reserve in the library, and from your favorite online booksellers. You do not need to buy this book before the first day of class.
Reference Textbooks (not required)
Cay S. Horstmann, Big Java: Early Objects, 5th Edition, Wiley, 2013. ISBN: 9781118431115. (The late objects version is fine too.)
Cay S. Horstmann, Scala for the Impatient, Addison-Wesley, 2012. (available as an e-book in the Columbia Library).
Main Course topics
- Recursion
- Algorithm Analysis
- Linked Lists
- Stacks, Queues
- Trees
- Heaps
- Sorting
- Hashing
- Graphs
- NP-Completeness
Grading
Your course grade will be based on 6 homework assignments; the lowest will be dropped (50%), a midterm exam (20%) and a final exam (30%).
Tentative Course Schedule
| Week / Dates | Lecture | Recitations | Reading | Homework |
| Week 1- Jan 18 | Introduction to data structures and algorithms, Abstract data types. Linear and binary Search. Arrays, ArrayLists. | Scala/Java setup, using the command line. Java and OOP review. Generics. | Weiss Ch 3.1 to 3.4 | Setup. |
| Week 2 - Jan 23/25: | LinkedLists. Iterators. Comparable. Lists in Scala. Analysis of algorithms, big-O, big-theta, big-omega, and related heuristics and rules. |
Java Review. Introduction to Functional Programming in Scala. | Weiss Ch 2 | Homework 1 out |
| Week 3 - Jan 30/Feb 1 | Series and sequences. Recursion: factorials, fibonacci sequence, "Towers of Hanoi". Analyzing recurrences. | Object-Oriented Programming in Scala. | Weiss Ch 2 | |
|
Week 4 - Feb 6/8 |
Stacks and Queues. Amortized Analysis. | More Scala: Tuples, Generics, Types, Functions | Weiss Ch 3 | Homework 2 Out |
|
Week 5 -Feb 13/15 |
Introduction to trees and tree traversals. Binary Trees and applications. Proofs by Structural Induction. |
Trees: Structural Induction and Recursion | Weiss Ch 4 | |
| Week 6 - Feb 20/22 | Sets and Maps. Binary Search Trees. Balanced BSTs: AVL Trees. | Maps, Trie's and AVL Tree Rotations | Weiss Ch 4 | Homework 3 out |
| Week 7 - Feb 27/Mar 1 | Midterm Review | Midterm Review | ||
|
Week 8 Mar 6/ Mar 8 |
Mar 6: Hash tables: Hash functions. Collision handling: Separate chaining and probing hash tables. Hashing in Java Midterm on Mar 8. |
No recitations. | Weiss Ch 5 | |
| SPRING BREAK | ||||
| Week 9 Mar 20/22 |
Priority queues, binary heaps and the build heap operation. Leftists heaps. Heap sort. | Functional leftist heaps in Scala. | Weiss Ch 6 | Homework 4 out |
| Week 10 Mar 27/29 | Comparison based sorting: Insertion Sort, Selection Sort, Merge Sort, Quick Sort. Radix Sort. | Functional Merge Sort implementation. | Weiss Ch 7 | |
| Week 11 Apr 3/5 | Introduction to Graphs. Traversing Graphs: BFS and DFS. Topological Sorting. Unweighted shortest Paths. | Implementing and visualizing graphs. | Weiss Ch 9 | Homework 5 out |
| Week 12 Apr 10/12 | Weighted shortest path: Dijkstra's algorithm. MSTs. DFS Spanning Trees. | Disjoint sets: Union/find. | Weiss Ch 9, 8 | |
|
Week 13 Apr 17/19 |
DFS applications: Biconnectivity. Euler Circuits. Hamiltonian cycles and NP-complete problems including the Traveling Salesperson Problem. | DFS spanning trees, biconnected components. | Weiss Ch 9.6, 9.7 | Homework 6 out |
|
Week 14 |
Algorithm Design Techniques (Greedy, Divide and Conquer, Dynamic Programming). Final review. |
Dynamic Programming. | Weiss Ch 10 |
Exam Schedule
The midterm exam is scheduled for the regular class time on Wednesday, March 8, 2016. The final exam will take place on Monday, 05/08/2017 1:10pm - 4:00pm in the regular class room.
Homework Policy
You will have approximately 2 weeks to complete each homework assignment. Homework assignments will usually be due on Fridays at 4pm. Homework assignments may be submitted up until 11:55pm the following Tuesday for a 20 point penalty.
Academic Honesty Policy
It is important that you read and understand this section. Any form of academic misconduct will result in a homework or exam grade of zero and could potentially be reported to the appropriate office.
Interaction With Other Students: All homework assignments must be solved individually. You are encouraged to discuss problems with others and to work them out on the whiteboard, but when you sit down to write or code up your solution you must work on your own, without any further interaction. You are not allowed to share your solutions (literal code and theory solutions) with other students.
Online Material: Treat coding problems like paper assignments: You are not permitted to copy any part of other people’s work without attribution. This applies to code produced by other students and to material found on the internet. Sometimes online sources (for instance Stackoverflow) can be useful as a reference. If you have to use code snippets found online you must attribute your source in a comment (complete link). You are not allowed to copy non-trivial code fragments from these sources and you can still lose points if we believe you did not do the work yourself.
Non trivial code is defined as:
- Any code you do not fully understand.
- Code longer than three lines or complete class or method definitions that directly relate to the homework problem.
Example: You may copy a one-liner that opens and reads from a text file, if you attribute your source, but it is not okay to copy an entire method for inserting into a balanced search tree.
In addition to this policy, the Computer Science department’s academic honesty policy, as well as the relevant policies of your school, apply to this course.
Course Summary:
| Date | Details | Due |
|---|---|---|